Scheduling Parallel Optical Circuit Switches for AI Training

Dit paper introduceert Spectra, een algoritme dat de makespan voor het plannen van AI-trainingverkeer over parallelle optische circuit switches aanzienlijk verlaagt door een drie-stapsaanpak van decompositie, belastingbewust toewijzen en ladingsvereffening, waardoor het aanzienlijk beter presteert dan bestaande methoden.

De kern

Stel je voor dat je een gigantische bibliotheek hebt waar duizenden boeken (data) elke seconde van de ene naar de andere plek moeten worden verplaatst. Dit is wat er gebeurt in een datacentrum tijdens het "trainen" van een slimme AI. De boeken moeten razendsnel van A naar B, en als ze te lang wachten, stopt de hele bibliotheek met werken.

Deze paper, getiteld "Scheduling Parallel Optical Circuit Switches for AI Training", gaat over hoe we die boeken sneller en zuiniger kunnen verplaatsen.

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De Verkeersopstopping

In de oude wereld gebruikten datacentra elektronische schakelaars (zoals verkeerslichten). Die zijn echter traag en verbruiken veel stroom als er veel verkeer is.
De oplossing? Optische Circuit Switches (OCS). Denk hierbij niet aan verkeerslichten, maar aan spiegels. Je kunt een spiegel zo draaien dat een lichtstraal (data) direct van de ene deur naar de andere gaat. Dit is supersnel en verbruikt weinig energie.

Maar er is een addertje onder het gras:
Het duurt even om die spiegel te draaien (de "reconfiguratie delay"). Als je de spiegel te vaak moet draaien om verschillende boeken te verplaatsen, sta je in de file. De tijd die de hele bibliotheek nodig heeft om klaar te zijn, heet de makespan (de totale doorlooptijd). Hoe korter die tijd, hoe sneller de AI leert.

2. De Oplossing: SPECTRA (De Slimme Regisseur)

De auteurs van dit paper hebben een nieuwe regisseur bedacht, genaamd SPECTRA. In plaats van één spiegel te gebruiken, gebruiken ze er meerdere tegelijk (parallel). Maar hoe verdeel je het werk zo dat niemand in de file staat?

SPECTRA werkt in drie simpele stappen, die we kunnen vergelijken met het organiseren van een grote verhuizing:

Stap 1: DECOMPOSE (De Verhuisklussen Indelen)

Stel je voor dat je een enorme lijst hebt met verhuisdozen die verplaatst moeten worden.

• Wat doet SPECTRA? Het kijkt naar de hele lijst en zegt: "Oké, we kunnen dit opdelen in een paar grote, logische groepen."
• De Analogie: In plaats van één voor één dozen te pakken, groepeert SPECTRA de dozen in pakketten die perfect passen in één verhuistruck (een 'permutatie'). Het zorgt ervoor dat er zo min mogelijk losse, kleine stukjes zijn die extra tijd kosten.

Stap 2: SCHEDULE (De Trucks Verdelen)

Nu heb je die pakketten en een rij verhuistrucks (de parallelle optische switches).

• Wat doet SPECTRA? Het kijkt naar de zwaarste pakketten en verdeelt ze slim over de trucks.
• De Analogie: Stel je hebt 2 trucks. De zwaarste doos gaat in de eerste truck. De volgende zware doos gaat in de tweede truck (want die is nog leeg). Zo proberen ze de lading zo gelijk mogelijk te verdelen, zodat geen enkele truck te lang onderweg is. Dit heet "load-aware assignment".

Stap 3: EQUALIZE (De Laatste Balans)

Soms blijft er toch een ongelijkheid. Misschien heeft Truck 1 net iets meer te dragen dan Truck 2, en dat kost extra tijd.

• Wat doet SPECTRA? Het kijkt of het mogelijk is om een deel van een pakket van de zwaarste truck af te halen en naar de lichtste truck te verplaatsen.
• De Analogie: Stel Truck 1 heeft een zware doos die halfvol is. SPECTRA zegt: "Wacht, we halen de bovenste helft van die doos eraf en doen die in Truck 2." Hierdoor rijden beide trucks bijna even lang, en is de totale verhuistijd korter. Dit is de "Equalize"-stap.

3. Waarom is dit zo goed?

De auteurs hebben hun nieuwe regisseur (SPECTRA) getest tegen de oude methoden en de beste bestaande methoden.

