💻 computer science

TEMPO: Makespan-Aware Expert-Parallel Load Balancing Across Memory- and Compute-Bound Regimes

TEMPO는 메모리 및 연산 제한 영역(memory- and compute-bound regimes) 전반에 걸친 비선형 전문가 실행 시간을 모델링하여 토큰 분포를 동적으로 최적화함으로써, 기존의 선형 개수 기반 방식이 실패하는 혼합 영역 시나리오에서 최대 15.5%의 처리량 향상과 상당한 지연 시간 감소를 달나성하는 메이크스팬 인지형 전문가 병렬 부하 분산 디스패처를 도입한다.

원저자: Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

게시일 2026-08-14

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 잠들지 않는 도시를 위해 거대하고 고속인 피자 배달 서비스를 운영하고 있다고 상상해 보십시오. 당신에게는 동일한 배달 기사들(GPU)의 함대와 수백 명의 다양한 전문 요리사들("전문가" - AI 모델의 전문가)이 있는 중앙 주방이 있습니다. 고객이 피자를 주문할 때마다, 시스템은 어떤 요리사가 피자를 만들고 어떤 기사가 완성된 피자를 가져갈지 결정해야 합니다. 인공지능의 세계, 구체적으로 "전문가 혼합(Mixture-of-Experts, MoE)"이라 불리는 유형의 모델에서는 정확히 이런 일이 일어납니다. 이 모델들은 수천 개의 작고 전문화된 하위 뇌로 이루어진 거대한 뇌와 같습니다. AI가 생각할 때, 한 번에 전체 뇌를 사용하는 것이 아니라, 작업을 처리하기 위해 몇몇 특정 전문가를 선택합니다.

큰 과제는 전체 팀이 동일한 속도로 움직이게 유지하는 것입니다. 만약 한 명의 기사가 거대하고 복잡한 주문을 맡게 되어 다른 모든 사람이 놀고 있다면, 전체 배달이 지연됩니다. 수년 동안 작업 부하를 균형 있게 맞추기 위한 표준 규칙은 간단했습니다: "주문 수를 균등하게 나누라." 만약 100개의 주문이 있다면, 10명의 기사에게 각각 10개씩 주는 식입니다. 이는 사과 더미를 똑같이 나누는 것처럼 논리적으로 보였습니다. 하지만 어떤 사과는 무거운 돌이고 어떤 사과는 가벼운 깃털이라면 어떨까요? 또는 주방에 새로운 요리사를 호출하는 데 주문의 양과 상관없이 고정된 시간이 걸린다는 규칙이 있다면 어떨까요? 기존의 규칙들은 시간이 항상 주문의 수와 직접적으로 연결되어 있다고 가정했습니다. 이 논문은 그 가정이 틀렸다면 어떨지 묻습니다.

KlingAI에서 연구한 이 논문의 저자들은 기존의 "주문 수 세기" 규칙이 사실은 함정이라는 것을 발견했습니다. 그들은 현대 AI 하드웨어에서 전문가를 처리하는 데 걸리는 시간이 단순히 그 전문가가 보는 토큰(단어 또는 데이터 조각)의 수에 의라 결정되지 않는다는 것을 발견했습니다. 그것은 두 얼굴을 가진 괴물입니다. 때때로, 시간은 메모리 뱅크에서 전문가의 "레시피(가중치)"를 불러오는 순수한 노력, 즉 주문의 크기와 상관없이 일정하게 소요되는 시간에 의해 지배됩니다. 다른 때에는 일단 레시피가 로드되면, 시간은 주문의 수에 따라 선형적으로 증가합니다. 오직 주문의 수만 바라보던 기존 방식들은 레시피를 불러오는 데 드는 숨겨진 비용을 놓치고 있었습니다. 그들은 무게를 재는 대신 개수를 세는 방식으로 깃털과 돌이 섞인 더미를 균형 잡으려 했던 것입니다.

이 문제를 해결하기 위해 팀은 TEMPO(Time-modeled Expert-Parallel Optimization)라는 새로운 디스패처를 구축했습니다. 토큰의 수를 세는 대신, TEMPO는 주방의 물리 법칙을 이해하는 스마트한 교통 통제관처럼 작동합니다. TEMPO는 요리사의 레시피를 불러오는 데 정확히 얼마나 걸리는지, 그리고 피자를 요리하는 데 얼마나 걸리는지를 측정하는 특수한 "비용 모델"을 사용합니다. TEM-PO는 만약 "차가운" 전문가(한동안 사용되지 않은 전문가)가 있다면, 그 작은 주문을 두 명의 기사에게 나누는 것이 재앙이라는 점을 깨닫습니다. 왜냐하면 "로딩 비용"을 두 번 지불해야 하기 때문입니다. 하지만 산더미 같은 주문을 가진 "뜨거운" 전문가라면, 나누는 것이 괜찮습니다.

