On the Computation Rate of All-Reduce

Titel: Over de Berekeningsrate van All-Reduce

Auteurs: Yufeng Zhou en Hua Sun (Universiteit van North Texas)
Datum: 27 februari 2026

1. Probleemstelling

Het paper onderzoekt de fundamentele limieten van de All-Reduce operatie in gedistribueerde netwerken, een cruciale primitief voor het trainen van moderne grote schaal leermodellen (zoals Deep Learning).

• Definitie: In een netwerk met $K$ knopen, houdt elke knoop een invoer $W_i$. Het doel is dat elke knoop de som van alle invoeren ($\sum_{i=1}^K W_i$) berekent via een communicatienetwerk.
• Netwerkmodel: Het netwerk bestaat uit $K$ knopen die verbonden zijn door ruisvrije, parallelle links met willekeurige bandbreedte $\beta_{ij}$ (aantal symbolen dat per gebruik kan worden verzonden).
• Doel: Het maximaliseren van de berekeningsrate ($R$), gedefinieerd als het aantal som-instanties dat per netwerkgebruik kan worden berekend. Dit staat in contrast met traditionele computerwetenschappelijke metrics zoals latentie of totale bandbreedteverbruik; hier ligt de focus op de informatie-theoretische capaciteit.

2. Methodologie

De auteurs benaderen het probleem vanuit een informatie-theoretisch perspectief en gebruiken twee hoofdmethodes om grenzen te stellen aan de maximale rate:

A. Cut-Set Bovengrens (Upper Bound)

• Principe: Gebaseerd op het cut-set argument uit netwerkcodering.
• Redenering: Als men een deelverzameling van knopen $K$ afscheidt van de rest van het netwerk ($K^c$), kan de totale som niet worden berekend zonder dat informatie de "cut" passeert.
• Formulering: De rate kan de totale bandbreedte van de links tussen een verzameling $K$ en zijn complement $K^c$ niet overschrijden.
  $$R^* \leq \min_{\emptyset \neq K \subset [K]} \sum_{i \in K, j \in K^c} \beta_{ij}$$
• Bewijs: Een entropie-gebaseerd bewijs toont aan dat zelfs met volledige samenwerking binnen de groepen, de informatiestroom de rate beperkt.

B. Lineair Programmeren Ondergrens (Lower Bound)

• Principe: Een haalbaar schema gebaseerd op tijdsharing (of bandbreedte-sharing) over alle mogelijke "Eerst Reduce, dan Broadcast" strategieën.
• Stap 1: Reduce: Alle invoeren worden geaggregeerd naar één wortelknoop via een gerichte boom (Rooted MAC Tree).
• Stap 2: Broadcast: De berekende som wordt van de wortel naar alle andere knopen verspreid via een andere boom (Rooted BC Tree).
• Optimalisatie: De auteurs definiëren een "Rooted MAC-BC Network" dat deze twee stappen combineert. Ze formuleren een Lineair Program (LP) om de gewichten ($\lambda_z$) van alle mogelijke MAC-BC-netwerken te optimaliseren binnen de bandbreedtebeperkingen van het fysieke netwerk.
  $$R^* \geq \max \sum \lambda_z \quad \text{onder de voorwaarde} \quad \sum \lambda_z \vec{\beta}_{TMB}^z \leq \vec{\beta}$$
• Complexiteit: Het vinden van alle mogelijke bomen is exponentieel ($K^{K-2}$), wat het LP in de praktijk zwaar rekent, maar het biedt een theoretische ondergrens.

3. Belangrijkste Resultaten

De auteurs passen de algemene grenzen toe op specifieke netwerktopologieën en vinden de volgende resultaten:

A. Algemene Klasse van Netwerken

Er wordt een klasse van netwerken geïdentificeerd (gerelateerd aan lineaire combinaties van boomtopologieën met een specifieke "cut-edge") waarvoor de boven- en ondergrens exact overeenkomen. Voor deze netwerken is de maximale berekeningsrate exact bepaald.

B. Specifieke Topologieën

Voor veelvoorkomende netwerken worden de grenzen expliciet berekend. In alle gevallen is de verhouding tussen de boven- en ondergrens maximaal 2 (d.w.z. de rate is bepaald binnen een factor 2).

1. Uniforme Complete Netwerken (Complete Graphs):

   • Alle knopen zijn verbonden met bandbreedte 1.
   • Resultaat: $\frac{K}{2} \leq R^* \leq K-1$.
   • De ondergrens wordt bereikt door het combineren van $K$ verschillende MAC-BC-netwerken.

2. Cycli en Ringen (Cycles & Rings):

   • Uniforme Cyclus (richting): $\frac{K}{2(K-1)} \leq R^* \leq 1$.
   • Uniforme Ring (twee richtingen): $\frac{K}{K-1} \leq R^* \leq 2$.
   • Opmerking: De bereikte rate voor de ring komt overeen met de bekende "Ring-All-Reduce" algoritmes uit de literatuur, maar wordt hier bewezen als optimaal binnen de gegeven kaders.

3. Uniforme Hyperkubussen (Hypercubes):

   • Voor een hyperkubus met $K=2^U$ knopen.
   • Resultaat: $\frac{2^{U-1}}{2^U - 1} U \leq R^* \leq U$.
   • De ondergrens wordt bereikt door een complexe constructie van $2^U \times U!$ verschillende MAC-BC-netwerken die gebruikmaken van permutaties van de bits in de knoopadressen.

4. Niet-uniforme 3-knoop Cyclus:

   • Voor een cyclus met bandbreedtes $a, b, c$ wordt de exacte rate bepaald als $\min(a,b,c) \leq \frac{a+b+c}{4}$. Anders ligt de rate tussen $\frac{a+b+c}{4}$ en $\min(a,b,c)$.

4. Bijdragen en Significance

• Theoretische Fundamenten: Het paper biedt de eerste informatie-theoretische analyse van de berekeningsrate voor All-Reduce, los van de traditionele focus op latentie.
• Optimaliteit: Voor een specifieke klasse van netwerken wordt de exacte capaciteit bewezen. Voor andere belangrijke topologieën (ringen, hyperkubussen) worden de beste bekende grenzen geleverd.
• Gap van 2: Een belangrijk inzicht is dat voor alle onderzochte netwerken de berekende rate binnen een multiplicatieve factor van 2 van de theoretische limiet ligt. Dit suggereert dat de "Reduce-then-Broadcast" strategie zeer efficiënt is, zelfs als deze niet altijd exact optimaal is.
• Open Problemen:
  • Het paper stelt dat de cut-set bovengrens waarschijnlijk niet kan worden verbeterd, maar dat het een open probleem blijft of er netwerken zijn waar de ondergrens (via LP) kan worden verbeterd door gecombineerde codering (joint coding) in plaats van gescheiden codering.
  • De exacte rate voor een uniforme complete grafiek met 3 knopen ($1.5 \leq R^* \leq 2$) blijft een open vraag.
  • Toepassing op Secure Aggregation (veilige aggregatie) wordt genoemd als een interessante toekomstige richting.

Conclusie

Zhou en Sun tonen aan dat het gebruik van tijdsharing over diverse boom-gebaseerde aggregatie- en distributiestrategieën een zeer krachtige methode is om de berekeningsrate van All-Reduce te maximaliseren. Hoewel de exacte optimale rate voor alle netwerktopologieën nog niet volledig is gekarakteriseerd, bieden hun grenzen een robuust kader voor het ontwerpen van efficiënte communicatieprotocollen in grote schaal distribueerde systemen.