Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters

기술 요약: 미지의 가속도 파라미터를 가진 가변적 작업(Malleable Jobs)을 위한 동적 코어 할당

문제 정의
본 논문은 멀티코어 컴퓨팅 시스템에서 유입되는 "가변적(malleable)" 작업들을 처리하는 동적 자원 할당 문제를 다룹니다. 할당된 코어 수가 도착 시점에 고정되는 "성형 가능(moldable)" 작업과 달리, 가변적 작업은 실행 중에 처리 용량을 동적으로 재분배할 수 있습니다. 시스템은 고정된 수의 동일한 코어($c$)와 두 가지 관측 가능한 작업 클래스로 구성됩니다. 각 작업 클래스는 할당된 용량 $z$와 병렬화 정도를 결정하는 미지의 파라미터 $p$를 갖는 고유한 속도 향상 함수(speed-up function) $s(z; p)$에 의해 특징지어집니다.

목표는 시스템 내의 장기 평균 작업 수(동일하게, 정상 상태에서의 평균 응답 시간)를 최소화하는 것입니다. 여기에는 근본적인 트레이드오프가 존재합니다: 더 많은 코어를 할당하면 작업 완료를 가속화할 수 있지만, 한계 효용 체감(예: 암달의 법칙)으로 인해 코어 할당이 늘어남에 따라 한계 이득은 감소합니다. 이러한 시스템에서 파라미터가 고정되어 있고 알려져 있을 때의 최적 정책(구체적으로는 각 클래스 내에서 균등 배분을 수행하는 EQUI 정책과 마르코프 결정 과정으로부터 도출된 클래스 간 최적 비율)은 이미 알려져 있으나, 본 논문은 파라미터 $p_1$과 $p_2$를 알 수 없으며 운영 데이터를 통해 학습해야 하는 시나리오를 다룹니다. 이러한 격차는 워크로드의 변화나 하드웨어 업그레이드로 인해 속도 향상 특성이 변할 수 있는 대규모 머신러닝 학습과 같은 현대적 클라우드 GPU 환경의 필요성에 의해 뒷받und 됩니다. 정적인 가정은 비현실적이기 때문입니다.

방법론
저자들은 파라미터 추정과 정책 최적화를 교대로 수행하는 반복적인 학습 및 제어 프레임워크를 제안합니다.

1. 시스템 모델:

   • 작업은 비율 $\lambda$인 푸아송 프로세스를 통해 도착합니다. 서비스 요구 사항은 비율 $\mu$인 지수 분포를 따릅니다.
   • 작업은 클래스 1(확률 $\alpha$) 또는 클래스 2(확률 $1-\alpha$)에 속합니다.
   • 속도 향상 함수 $s(z; p)$는 $z \le 1$일 때 선형이며, $z > 1$일 때는 오목(concave)하고 단조 증가합니다. 두 가지 특정 모델인 암달의 법칙과 거듭제곱 법칙($s(z; p) = \max\{z, 1\}^p$)이 고려됩니다.
   • 할당 정책 $\pi$는 현재 시스템 상태 $(n^{(1)}, n^{(2)})$에 기반하여 클래스 1에 할당될 코어의 비율을 결정합니다. 각 클래스 내에서는 코어가 균등하게 공유됩니다(EQUI 정책).

2. 파라미터 추정 (최대 우도 추정법, MLE):

   • 학습 메커니즘의 핵심은 상태 의존적 간격 시간(inter-departure times)에 기반한 최대 우도 추정량(MLE)입니다.
   • 각 클래스의 출발 프로세스는 상태 의존적 푸아송 프로세스로 모델링됩니다. 순간적인 출발 비율 $\delta^{(i)}$는 작업 수 $n^{(i)}$, 할당된 코어 $c^{(i)}$, 그리고 미지의 파라미터 $p_i$에 따라 달라집니다.
   • 우도 함수는 시스템 상태(따라서 출발 비율)가 일정하게 유지되는 구간들로 간격 시간을 분해함으로써 구축됩니다. 로그 우도는 관측된 출발 시간 및 시스템 상태의 시퀀스를 함수로 하여 명시적으로 도출됩니다.
   • 저자들은 고정된 할당 정책 하에서, 관측된 출발 횟수가 증가함에 따라 이러한 MLE가 강한 일치성(strong consistency)(참값으로 거의 확실하게 수렴함)을 가짐을 증명합니다. 이 증명은 큐잉 시스템의 재생 구조(regenerative structure)와 $p$에 대한 속도 향상 함수의 립시츠 연속성(Lipschitz continuity)에 의존합니다.