논문은 TEMPO가 단순히 추측하는 것이 아니라, 밀리초 단위로 모든 요청 배치에 대해 완벽한 균형을 계산한다는 것을 보여줍니다. 연구진은 실제 AI 모델에 테스트를 진행했고, 기존 방식들이 종로 15% 더 느리거나 줄 끝에 서 있는 마지막 몇 명의 고객에게 상당한 지연을 초래한다는 것을 발견했습니다. 그러나 TEMPO는 줄을 매끄럽게 계속 움직이게 합니다. 이는 "모두가 똑같은 수의 사과를 가져라"라는 규칙에서 "모두가 똑같은 양의 일을 해라(어떤 사과는 무겁고 어떤 요리사는 깨어나는 데 시간이 걸린다는 점을 고려하여)"라는 규칙으로 전환하는 것과 같습니다.

연구진은 이 새로운 방법이 정확히 어디에서 작동하고 어디에서 작동하지 않는지를 보여주기 위해 매우 신중했습니다. 그들은 만약 "뜨거운" 전문가들이 너무 많아서 시스템이 순수한 데이터의 양에 의해 압도당하는 상황(컴퓨트 바운드 영역)이라면, 기존의 토큰 카운팅 방식이 실제로 괜찮다는 것을 증명했습니다. 하지만 일부 전문가는 바쁘고 다른 전문가는 쉬고 있으며, "로딩 비용"이 높은 실제 세상에서는 TEMPO가 빛을 발합니다. 그들은 심지어 AI 교통을 위한 일기예보와 같은 "위상도(phase diagram)"를 그려서, 새로운 방법이 시간을 절약할 때와 기존 방법이 충분히 좋을 때를 정확히 예측했습니다.

결국, 이 논문은 단지 더 빠른 알고리즘에 관한 것이 아니라, AI에서 작업의 균형을 맞추는 방식에 대한 우리의 생각을 바꾸는 것에 관한 것입니다. 이는 현대의 복잡하고 고속인 AI 세계에서는 단순히 사물을 세는 것만으로는 부족하다는 것을 가르쳐 줍니다. 데이터를 이동시키는 숨겨진 비용과 작업의 구체적인 형태를 이해해야 합니다. 데이터의 양을 세는 대신 작업을 수행하는 데 걸리는 실제 시간을 측정함으로써, TEMPO는 AI 모델을 더 빠르고 효율적이며 미래의 막대한 수요를 감당할 수 있게 만듭니다. 이는 혼란스러운 주방을 잘 돌아가는 기계로 바꾸어, 피자가 히팅 램프 아래에서 기다리고 있는 동안 어떤 기사도 허송세월하지 않도록 보장합니다.

기술 요약: TEMPO – 메이크스팬(Makespan) 인지형 전문가 병렬 로드 밸런싱

1. 문제 정의

MoE(Mixture-of-Experts) 서빙에서 레이어의 지연 시간은 매 레이어 끝에 있는 동기화 지점 때문에 메이크스팬(단일 GPU에서 소요되는 최대 시간)에 의해 결정됩니다. 현재의 프로덕션 디스패처(예: EPLB, LPLB, UltraEP, METRO)는 토큰 수 또는 활성화된 전문가 수 중 하나를 최적화하여 부하를 조절하는 프록시(proxy)를 사용합니다. 이러한 프록시는 전문가 실행 시간이 토큰 수 또는 전문가 수에 선형적으로 비례한다는 암묵적인 선형성 가정에 의존합니다.

그러나 데이터센터 GPU(특히 DeepGEMM fp8 그룹 GEMM 커널을 사용하는 경우)에 대한 측정 결과, 전문가 실행 시간은 비선형적이며 두 가지 레짐(regime) 구조를 따름이 밝혀졌습니다.

메모리 제한(Flat) 레짐: 전문가당 토큰 수가 $n^* \approx 156\text{--}168$ 미만인 경우, 비용은 HBM에서 전문가 가중치를 스트리밍하는 데 지배됩니다. 이 레짐에서 시간은 활성화된 전문가 복제본의 토큰 수와 상관없이 일정합니다.
연산 제한(Linear) 레겐: $n^*$ 이상인 경우, 비용은 토큰 수에 따라 선형적으로 증가합니다. 그러나 128-토큰 M-타일로 토큰을 올림 처리하는 그룹 GEMM 구현으로 인해, 전문가를 여러 복제본으로 분할하면 "패딩 연산(padded compute)"이 발생하여 단순한 토큰 카운팅으로는 포착할 수 없는 비선형성이 나타납니다.

