💻 computer science

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

O TEMPO introduz um despachante de balanceamento de carga de paralelismo de especialistas consciente do makespan que modela tempos de execução de especialistas não lineares através de regimes limitados por memória e computação para otimizar dinamicamente a distribuição de tokens, alcançando ganhos de até 15,5% no throughput e reduções significativas de latência em cenários de regime misto onde métodos tradicionais baseados em contagem linear falham.

Autores originais: Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

Publicado 2026-08-14

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está administrando um serviço de entrega de pizza massivo e de alta velocidade para uma cidade que nunca dorme. Você tem uma frota de motoristas de entrega idênticos (as GPUs) e uma cozinha central com centenas de chefs especializados diferentes (os "especialistas" de um modelo de IA). Toda vez que um cliente faz um pedido de pizza, o sistema tem que decidir quais chefs trabalharão nela e qual motorista levará a torta pronta. No mundo da Inteligência Artificial, especificamente com um tipo de modelo chamado "Mixture-of-Experts" (MoE), é exatamente isso que acontece. Esses modelos de IA são como cérebros gigantes feitos de milhares de subcérebros menores e especializados. Quando a IA pensa, ela não usa todo o seu cérebro de uma vez; ela escolhe alguns especialistas específicos para lidar com o trabalho.

O grande desafio é manter toda a equipe se movendo na mesma velocidade. Se um motorista ficar preso com um pedido enorme e complicado enquanto todos os outros estão ociosos, toda a entrega será atrasada. O tempo que leva para concluir um lote de pedidos é determinado pela pessoa mais lenta do grupo. Durante anos, a regra padrão para equilibrar essa carga de trabalho foi simples: "Apenas divida o número de pedidos igualmente". Se você tem 100 pedidos, dê 10 para cada um de seus 10 motoristas. Isso parecia lógico, como compartilhar uma pilha de maçãs igualmente. Mas e se algumas maçãs forem pedras pesadas e outras penas leves? Ou se a cozinha tiver uma regra onde escolher um novo chef leva um tempo fixo, não importa quantas pizzas eles façam? As regras antigas assumiam que o tempo estava sempre diretamente ligado ao número de pedidos. O antigo método assumia que o tempo era sempre diretamente proporcional ao número de pedidos. Este artigo pergunta: e se essa suposição estiver errada?

Os pesquisadores por trás deste artigo, trabalhando na KlingAI, descobriram que a antiga regra de "contar os pedidos" é, na verdade, uma armadilha. Eles descobriram que, no hardware de IA moderno, o tempo necessário para processar um especialista não depende apenas de quantos tokens (palavras ou blocos de dados) ele vê. É uma fera de duas faces. Às vezes, o tempo é dominado pelo esforço puro de carregar a "receita" do especialista (pesos) da memória, o que leva um tempo fixo, independentemente de quão pequeno seja o pedido. Outras vezes, uma vez que a receita é carregada, o tempo cresce linearmente com o número de pedidos. Os métodos antigos, que olhavam apenas para o número de pedidos, estavam ignorando o custo oculto de carregar a receita. Eles estavam tentando equilibrar uma pilha de penas e pedras contando-as, em vez de pesá-las.

Para corrigir isso, a equipe construiu um novo despachante chamado TEMPO (Time-modeled Expert-Parallel Optimization). Em vez de apenas contar tokens, o TEMPO age como um controlador de tráfego inteligente que entende a física da cozinha. Ele usa um "modelo de custo" especial que mede exatamente quanto tempo leva para carregar a receita de um chef e quanto tempo leva para cozinhar a pizza. Ele percebe que, se você tem um especialista "frio" (um que não é usado há algum tempo), dividir seu pequeno pedido entre dois motoristas é um desastre porque você tem que pagar a "taxa de carregamento" duas vezes. Mas se você tem um especialista "quente" com uma montanha de pedidos, dividir é aceitável.

O artigo mostra que o TEMPO não apenas adivinha; ele calcula o equilíbrio perfeito para cada lote de pedidos em milissegundos. Eles testaram isso em modelos de IA reais e descobriram que os métodos antigos eram frequentemente 15% mais lentos ou causavam atrasos significativos para os últimos clientes de uma fila. O TEMPO, no entanto, mantém a linha fluindo suavemente. É como mudar de uma regra que diz "todos recebem o mesmo número de maçãs" para uma regra que diz "todos recebem a mesma quantidade de trabalho", levando em conta que algumas maçãs são pesadas e alguns chefs demoram a acordar.

Os pesquisadores foram muito cuidadosos para mostrar exatamente onde este novo método funciona e onde ele não funciona. Eles provaram que, se os especialistas "quentes" forem tão numerosos que o sistema é apenas sobrecarregado pelo volume puro de dados (o regime "compute-bound"), o antigo método de contagem de tokens é, na verdade, adequado. Mas no mundo real, onde alguns especialistas estão ocupados e outros estão descansando, e onde a "taxa de carregamento" é alta, o TEMPO brilha. Eles até mapearam um "diagrama de fase", que é como um mapa meteorológico para o tráfego de IA, prevendo exatamente quando o novo método economizará tempo e quando o método antigo é bom o suficiente.