3. 정책 최적화 (MDP):

   • 파라미터가 추정되면, 마르코프 결정 과정(MDP)의 벨만 최적 방정식을 풀어 최적의 할당 정책을 계산합니다.
   • 상태 공간은 각 클래스의 작업 수로 정의됩니다. 행동 공간은 클래스 1에 할당되는 코어의 비율입니다.
   • 비용 함수는 시스템 내의 총 작업 수입니다. MDP는 연속 시간 프로세스를 이산 시간 등가 모델로 균질화(uniformizing)한 후 가치 반복법(value iteration)을 사용하여 해결됩니다.

4. 학습 알고리즘:
   본 논문은 이 루프를 구현하는 두 가지 구체적인 알고리즘을 제안합니다.

   • 알고리즘 1a: 최근 관측 창(정해진 수의 출발 횟수 $N_k$로 정의됨) 동안 수집된 데이터만을 사용하여 추정치를 업데이트합니다. 이는 파라미터가 시간에 따라 변할 수 있는 비정상적(non-stationary) 환경에 적응할 수 있게 해줍니다.
   • 알고리즘 1b: $t=0$부터 축적된 모든 데이터를 사용하여 업데이트합니다. 이는 정적인 환경에서 일반적으로 더 빠른 수렴과 높은 정확도를 제공하지만, 변화하는 파라미터에 대한 적응성은 떨어집니다.

주요 기여

• 가변적 작업 모델의 확장: 본 논문은 속도 향상 함수가 사전에 알려져 있다는 가정을 넘어, 미지의 속도 향상 파라미터를 학습하는 메커니즘을 도입함으로써 고전적인 가변적 작업 코어 할당 모델을 확장합니다.
• 큐잉 시스템에서의 통계적 추론: 상태 의존적 간격 시간을 사용하여 병렬화 특성을 추정하기 위한 특정 MLE 절차를 개발하고, 고정된 정책 하에서의 강한 일치성을 증명합니다.
• 통합 학습 프레임워크: 통계적 추정과 동적 계획법 기반의 정책 업데이트를 결합한 두 가지 반복 알고리즘(1a 및 1b)을 제안하고 분석합니다.
• 수치적 검증: 광범-한 수치 실험을 통해 제안된 방법들이 정확한 파라미터 추정치와 준최적(near-optimal) 시스템 성능을 달연함을 입증합니다. 또한, 낮은 병렬성을 가진 작업(낮은 $p$)에 대한 파라미터 추정이 높은 병렬성을 가진 작업보다 더 어렵다는 "준 식별성(quasi-identifiability)" 문제를 강조합니다.

결과

• 수렴성: 수치 실험은 추정량이 참값으로 수렴함을 확인합니다. 알고리즘 1b는 전체 데이터 이력을 사용하기 때문에 정적인 설정에서 1a보다 일반적으로 더 빠르게 수렴합니다.
• 적응성: 파라미터가 특정 시점에 변하는 비정상적 실험에서, 알고리즘 1a는 진화하는 파라미터를 성공적으로 추적하고 할당 정책을 조정하여 동적인 환경에서의 유용성을 입증했습니다.
• 성능: 학습된 정책은 참값을 처음부터 알고 있었을 때 달성했을 이론적 최적치에 근접한 평균 응답 시간을 달성합니다.
• 추정의 비대칭성: 결과는 낮은 병렬성(작은 $p$)을 가진 클래스의 파라미터를 추정하는 것이 해당 영역에서의 속도 향상 함수의 코어 할당에 대한 민감도가 약하기 때문에, 높은 병렬성을 가진 클래스보다 본질적으로 더 어렵고 수렴이 느리다는 것을 나타냅니다.

의의
본 논문은 속도 향상 함수가 알려져 있고 정적이라는 가정이 존재하는 문헌의 중요한 공백을 메움으로써 그 의의를 찾습니다. 이 프레마워크를 통해 온라인으로 파라미터를 학습할 수 있게 함으로써, 자원 효율성이 매우 중요하지만 시스템 특성이 불확실한 현대의 동적인 컴퓨팅 환경(예: 클라우드 기반 AI 학습)에 대한 실질적인 솔루션을 제공합니다. 저자들은 이 프레임워크가 두 개 이상의 작업 클래스로 자연스럽게 확장될 수 있지만, 연관된 벨만 방정식을 푸는 데 따르는 계산 복잡도가 크게 증가한다는 점을 언급하며 모델의 표현력과 계산 가능성 사이의 트레이드오프를 강조합니다. 본 연구는 비정상적 환경, 일반적인 서비스 시간 분포, 그리고 고차원 시스템을 위한 확장 가능한 근사 방법론에 대한 향후 연구의 토대를 마련합니다.