• Het resultaat: SPECTRA is veel sneller.
  • Bij een standaard AI-model (GPT) was het 1,4 keer sneller.
  • Bij een complexer model (MoE) was het 1,9 keer sneller.
  • Bij standaard tests was het zelfs 2,4 keer sneller.

Het is alsof je een verhuizing die normaal 10 uur duurt, in 4 uur hebt afgerond.

4. De Onderbouwing (De Wiskunde)

De auteurs hebben niet zomaar geraden. Ze hebben bewezen dat er een theoretisch minimum is aan tijd dat nodig is (een "ondergrens"). SPECTRA komt zo dicht mogelijk bij dit theoretische minimum. Het is alsof ze de snelst mogelijke route hebben gevonden die wiskundig haalbaar is.

Samenvatting in één zin

SPECTRA is een slimme manier om data in een datacentrum te verdelen over meerdere snelle optische schakelaars, zodat de AI-training veel sneller klaar is door slimme groepering, eerlijke verdeling en het oplossen van kleine onevenwichtigheden.

Kortom: Het zorgt ervoor dat de "spiegels" in het datacentrum niet te veel tijd verliezen met draaien, waardoor de AI veel sneller kan leren.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Scheduling Parallel Optical Circuit Switches for AI Training" in het Nederlands.

Titel: Scheduling Parallel Optical Circuit Switches for AI Training

Auteurs: Kevin Liang, Litao Qiao, Isaac Keslassy, Bill Lin

---

1. Probleemstelling

De snelle groei van AI-training (zoals GPT-modellen en Mixture of Experts) heeft de vraag naar datacenter-bandbreedte en energie-efficiëntie drastisch verhoogd. Traditionele elektronische pakketgeswitchte netwerken schalen slecht in grootte en vermogen om deze eisen te halen. Optische Circuit Switches (OCS) worden gezien als een veelbelovend alternatief vanwege hun hoge bandbreedte en lage energieper-bit.

Om de capaciteit te vergroten, worden vaak meerdere OCS-eenheden parallel ingezet. Het centrale probleem dat in dit artikel wordt aangepakt, is het plannen (scheduling) van een verkeersmatrix $D$ (de data die tussen racks moet worden verplaatst) over $s$ parallelle OCS-switches.

De uitdagingen zijn:

• Herschakelvertraging ($\delta$): OCS-switches hebben een niet-verwaarloosbare vertraging nodig om hun configuratie te wijzigen.
• Makespan-minimalisatie: Het doel is om de totale tijd (makespan) te minimaliseren die nodig is om de volledige verkeersmatrix $D$ te verwerken. Omdat AI-training synchroon verloopt, bepaalt de langste schakel (de makespan) de totale doorvoertijd (Collective Completion Time - CCT).
• Complexiteit: Het optimaliseren van deze planning is NP-hard, zelfs voor één switch. Bestaande oplossingen focussen vaak op één switch of gebruiken suboptimale strategieën voor parallelle switches.

2. Methodologie: Het SPECTRA-algoritme

De auteurs stellen SPECTRA (Scheduling ParallEl Circuit switches for data cen-ter TRAffic) voor, een algoritme dat het probleem oplost in drie opeenvolgende stappen, elk opgelost met polynomiale tijdcomplexiteit:

Stap 1: DECOMPOSE (Ontleden)

De verkeersmatrix $D$ wordt ontbonden in een minimale set van gewogen permutaties $\{P_1, ..., P_k\}$ met bijbehorende gewichten $\{\alpha_1, ..., \alpha_k\}$.

• Doel: Het aantal permutaties minimaliseren (om het aantal herschakelvertragingen $\delta$ te minimaliseren) en tegelijkertijd de totale duur van de permutaties minimaliseren.
• Techniek: Het algoritme gebruikt een Maximum Weight Matching (MWM) onder knopdekkingseisen (node coverage constraints). Het bouwt iteratief permutaties die het "graad" (aantal niet-nul elementen) van de resterende matrix verlagen.
• Refinement: Een sub-routine (REFINE) past de gewichten $\alpha_i$ aan om te garanderen dat de som van de permutaties de oorspronkelijke matrix $D$ volledig dekt.

Stap 2: SCHEDULE (Plannen)

De gegenereerde permutaties worden toegewezen aan de $s$ beschikbare switches.

• Doel: De belasting over de switches verdelen om de makespan te minimaliseren.
• Techniek: Dit is een variant van het "Makespan Minimization on Identical Parallel Machines" probleem. Het algoritme sorteert de permutaties op afnemende gewichten en past een Longest Processing Time (LPT)-heuristiek toe: elke permutatie wordt toegewezen aan de switch die op dat moment de minst zware belasting heeft (inclusief de herschakelvertraging $\delta$).