No fim, este artigo não é apenas sobre um algoritmo mais rápido; é sobre mudar a forma como pensamos sobre o equilíbrio de trabalho na IA. Ele nos ensina que, no complexo e veloz mundo da IA moderna, você não pode apenas contar coisas. Você tem que entender os custos ocultos de mover dados e a forma específica do trabalho. Ao medir o tempo real para realizar o trabalho, em vez de apenas contar os itens, o TEMPO torna os modelos de IA mais rápidos, mais eficientes e prontos para lidar com as demandas massivas do futuro. Ele transforma uma cozinha caótica em uma máquina bem lubrificada, garantindo que nenhum motorista fique esperando enquanto a pizza fica sob a lâmpada de calor.

Resumo Técnico: TEMPO – Balanceamento de Carga Especialista-Paralelo Consciente de Makespan

1. Definição do Problema

No serviço de Mixture-of-Experts (MoE), a latência de uma camada é determinada pelo makespan (o tempo máximo gasto em qualquer única GPU) devido aos pontos de sincronização ao final de cada camada. Os despachantes de produção atuais (ex: EPLB, LPLB, UltraEP, METRO) tentam balancear a carga otimizando proxies: ou o número de tokens por GPU ou o número de especialistas ativados por GPU. Esses proxies dependem de suposições de linearidade implícitas — que o tempo de execução do especialista é linearmente proporcional à contagem de tokens ou à contagem de especialistas, respectivamente.

No entanto, medições em GPUs de datacenter (especificamente usando kernels DeepGEMM fp8 grouped GEMM) revelam que o tempo de execução do especialista é não-linear e segue uma estrutura de dois regimes:

Regime Limitado por Memória (Flat/Plano): Abaixo de um limiar de $n^* \approx 156\text{--}168$ tokens por especialista, o custo é dominado pelo streaming dos pesos do especialista a partir da High Bandwidth Memory (HBM). Neste regime, o tempo é constante por réplica de especialista ativada, independentemente da contagem de tokens.
Regime Limitado por Computação (Linear): Acima de $n^*$ , o custo torna-se linear com a contagem de tokens. No entanto, devido às implementações de grouped GEMM que arredondam os tokens para M-tiles de 128 tokens, a divisão de um especialista entre múltiplas réplicas introduz "computação preenchida" (padded compute), tornando o custo não-linear de uma forma que a simples contagem de tokens não detecta.

Consequentemente, batches de decode do mundo real frequentemente contêm um regime misto: especialistas "quentes" com muitos tokens (regime linear) e especialistas "frios" com poucos tokens (regime plano) coexistem. Os proxies existentes falham porque estratégias de balanceamento de tokens fragmentam especialistas frios (pagando pisos de ativação ocultos), enquanto estratégias de balanceamento de ativação sobrecarregam réplicas quentes. Nenhum proxy fixo único é ideal em todos os pontos operacionais.

2. Metodologia

Modelagem de Custo

Os autores formalizam o tempo de execução por especialista $t$ como uma função max-afim:
$t = \max(a + bG, c + \beta N)$
Onde $G$ é o número de réplicas de especialistas ativadas e $N$ é a contagem de tokens.

$b$ (Piso de Ativação): O custo de streaming de pesos para uma réplica adicional (limitado por memória).
$\beta$ (Inclinação de Tokens): O custo por token no regime limitado por computação.
Consciência de Tile (Tile Awareness): Para prefill ou batches grandes, um parâmetro secundário captura o efeito de "escada" (staircase) de tiling de 128 tokens, refinando o modelo para $t = \max(a+bG+b_2(T-G), c+\beta N)$ .

Este modelo é calibrado via um microbenchmark de caixa-preta de dez minutos no kernel implantado, medindo tempos de parede (wall-clock times) através de grades de $(G, N)$ .

Formulação do Problema

O problema de despacho é formalizado como um problema de minimização de makespan com custo fixo, que é NP-difícil mesmo com duas GPUs e replicação total, pois requer o balanceamento de duas restrições concorrentes (contagem de ativação vs. contagem de tokens) simultaneamente. No entanto, o problema é polinomial em limites degenerados (balanceamento puro de tokens ou balanceamento puro de ativação).

O Algoritmo TEMPO

O TEMPO (Time-modeled Expert-Parallel Optimization) é um despachante que resolve este problema de makespan em milissegundos, operando fora do caminho crítico. Seu solver, tempo fast, emprega quatro estágios:

Semeadura Gananciosa Consciente de Custo (Cost-Aware Greedy Seeding): Coloca especialistas inteiros em réplicas com o menor custo marginal, evitando a fragmentação de especialistas frios.
Rebalanceamento de Ativação: Usa cadeias de aumento para rebalancear contagens de especialistas no regime plano (onde movimentos de tokens são ineficazes).
Busca Local de Gargalo (Bottleneck Local Search): Realiza migrações parciais de tokens para reduzir o makespan no regime linear.
Ensemble com Tolerância de Troca (Switching Tolerance): Avalia a solução atual contra uma linha de base de Token-LP (Programação Linear) e um heurístico de Round-Robin. Ele só troca se a nova solução for >1% melhor, garantindo estabilidade e herdando as garantias teóricas dos algoritmos mais simples.

Integração ao Sistema

O TEMPO é integrado ao SGLang com foco em overhead zero no caminho crítico:

In-Graph: Um único kernel CUDA fundido lida com o despacho probabilístico e a coleta de contagem, eliminando coletivos por camada exigidos por solvers LP anteriores.
Out-of-Process: O solver roda em um processo separado, evitando a contenção do GIL e garantindo que a decisão de despacho não bloqueie o grafo de inferência.
Consciência de Topologia: Para configurações multi-nó, uma divisão de dois estágios garante que os tokens sejam roteados primeiro para réplicas no mesmo nó, minimizando o tráfego inter-nó sem alterar o solver central.

3. Resultados Principais

Teóricos e Simulação

Diagrama de Fase: Um diagrama de fase calibrado demonstra que a política fixa ótima alterna entre balanceamento de ativação (limitado por memória) e balanceamento de tokens (limitado por computação) com base no tamanho do batch e no skew de especialistas. O TEMPO acompanha a política ótima através de todo este mapa.
Garantia de Aproximação: Sob replicação total, o TEMPO fornece uma garantia de aproximação aditiva de $OPT + \max(b, \beta n_{max})$ .
Ganhos de Simulação: Em ambientes simulados, o TEMPO alcança até 15,5% de melhoria sobre a melhor linha de base fixa em cenários de regime misto (especificamente para extrapolações EP32–64).

Avaliação Empírica (Testbed A & B)

Microbenchmarks: Em um Testbed A de 8 GPUs, o TEMPO permanece dentro de 1% da melhor linha de base fixa em cada ponto de grade avaliado e vence por até 15,5% onde os regimes se misturam.
Serviço End-to-End (Qwen3-235B):
- Em tráfego de contexto longo e pesado em decode, o TEMPO melhora o throughput em 4–6% e reduz a latência inter-token p99 em ~15,6%.
- Em uma configuração EP16 de 2 nós com divisão consciente de topologia, os ganhos chegam a 4–7%.
- Crucialmente, o artigo observa que grande parte da diferença entre o LPLB entregue pelo SGLang e o TEMPO é arquitetural (remoção de coletivos in-graph); quando o LPLB é portado para a mesma arquitetura, o ganho residual do TEMPO é primariamente a estabilidade em pontos limitados por computação.
Serviço End-to-End (DeepSeek-V3): Em um modelo onde a comunicação domina e os especialistas são menores por GPU (fora da "região de vitória"), o TEMPO retorna apenas custos de mecanismo, performando de forma equivalente ao posicionamento estático. Isso confirma a afirmação do artigo de que os benefícios são condicionais.
Estagnação (Staleness) e Posicionamento: O sistema é robusto à estagnação de posicionamento (drift de até 200ms). No entanto, se a camada de posicionamento estiver significativamente estagnada (especialistas quentes movidos para réplicas frias), o despacho sozinho não pode recuperar o throughput; apenas a camada de posicionamento pode corrigir a média, enquanto o despacho repara a cauda de latência.

4. Significância e Alegações

A principal alegação do artigo não é uma vitória de desempenho universal, mas um diagrama de fase que prevê quando o despacho baseado em tempo é benéfico.

A "Região de Vitória": O despacho adaptativo gera ganhos significativos apenas quando:
1. O modelo possui especialistas grandes (alto piso de ativação $b$ ).
2. Os batches estão em um regime misto (contendo especialistas quentes e frios).
3. O posicionamento está estagnado o suficiente para causar desbalanceamento, mas não tanto que apenas a migração de pesos possa corrigir.
4. O cálculo do especialista constitui uma parcela significativa do tempo de passo (não dominado por comunicação).
Mudança Metodológica: O artigo argumenta que "balancear o tempo, não os tokens" é a abordagem fundamentada para o serviço de MoE. Demonstra que proxies de contagem de tokens são sistematicamente errados em regimes limitados por memória e que um modelo de custo calibrado é necessário para navegar a interação entre gargalos de memória e computação.
Praticidade: O trabalho fornece uma solução implantável (TEMPO) que se integra perfeitamente a stacks de serviço existentes (SGLang) com overhead desprezível, provando que a otimização complexa de makespan pode ser realizada em milissegundos sem bloquear a inferência.

Os autores afirmam explicitamente que para formas de especialistas pequenos ou modelos dominados por comunicação, o despacho adaptativo não oferece vantagem sobre o posicionamento estático, e o sistema degrada corretamente para a paridade em vez de incorrer em penalidade. A contribuição é o mapeamento dessas condições e o algoritmo para navegá-las.