결과적으로, 실제 디코드 배치는 혼합 레짐을 포함하는 경우가 많습니다. 즉, "핫(hot)" 전문가(많은 토큰 보유, 선형 레짐)와 "콜드(cold)" 전문가(적은 토큰 보유, 플랫 레짐)가 공존합니다. 기존의 프록시들은 토큰 기반 전략이 콜드 전문가를 파편화하여 숨겨진 활성화 비용을 발생시키거나, 활성화 기반 전략이 핫 복제본에 과부하를 주는 문제를 해결하지 못합니다. 고정된 단일 프록시는 모든 운영 지점에서 최적일 수 없습니다.

2. 방법론

비용 모델링

저자들은 전문가당 실행 시간 $t$ 를 다음과 같은 max-affine 함수로 정식화합니다:
$t = \max(a + bG, c + \beta N)$
여기서 $G$ 는 활성화된 전문가 복제본 수, $N$ 은 토큰 수입니다.

$b$ (활성화 바닥값/Activation Floor): 추가 복제본을 위한 가중치 스트리밍 비용(메모리 제한).
$\beta$ (토큰 기울기/Token Slope): 연산 제한 레짐에서의 토큰당 비용.
타일 인식(Tile Awareness): 프리필(prefill) 또는 대규모 배치 처리를 위해, 128-토큰 타일링의 "계단형(staircase)" 효과를 포착하는 보조 파라미터를 사용하여 모델을 $t = \max(a+bG+b_2(T-G), c+\beta N)$ 으로 정교화합니다.

이 모델은 배포된 커널에 대해 $(G, N)$ 그리드 전반의 실제 실행 시간을 측정하는 10분간의 블랙박스 마이크로 벤치마크를 통해 교정됩니다.

문제 정식화

디스패치 문제는 고정 비용 메이크스팬 최소화(fixed-charge makespan minimization) 문제로 정식화됩니다. 저자들은 두 개의 GPU와 전체 복제(full replication) 상황에서도 이 문제가 두 가지 상충하는 제약 조건(활성화 횟수 vs 토크 수)을 동시에 조절해야 하므로 NP-hard임을 증명했습니다. 그러나 순수 토큰 밸런싱이나 순수 활성화 밸런싱과 같은 퇴화된 극한 상황에서는 다항 시간 내에 해결 가능합니다.

TEMPO 알고리즘

TEMPO(Time-modeled Expert-Parallel Optimization)는 밀리초 단위로 이 메이크스팬 문제를 해결하며, 크리티컬 패스(critical path) 외부에서 동작하는 디스패처입니다. 그 솔버인 tempo fast는 네 단계로 작동합니다:

비용 인지형 그리디 시딩(Cost-Aware Greedy Seeding): 콜드 전문가의 파편화를 피하기 위해, 낮은 한계 비용을 가진 복제본에 전체 전문가를 배치합니다.
활성화 재균형(Activation Rebalancing): 플랫 레짐(토큰 이동이 효과적이지 않은 구간)에서 전문가 수를 재균형 맞추기 위해 증강 체인(augmenting chains)을 사용합니다.
병목 로컬 서치(Bottleneck Local Search): 선형 레짐에서 메이크스팬을 줄이기 위해 부분적인 토큰 마이그레이션을 수행합니다.
스위칭 허용 오차를 가진 앙상블(Ensemble with Switching Tolerance): 현재 솔루션을 Token-LP(선형 계획법) 베이스라인 및 Round-Robin 휴리스틱과 비교하여 점수를 매깁니다. 새로운 솔루션이 1% 이상 더 나은 경우에만 전환하여, 안정성을 확보하고 단순 알고리즘의 이론적 보장을 계승합니다.

시스템 통합

TEMPO는 크리티컬 패스 상의 오버헤드를 제로화하는 데 중점을 두어 SGLang에 통합되었습니다:

인-그래프(In-Graph): 단일 퓨즈드 CUDA 커널이 확률적 디스패치 및 카운트 수집을 처리하여, 이전 LP 솔버들이 필요로 했던 퍼 레이어 콜렉티브(per-layer collectives)를 제거합니다.
아웃-오브-프로세스(Out-of-Process): 솔버는 별도의 프로세스에서 실행되어 GIL 경합을 피하고, 디스패치 결정이 인퍼런스 그래프를 차단하지 않도록 합니다.
토폴로지 인식(Topology Awareness): 멀티 노드 설정의 경우, 2단계 분할을 통해 토큰을 먼저 동일 노드의 복제본으로 라우팅함으로써 코어 솔버를 변경하지 않고도 노드 간 트래픽을 최소화합니다.

3. 주요 결과

이론 및 시뮬레이션

