Concurrent Scheduling of High-Level Parallel Programs on Multi-GPU Systems

Moderne supercomputers zijn niet langer simpelweg snellere versies van de machines van enkele decennia geleden; het zijn enorme collecties van duizenden gespecialiseerde processors die samenwerken. Om het meeste uit deze massieve systemen te halen, vertrouwen wetenschappers op software die automatisch kan beslissen welk deel van een berekening naar welke processor gaat en hoe data tussen hen beweegt. Dit is een moeilijke taak, omdat de software het geheugen en de communicatie moet beheren zonder het eigenlijke werk te vertragen. Als het systeem te veel tijd besteedt aan het uitzoeken waar data moet worden geplaatst of hoe het consistent moet blijven, staan de krachtige processors stil, wat energie en tijd verspilt. De uitdaging is om deze beslissingen snel genoeg te nemen zodat de computer nooit stopt om na te denken, waarbij de workflow zo soepel blijft als de stroom van water in een rivier.

Onderzoekers aan de Universiteit van Innsbruck hebben een nieuwe manier ontwikkeld om dit planningsprobleem aan te pakken voor systemen die zijn uitgerust met veel grafische processoren, of GPU's. Deze chips zijn ontworpen om enorme hoeveelheden parallel werk aan te kunnen, maar het coördineren van honderden hiervan vereist een geavanceerde manager. Het team introduceerde een methode genaamd instructie-grafiekplanning (instruction-graph scheduling), die fungeert als een gedetailleerde, laag-niveau kaart van elke afzonderlijke operatie die de computer moet uitvoeren. In plaats van beslissingen ter plekke te nemen terwijl elke stap nodig is, maakt het systeem een compleet plan dat zowel geheugenallocatie, datatransfers als de eigenlijke berekeningen omvat. Dit plan wordt gegenereerd terwijl de computer al bezig is met vorige taken, waardoor de scheduler effectief vooruit kan kijken en de volgende stappen kan voorbereiden zonder de huidige stroom te onderbreken.

De kern van deze aanpak is een verschuiving in hoe de software naar het werk kijkt. Voorheen genereerde het systeem een lijst met taken op hoog niveau en bepaalde pas de specifieke details, zoals het kopiëren van geheugen, op het moment dat het tijd was om ze uit te voeren. Dit leidde vaak tot vertragingen omdat het systeem halverwege een berekening moest stoppen om afhankelijkheden te analyseren. De nieuwe methode breekt elke taak af in de kleinste componenten, zoals het alloceren van een specifك blok geheugen of het verzenden van een klein stukje data naar een naburige processor. Door deze kleine stappen in een enkele, onderling verbonden grafiek te rangschikken, kan het systeem precies zien welke stappen tegelijkertijd kunnen plaatsvinden. Dit stelt de computer in staat om communicatie te overlappen met berekening, wat betekent dat data tussen processors kan bewegen terwijl de chips bezig zijn met het verwerken van cijfers, in plaats van te wachten tot de een klaar is voordat de ander begint.

Om dit idee te testen, hebben de onderzoekers hun systeem geïntegreerd in een softwareframework genaamd Celerity, dat ontworpen is voor het draaien van complexe simulaties op GPU-clusters. Ze draaiden drie verschillende wetenschappelijke applicaties om te zien hoe goed de nieuwe scheduler presteerde vergeleken met de standaardversie. Eén applicatie simuleerde de zwaartekrachtwerking tussen miljarden deeltjes, een andere modelleerde hoe geluid door een kamer weerkaatst, en de derde volgde hoe golven door een medium bewegen. In elk geval maten ze hoe snel het programma draaide naarmate ze meer GPU's toevoegden, een metriek die bekend staat als sterke schaling (strong scaling). De resultaten lieten zien dat de nieuwe aanpak consequent beter presteerde dan het basisysteem, vooral naarmate het aantal processors groeide. Op een systeem met 128 GPU's liet de nieuwe scheduler de kamer-simulatieapplicatie meer dan twee keer zo snel draaien als de oude methode, terwijl de deeltjessimulatie ook een aanzienlijke snelheidstoename zag.

