Resource Heterogeneity-Aware and Utilization-Enhanced Scheduling for Deep Learning Clusters

Dit paper introduceert Hadar en HadarE, twee nieuwe schedulers voor deep learning-clusters die door middel van taakniveau-heterogeniteitsbewustzijn en het forken van taken de resourcebenutting en trainingssnelheid aanzienlijk verbeteren ten opzichte van bestaande systemen zoals Gavel.

De kern

Stel je voor dat je een enorme keuken hebt met verschillende soorten kachels: een superkrachtige gaskachel, een wat langzamere elektrische kookplaat en een oude, trage keramische plaat. Je hebt ook tien verschillende recepten (je "Deep Learning-modellen") die tegelijkertijd moeten worden bereid.

Het probleem met de huidige systemen (zoals Gavel, de huidige standaard) is dat ze een beetje stijf zijn. Ze zeggen: "Recept A heeft 4 kachels nodig. Oké, ik zoek 4 identieke gaskachels. Als die niet allemaal vrij zijn, wacht Recept A gewoon tot ze er allemaal zijn." Dit betekent dat de elektrische kookplaat en de keramische plaat vaak leeg staan terwijl de gaskachels vol zitten. Er is veel verspilling.

De auteurs van dit paper hebben een slimme nieuwe kok bedacht, genaamd Hadar, en een nog slimmere versie, HadarE. Hier is hoe het werkt, vertaald naar alledaags taal:

1. Hadar: De Slimme Chef die Alles Kijkt

Hadar kijkt niet alleen naar de kachels, maar ook naar de recepten zelf.

• Het inzicht: Sommige recepten werken sneller op een gaskachel, maar andere werken bijna net zo goed op een elektrische plaat.
• De oplossing: In plaats van te wachten op 4 perfecte gaskachels, zegt Hadar: "Oké, Recept A, je krijgt 2 gaskachels, 1 elektrische plaat en 1 keramische plaat. Je moet je aanpassen, maar je kunt wel koken!"
• Het resultaat: De keuken draait veel efficiënter. Niets staat stil. De totale tijd om alle maaltijden klaar te krijgen, wordt korter omdat er geen enkele kachel onbenut blijft.

2. HadarE: De "Kloon-methode"

Hadar is al goed, maar HadarE (Hadar Enhancement) is de echte game-changer. Het introduceert een concept dat we kunnen vergelijken met het klonen van een taak.

Stel je voor dat je een enorme taart moet bakken, maar je hebt maar één oven. Het duurt lang.

• Hadar zou zeggen: "We gebruiken de oven zo efficiënt mogelijk, maar we bakken maar één taart tegelijk."
• HadarE zegt: "Wacht even! Laten we het recept voor die taart in 5 kopieën verdelen. We laten 5 verschillende koks (of kachels) elk een klein stukje van die taart bakken tegelijk."

Hoe werkt dit in de praktijk?

1. Verdelen: Zodra een taak (een AI-model) begint, wordt deze opgesplitst in meerdere kopieën.
2. Verspreiden: Deze kopieën worden verspreid over alle beschikbare kachels in de keuken, zelfs als ze allemaal verschillend zijn (snel, traag, oud, nieuw).
3. Samenvoegen: Zodra een kachel klaar is met zijn stukje, meldt hij dit. De "Chef" (de Job Tracker) pakt de resultaten, mengt ze samen (zodat het weer één compleet recept is) en stuurt de taak verder.

Waarom is dit geweldig?

• Geen lege kachels: Zelfs als je maar één taak hebt om te doen, maar 10 kachels hebt, gebruikt HadarE alle 10 kachels om die ene taak sneller af te ronden.
• Snelheid: De taart is veel sneller klaar. In de tests bleek dat HadarE de totale tijd met wel 50% tot 80% verkortte vergeleken met de oude methoden.
• Beter resultaat: Het verrassende is dat de taart (het AI-model) zelfs beter smaakt. Omdat de verschillende kachels op hun eigen manier hebben gewerkt, lijkt het alsof het model meer "ervaring" heeft opgedaan en generaliseert het beter.

