Riassunto Tecnico: TEMPO – Bilanciamento del Carico Expert-Parallel Consapevole del Makespan

1. Definizione del Problema

Nel serving di Mixture-of-Experts (MoE), la latenza di un livello è determinata dal makespan (il tempo massimo impiegato da una singola GPU) a causa dei punti di sincronizzazione alla fine di ogni livello. Gli attuali dispatcher di produzione (ad esempio, EPLB, LPLB, UltraEP, METRO) tentano di bilanciare il carico ottimizzando dei proxy: ovvero il numero di token per GPU o il numero di esperti attivati per GPU. Questi proxy si basano su assunzioni di linearità implicita — ovvero che il tempo di esecuzione dell'esperto sia linearmente proporzionale al conteggio dei token o al conteggio degli esperti, rispettivamente.

Tuttavia, le misurazioni su GPU datacenter (specificamente utilizzando kernel DeepGEMM fp8 grouped GEMM) rivelano che il tempo di esecuzione dell'esperto è non lineare e segue una struttura a due regimi:

1. Regime Limitato dalla Memoria (Flat/Piatto): Al di sotto di una soglia di $n^* \approx 156\text{--}168$ token per esperto, il costo è dominato dal caricamento dei pesi dell'esperto dalla High Bandwidth Memory (HBM). In questo regime, il tempo è costante per ogni replica dell'esperto attivata, indipendentemente dal numero di token.
2. Regime Limitato dal Calcolo (Lineare): Sopra $n^*$, il costo diventa lineare con il conteggio dei token. Tuttavia, a causa delle implementazioni di grouped GEMM che arrotondano i token a M-tile da 128 token, la suddivisione di un esperto tra più repliche introduce un "calcolo con padding", rendendo il costo non lineare in un modo che il semplice conteggio dei token non riesce a cogliere.

Di conseguenza, i batch di decode reali spesso contengono un regime misto: esperti "caldi" con molti token (regime lineare) ed esperti "freddi" con pochi token (regime piatto) coesistono. I proxy esistenti falliscono perché le strategie di bilanciamento dei token frammentano gli esperti freddi (pagando costi di attivazione nascosti), mentre le strategie di bilanciamento delle attivazioni sovraccaricano le repliche calde. Nessun singolo proxy fisso è ottimale in tutti i punti operativi.

2. Metodologia

Modellazione del Costo

Gli autori formalizzano il tempo di esecuzione per esperto $t$ come una funzione max-affine:
$$t = \max(a + bG, c + \beta N)$$
Dove $G$ è il numero di repliche dell'esperto attivate e $N$ è il conteggio dei token.

• $b$ (Activation Floor): Il costo di caricamento dei pesi per una replica aggiuntiva (limitato dalla memoria).
• $\beta$ (Token Slope): Il costo per token nel regime limitato dal calcolo.
• Consapevolezza dei Tile: Per il prefill o batch di grandi dimensioni, un parametro secondario cattura l'effetto "a scalino" del tiling a 128 token, raffinando il modello in $t = \max(a+bG+b_2(T-G), c+\beta N)$.

Questo modello viene calibrato tramite un microbenchmark black-box di dieci minuti sul kernel distribuito, misurando i tempi di wall-clock attraverso griglie $(G, N)$.

Formulazione del Problema

Il problema del dispatch è formalizzato come un problema di minimizzazione del makespan a costo fisso, che gli autori dimostrano essere NP-hard anche con due GPU e replica completa, poiché richiede il bilanciamento simultaneo di due vincoli competitivi (conteggio attivazioni vs conteggio token). Tuttavia, il problema è polinomiale nei limiti degeneri (bilanciamento puro dei token o bilanciamento puro delle attivazioni).

L'Algoritmo TEMPO

TEMPO (Time-modeled Expert-Parallel Optimization) è un dispatcher che risolve questo problema di makespan in millisecondi, operando fuori dal percorso critico (critical path). Il suo solver, tempo fast, impiega quattro fasi:

1. Semina Greedy Consapevole dei Costi: Posiziona interi esperti sulle repliche con il costo marginale più basso, evitando la frammentazione degli esperti freddi.
2. Ribilanciamento delle Attivazioni: Utilizza catene di aumento per ribilanciare i conteggi degli esperti nel regime piatto (dove i movimenti di token sono inefficaci).
3. Ricerca Locale del Collo di Bottiglia: Esegue migrazioni parziali di token per ridurre il makespan nel regime lineare.
4. Ensemble con Tolleranza di Commutazione: Valuta la soluzione corrente rispetto a un baseline Token-LP (Linear Programming) e un'euristica Round-Robin. Commuta solo se la nuova soluzione è superiore di oltre l'1%, garantendo stabilità e ereditando le garanzie teoriche degli algoritmi più semplici.

Integrazione nel Sistema