페이즈 다이어그램(Phase Diagram): 교정된 페이즈 다이어그램은 배치 크기와 전문가 왜곡(skew)에 따라 최적의 고정 정책이 활성화 밸런싱(메모리 제한)과 토큰 밸런싱(연산 제한) 사이에서 전환됨을 보여줍니다. TEMPO는 이 전체 맵을 따라 최적의 정책을 추적합니다.
근사 보장: 전체 복제 조건 하에서, TEMPO는 $OPT + \max(b, \beta n_{max})$ 의 가산 근사 보장(additive approximation guarantee)을 제공합니다.
시뮬레이션 이득: 시뮬레이션 환경에서 TEMPO는 혼합 레짐(특히 EP32–64 외삽 시)에서 최적의 고정 베이스라인 대비 최대 **15.5%**의 개선을 달와냅니다.

실증 평가 (테스트베드 A & B)

마이크로 벤치마크: 8-GPU 테스트베드 A에서, TEMPO는 평가된 모든 그리드 지점에서 최적의 고정 베이스라인과 1% 이내의 차이를 유지하며, 레짐이 섞이는 구간에서는 최대 **15.5%**까지 우위를 점합니다.
엔드 투 엔드 서빙 (Qwen3-235B):
- 롱 컨텍스트 및 디코드 중심 트래픽에서, TEMPO는 처리량(throughput)을 4–6% 향상시키고 p99 인터-토큰 지연 시간을 약 15.6% 감소시킵니다.
- 토폴로지 인식 분할을 적용한 2-노드 EP16 설정에서 이득은 **4–7%**에 달합니다.
- 중요하게도, 논문은 SGLang의 기존 LPLB와의 격차 상당 부분이 아키텍처적(인-그래프 콜렉티브 제거)인 것임을 언급합니다. LPLB를 동일한 아키텍처로 포팅했을 때, TEMPO의 잔여 이득은 주로 연산 제한 지점에서의 안정성입니다.
엔드 투 엔드 서빙 (DeepSeek-V3): 통신이 지배적이고 전문가가 GPU당 작게 구성된 모델(윈 지역 외부)에서는, TEMPO는 정적 배치와 동일한 성능만을 보여줍니다. 이는 논문의 주장이 조건부적임을 확인해 줍니다.
신선도(Staleness) 및 배치: 시스템은 배치 신선도(최대 200ms 드리프트)에 견고합니다. 그러나 배치 레이어가 심각하게 오래되어(핫 전문가가 콜드 복제본으로 이동) 디스패치만으로 회복할 수 없는 수준이라면, 디스패치는 평균을 고칠 수 없고 배치 레이어만이 평균을 수정할 수 있습니다. 즉, 디스패치는 지연 시간 꼬리(latency tail)를 수리합니다.

4. 의의 및 주장

이 논문의 핵심 주장은 보편적인 성능 승리가 아니라, 언제 시간 기반 디스패치가 유익한지를 예측하는 페이즈 다이어그램입니다.

"승리 영역(Win Region)": 적응형 디스패치는 다음 조건에서 유의미한 이득을 줍니다:
1. 모델의 전문가가 크고 (높은 활성화 바닥값 $b$ ).
2. 배치가 혼합 레짐(핫 및 콜드 전문가가 공존)을 포함할 때.
3. 배치 레이어가 가중치 이동으로만 해결할 수 있을 정도로 너무 오래되지 않았을 만큼만 신선도가 떨어졌을 때.
4. 전문가 연산이 스텝 시간에서 상당한 비중을 차지할 때 (통신에 의해 지배되지 않을 때).
방법론적 전환: 논문은 "토큰이 아닌 시간을 밸런싱하는 것"이 MoE 서빙을 위한 원칙적인 접근법이라고 주장합니다. 토큰 수 프록시는 메모리 제한 레짐에서 체계적으로 틀릴 수 있으며, 메모리와 연산 병목 사이의 상호작용을 탐색하기 위해서는 교정된 비용 모델이 필요함을 입증합니다.
실용성: 본 연구는 밀리초 단위로 인퍼런스 블로킹 없이 복잡한 메이크스팬 최적화를 수행할 수 있음을 증명하며, SGLang에 원활하게 통합되어 오버헤드가 거의 없는 실행 가능한 솔루션(TEMPO)을 제공합니다.

저자들은 작은 규모의 전문가 형태나 통신 지배적 모델의 경우, 적응형 디스패치가 정적 배치보다 나은 점이 없음을 명시하며, 시스템이 페널티를 입지 않고 동일한 성능으로 정상 작동함을 밝혔습니다. 이들의 기여는 이러한 조건들을 매핑하고 이를 탐색하는 알고리즘을 제시하는 데 있습니다.