Samenvatting in een Metafoor

• De oude manier (Gavel): Een busmaatschappij die alleen bussen laat rijden als er precies 50 passagiers zijn. Als er 49 zijn, staat de bus stil en wachten de passagiers. De andere bussen rijden leeg.
• Hadar: Een slimme busplanner die zegt: "Deze 49 passagiers kunnen ook in een kleinere bus of een taxi stappen, zolang ze maar op weg zijn."
• HadarE: De busmaatschappij die zegt: "We splitsen deze 49 passagiers op in 5 kleine groepjes. Elke groep gaat in een ander voertuig (fiets, scooter, bus, auto). Ze komen allemaal tegelijk aan bij het station, en we vervoeren ze allemaal tegelijk."

Conclusie:
Dit paper introduceert een systeem dat slim genoeg is om te zien dat niet alle computerchips (GPU's) hetzelfde zijn, en dat niet alle taken hetzelfde moeten worden behandeld. Door taken slim te verdelen en zelfs te "vermenigvuldigen" over verschillende machines, wordt de computercluster veel sneller, goedkoper en efficiënter. Het is alsof je van een trage, statische fabriek bent veranderd in een dynamisch, vloeiend team dat altijd op volle toeren draait.

Technische samenvatting

Probleemstelling

Deep Learning (DL) training vereist steeds meer rekenkracht, vaak geleverd door clusters met versnelde hardware zoals GPU's en TPUs. Bestaande schedulers voor deze clusters hebben twee belangrijke tekortkomingen:

1. Gebrek aan fijnmazige heterogene bewustzijn: Veel schedulers (zoals Gavel) behandelen heterogeniteit op het niveau van de hele taak (job-level). Als een taak bijvoorbeeld 4 specifieke GPU's nodig heeft, maar het cluster heeft slechts 3 van dat type en 3 van een ander type beschikbaar, kan de taak niet starten en moet wachten. Ze negeren dat taken vaak op verschillende hardwaretypes kunnen draaien met verschillende prestaties.
2. Onderschatting van hulpbronnen: Zelfs als er voldoende totale rekenkracht is, blijven nodes vaak idle (inactief) omdat taken niet gelijktijdig op meerdere nodes kunnen worden uitgevoerd als ze niet exact op één node passen. Dit leidt tot lage hulpbronbenutting en langere totale trainingsduur.

Methodologie

De auteurs stellen twee oplossingen voor: Hadar en HadarE.

1. Hadar: Een heterogene, taakgeoriënteerde scheduler

Hadar is een nieuwe scheduler die prestatie-heterogeniteit op taakniveau (task-level) analyseert en optimaliseert.

• Optimalisatiekader: Het probleem wordt geformuleerd als een optimalisatieprobleem om de totale nuttigheid (utility) van alle jobs te maximaliseren, rekening houdend met zowel ruimtelijke (welke GPU op welke node) als temporele (wanneer) allocatie.
• Primaal-Duale Framework: Om het complexe integer lineaire programma (ILP) op te lossen, gebruiken de auteurs een primaal-duale methode.
  • Ze introduceren een "dual subroutine" die een prijsfunctie voor hulpbronnen berekent. Deze prijs stijgt exponentieel naarmate meer hulpbronnen worden toegewezen, waardoor jobs met lage nuttigheid worden gefilterd.
  • Een dynamisch programmeringsalgoritme (DP) wordt gebruikt om de beste toewijzing te vinden binnen een rondje, rekening houdend met de "All-or-Nothing" eigenschap van gang scheduling en de bottleneck-snelheid van de langzaamste GPU in een taak.
• Theoretische Garantie: Het algoritme heeft een polynomiale tijdscomplexiteit en biedt een bewezen competitieve ratio (binnen een constante factor van de optimale oplossing).

2. HadarE: Hulpbronbenutting-verbetering via Forking

Om het probleem van idle nodes op te lossen, wordt Hadar uitgebreid tot HadarE (Hadar Enhancement).

• Job Forking: Elke trainingsjob wordt opgesplitst in meerdere kopieën (forks). Als een cluster $n$ nodes heeft, kan een job in $n$ kopieën worden verdeeld.
• Gelijktijdige Executie: Deze kopieën kunnen gelijktijdig op verschillende, heterogene nodes draaien. Dit zorgt ervoor dat er bijna nooit nodes idle blijven zolang er nog werk is.
• Aggregatie en Consolidatie:
  • Een Job Tracker bewaakt de voortgang van alle kopieën.
  • Aan het einde van elke ronde worden de getrainde modelparameters van alle kopieën geaggregeerd (som van trainingsstappen) en geconsolideerd (gewogen gemiddelde van de gewichten).
  • De geconsolideerde parameters worden teruggegeven aan de scheduler voor de volgende ronde.
• Initiële Snelheidsschatting: Omdat het profileren van elke job op elke node tijd kost, gebruikt HadarE een formule voor initiële doorloopschatting op basis van de Performance-Memory Index (PMI), PCIe-bandbreedte, batchgrootte en modelcomplexiteit. Deze schatting wordt tijdens het trainen verfijnd.

Belangrijkste Bijdragen

1. Hadar Scheduler: Een efficiënte scheduler die prestatie-heterogeniteit op taakniveau adresseert, in tegenstelling tot eerdere job-level benaderingen.
2. Optimalisatiealgoritme: Een primaal-duale algoritme met dynamische programmering dat polynomiale tijd heeft en een bewezen competitieve ratio biedt.
3. HadarE (Enhancement): Een innovatieve aanpak waarbij jobs worden geforked om gelijktijdige training op meerdere heterogene nodes mogelijk te maken, wat de hulpbronbenutting maximaliseert.
4. Uitgebreide Validatie: Experimenten op zowel gesimuleerde traces als fysieke clusters (AWS en een lokaal lab) met diverse werklasten.

Resultaten

De evaluatie toont aan dat zowel Hadar als HadarE significant beter presteren dan de state-of-the-art scheduler Gavel en andere bestaande schedulers (zoals Tiresias en YARN-CS).

• Hulpbronbenutting (CRU/GRU):
  • Hadar verbetert de benutting met ongeveer 1,20x ten opzichte van Gavel.
  • HadarE bereikt een verbetering van 1,45x tot 1,62x (afhankelijk van het cluster) ten opzichte van Gavel, door idle nodes te elimineren.
• Totale Trainingsduur (TTD):
  • Hadar verkort de totale tijd met ongeveer 17-21% (1,17x - 1,21x snelheidswinst) ten opzichte van Gavel.
  • HadarE reduceert de totale tijd met 50% tot 80% (afhankelijk van het cluster) ten opzichte van Gavel.
• Gemiddelde Job Voltooiingstijd (JCT):
  • HadarE verlaagt de JCT met een factor van 2,23x tot 2,76x ten opzichte van Gavel.
• Kwaliteit van het Model:
  • Belangrijk is dat de versnelde training via forking geen kwaliteitsverlies veroorzaakt. Sterker nog, HadarE produceert modellen met betere inferentiekwaliteit (hogere nauwkeurigheid, lagere MSE) dan Hadar. Dit wordt toegeschreven aan het feit dat krachtigere nodes meer trainingsstappen kunnen uitvoeren voordat de parameters worden samengevoegd, wat de generalisatie verbetert.

Betekenis

Dit werk is significant omdat het een fundamentele verschuiving biedt in hoe DL-clusters worden beheerd. Door heterogeniteit niet als een obstakel maar als een flexibiliteit te zien (op taakniveau) en door jobs dynamisch te forken, kunnen organisaties hun dure hardware (GPU's/TPUs) veel efficiënter benutten. Dit leidt niet alleen tot snellere trainingstijden en lagere kosten, maar ook tot betere AI-modellen. De oplossing is direct toepasbaar in cloud-omgevingen en grote datacenters waar gemengde hardware veel voorkomt.