Stap 3: EQUALIZE (Verevenen)

Om de makespan verder te reduceren, wordt de belasting tussen de zwaarst en lichtst belaste switches in evenwicht gebracht.

• Doel: De "hotspots" (zwaarst belaste switch) verminderen door delen van lange permutaties te splitsen en te verplaatsen.
• Techniek: Het algoritme identificeert de switch met de grootste belasting ($h_{max}$) en de kleinste ($h_{min}$). Als het verschil groter is dan $\delta$, wordt een deel van de langste permutatie op $h_{max}$ gesplitst en verplaatst naar $h_{min}$. Dit proces is iteratief en houdt rekening met de extra $\delta$-vertraging die nodig is voor de nieuwe configuratie op de ontvangende switch.

3. Belangrijkste Bijdragen

• Nieuw Algoritme (SPECTRA): Een geïntegreerde aanpak die decompositie, planning en load-balancing combineert voor parallelle OCS.
• Theoretische Ondergrenzen: De auteurs leiden nieuwe theoretische ondergrenzen af voor de minimale makespan van een willekeurige verkeersmatrix over $s$ parallelle switches. Dit biedt een benchmark om de optimaliteit van algoritmen te beoordelen.
• Nieuwe Workload: Presentatie van een nieuwe dataset gebaseerd op Qwen-57B (Mixture of Experts) verkeer, gemeten in een 64-GPU cluster. Dit vult een gat in de literatuur, aangezien bestaande benchmarks vaak te simpel of te gesparseerd zijn.
• Vergelijking met State-of-the-Art: Een uitgebreide evaluatie tegen bestaande methoden, waaronder een variant gebaseerd op het LESS-algoritme (sparsiteit-gebaseerd) en een variant die ECLIPSE (een bestaande decompositiemethode) gebruikt.

4. Resultaten

Het algoritme is geëvalueerd op drie soorten werklasten:

1. GPT-3B Workload: Een gesparseerde en sterk scheef verdeelde verkeersmatrix (32x32).
2. MoE Workload (Qwen): Een dichte en relatief uniforme verkeersmatrix (64x64).
3. Standaard Benchmark: Een willekeurige matrix met 100x100 poorten.

Kernresultaten:

• Prestatieverbetering: SPECTRA presteert aanzienlijk beter dan de BASELINE (gebaseerd op LESS):
  • 1.4x kortere makespan voor GPT-workloads.
  • 1.9x kortere makespan voor MoE-workloads.
  • 2.4x kortere makespan voor standaard benchmarks.
• Vergelijking met ECLIPSE: Een variant van SPECTRA die ECLIPSE gebruikt voor de decompositiestap presteert slechter dan de originele SPECTRA-decompositie, vooral bij dichte matrices (MoE).
• Optimaliteit: De door SPECTRA bereikte makespans komen zeer dicht in de buurt van de theoretisch afgeleide ondergrenzen, wat aantoont dat het algoritme in de praktijk bijna optimaal presteert.
• Robuustheid: Het algoritme werkt goed zowel bij zeer gesparseerde als zeer dichte verkeerspatronen en is minder gevoelig voor variaties in de herschakelvertraging $\delta$ dan concurrenten.

5. Significance (Betekenis)

Dit onderzoek is cruciaal voor de toekomst van AI-datacenters. Het toont aan dat algoritmische co-design (het gezamenlijk optimaliseren van verkeersontleding en switch-planning) essentieel is om de voordelen van optische circuit switching volledig te benutten.

• Energie en Snelheid: Door de makespan te minimaliseren, worden AI-trainingstaken sneller voltooid en wordt energie bespaard (minder wachttijd voor accelerators).
• Schalbaarheid: De aanpak maakt het mogelijk om grote clusters (zoals die nodig voor LLM's) efficiënter te bedienen met parallelle optische hardware, wat een knelpunt in de huidige infrastructuur oplost.
• Praktische Toepasbaarheid: De lage uitvoeringstijd van het algoritme (milliseconden) maakt het geschikt voor real-time of near-real-time planning in datacenters.

Kortom, SPECTRA biedt een bewezen, efficiënte oplossing voor het planningsprobleem in de volgende generatie AI-datacenters, waarbij het de beperkingen van optische herschakeling effectief omzeilt.