TEMPO è integrato in SGLang con un focus sull'overhead zero sul percorso critico:

• In-Graph: Un singolo kernel CUDA fuso gestisce il dispatch probabilistico e la raccolta dei conteggi, eliminando i collettivi per livello richiesti dai precedenti solver LP.
• Out-of-Process: Il solver viene eseguito in un processo separato, evitando la contesa del GIL e garantendo che la decisione di dispatch non blocchi il grafo di inferenza.
• Consapevolezza della Topologia: Per configurazioni multi-nodo, una divisione a due stadi assicura che i token siano instradati prima alle repliche sullo stesso nodo, minimizzando il traffico inter-nodo senza alterare il core del solver.

3. Risultati Chiave

Teorici e Simulazioni

• Diagramma di Fase: Un diagramma di fase calibrato dimostra che la policy ottimale fissa oscilla tra il bilanciamento delle attivazioni (limitato dalla memoria) e il bilanciamento dei token (limitato dal calcolo) in base alla dimensione del batch e allo skew degli esperti. TEMPO segue la policy ottimale attraverso l'intero mappamondo.
• Garanzia di Approssimazione: Sotto replica completa, TEMPO fornisce una garanzia di approssimazione additiva di $OPT + \max(b, \beta n_{max})$.
• Guadagni di Simulazione: In ambienti simulati, TEMPO raggiunge un miglioramento fino al 15,5% rispetto al miglior baseline fisso negli scenari a regime misto (specificamente per estrapolazioni EP32–64).

Valutazione Empirica (Testbed A & B)

• Microbenchmark: Su un Testbed A a 8 GPU, TEMPO rimane entro l'1% del miglior baseline fisso in ogni punto della griglia valutata e vince fino al 15,5% dove i regimi si mescolano.
• Serving End-to-End (Qwen3-235B):
  • Su traffico a lungo contesto e heavy di decode, TEMPO migliora il throughput del 4–6% e riduce la latenza p99 inter-token di circa il 15,6%.
  • Su una configurazione EP16 a 2 nodi con splitting consapevole della topologia, i guadagni raggiungono il 4–7%.
  • Crucialmente, il paper nota che gran parte del divario tra TEMPO e il LPLB spedito con SGLang è architettonico (rimozione dei collettivi in-graph); quando LPLB viene portato sulla stessa architettura, il guadagno residuo di TEMPO è principalmente la stabilità nei punti di calcolo intensivo.
• Serving End-to-End (DeepSeek-V3): Su un modello dove la comunicazione domina e gli esperti sono più piccoli per GPU (fuori dalla "regione di vincita"), TEMPO restituisce solo i costi meccanici, performando in linea con il placement statico. Ciò conferma la tesi del paper che i benefici sono condizionali.
• Staleness e Placement: Il sistema è robusto alla staleness del placement (fino a 200ms di deriva). Tuttavia, se il livello di placement è significativamente obsoleto (esperti caldi spostati su repliche fredde), il solo dispatch non può recuperare il throughput; solo il livello di placement può correggere la media, mentre il dispatch ripara la coda della latenza.

4. Significato e Rivendicazioni

La principale rivendicazione del paper non è un guadagno universale di prestazioni, ma un diagramma di fase che predice quando il dispatch basato sul tempo è benefico.

• La "Regione di Vincita": Il dispatch adattivo produce guadagni significativi solo quando:
  1. Il modello ha esperti grandi (alto activation floor $b$).
  2. I batch sono in un regime misto (contenenti sia esperti caldi che freddi).
  3. Il placement è abbastanza obsoleto da causare squilibrio, ma non così obsoleto che solo la migrazione dei pesi possa risolvere il problema.
  4. Il calcolo dell'esperto costituisce una quota significativa del tempo di step (non dominato dalla comunicazione).
• Spostamento Metodologico: Il paper sostiene che "bilanciare il tempo, non i token" è l'approccio rigoroso per il serving MoE. Dimostra che i proxy basati sul conteggio dei token sono sistematicamente errati nei regimi limitati dalla memoria e che un modello di costo calibrato è necessario per navigare l'interazione tra colli di bottiglia di memoria e calcolo.
• Praticità: Il lavoro fornisce una soluzione implementabile (TEMPO) che si integra perfettamente negli stack di serving esistenti (SGLang) con un overhead trascurabile, provando che l'ottimizzazione del makespan complessa può essere eseguita in millisecondi senza bloccare l'inferenza.

Gli autori dichiarano esplicitamente che per forme di esperti piccoli o modelli dominati dalla comunicazione, il dispatch adattivo non offre alcun vantaggio rispetto al placement statico, e il sistema degrada correttamente verso la parità invece di incorrere in una penalità. Il contributo risiede nella mappatura di queste condizioni e nell'algoritmo per navigarle.