Een belangrijke innovatie in dit werk is een techniek genaamd scheduler lookahead, die een specifiek probleem met betrekking tot geheugengebruik oplost. In veel simulaties kan de hoeveelheid data die een programma moet opslaan van de ene stap naar de volgende veranderen. Zonder een manier om deze veranderingen te voorspellen, kan de software een klein blok geheugen alloceren, om er een moment later achter te komen dat het te klein is, waardoor het een groter blok moet alloceren en alle data moet kopiëren. Dit proces van herverdeling is traag en kan kostbare tijd verspillen. Het nieuwe systeem kijkt vooruit naar de komende taken om te zien of de geheugeneisen groeien. Als het een patroon detecteert waarbij de datagrootte zal toenemen, wacht het met het alloceren van het geheugen totdat het de uiteindelijke benodigde grootte weet, waardoor de kostbare stap van herverdeling volledig wordt vermeden. Dit is bijzonder effectief voor applicaties waarbij de data gestaag groeit, waardoor het systeem in één keer de juiste hoeveelheid geheugen kan alloceren.

De onderzoekers bouwden ook een systeemarchitectuur die het werk van het plannen scheidt van het werk van het uitvoeren. Ze creëerden een toegewijde thread, of een aparte uitvoeringlijn, die uitsluitend verantwoordelijk is voor het bouwen van deze gedetailleerde instructie-grafieken. Ondertussen handelen andere threads de werkelijke uitvoering van de instructies op de GPU's af. Deze scheiding zorgt ervoor dat het proces van het plannen van de volgende stappen nooit in de weg zit van de huidige stappen die worden uitgevoerd. De twee processen draaien naast elkaar en communiceren via een gestroomlijnde wachtrij die instructies van de planner naar de uitvoerder doorgeeft. Dit ontwerp minimaliseert de tijd die het systeem doorbrengt met wachten, waardoor de GPU's bezig blijven met nuttig werk in plaats van stil te staan terwijl de software uitzoekt wat het volgende moet doen.

De experimenten werden uitgevoerd op de Leonardo supercomputer in Italië, een machine met duizenden processors en snelle verbindingen. Het team gebruikte echte wetenschappelijke codes om te garanderen dat hun bevindingen stand zouden houden in praktische scenario's. Ze ontdekten dat hoewel de nieuwe methode de fundamentele grenzen van hoeveel data kan worden opgeslagen of hoe groot een probleem kan zijn niet veranderde, het de efficiëntie van hoe dat werk werd verdeeld aanzienlijk verbeterde. De verbeteringen waren het meest merkbaar in applicaties waar de patronen van data-toegang complex of veranderlijk waren, aangezien het systeem de tijd die besteed wordt aan communicatie en geheugenbeheer beter kon verbergen. Voor applicaties met zeer korte berekeningsstappen verminderde de nieuwe scheduler de overhead genoeg om het systeem zelfs met een groot aantal processors efficiënt te laten schalen.

Dit werk demonstreert dat de manier waarop software de interne logistiek van een supercomputer beheert, net zo belangrijk is als de ruwe kracht van de hardware zelf. Door het zware werk van de scheduling uit het kritieke pad te halen en in een parallel proces te plaatsen, hebben de onderzoekers aangetoond dat het mogelijk is om deze massieve machines op piek-efficiëntie te laten draaien. De instructie-grafiek benadering biedt een manier om de complexe web van afhankelijkheden die bestaan in moderne parallelle programma's te visualiseren en te beheren, waardoor wat ooit een flessenhals was, wordt veranderd in een gestroomlijnde pijplijn. Naarmate supercomputers in omvang en complexiteit blijven groeien, zullen technieken zoals deze essentieel zijn om ervoor te zorgen dat wetenschappers het meeste uit hun investeringen kunnen halen, waardoor zij problemen kunnen oplossen die voorheen te groot of te traag waren om aan te pakken.