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

Moderne Supercomputer sind nicht mehr nur schnellere Versionen der Maschinen von vor einigen Jahrzehnten; sie sind riesige Sammlungen aus tausenden spezialisierten Prozessoren, die zusammenarbeiten. Um das Beste aus diesen massiven Systemen herauszuholen, verlassen sich Wissenschaftler auf Software, die automatisch entscheiden kann, welcher Teil einer Berechnung an welchen Prozessor geht und wie die Daten zwischen ihnen bewegt werden. Dies ist eine schwierige Aufgabe, da die Software das Speichermanagement und die Kommunikation steuern muss, ohne die eigentliche Arbeit zu verlangsamen. Wenn das System zu viel Zeit damit verbringt, herauszufinden, wo es Daten platzieren oder wie es die Konsistenz wahren soll, sitzen die leistungsstarken Prozessoren untätig da und verschwenden Energie und Zeit. Die Herausforderung besteht darin, diese Entscheidungen schnell genug zu treffen, damit der Computer niemals innehält, um nachzudenken, und den Arbeitsfluss so reibungslos wie den Fluss des Wassers in einem Fluss hält.

Forscher der Universität Innsbruck haben einen neuen Weg entwickelt, um dieses Scheduling-Problem für Systeme mit vielen Grafikprozessoren, oder GPUs, zu bewältigen. Diese Chips sind darauf ausgelegt, massive Mengen an paralleler Arbeit zu bewältigen, aber die Koordination von Hunderten von ihnen erfordert einen anspruchsvollen Manager. Das Team führte eine Methode namens Instruction-Graph-Scheduling ein, die wie eine detaillierte, niedrigschwellige Karte jeder einzelnen Operation fungiert, die der Computer ausführen muss. Anstatt Entscheidungen spontan zu treffen, wenn jeder Schritt benötigt wird, erstellt das System einen vollständigen Plan, der Speicherzuweisung, Datentransfers und die eigentlichen Berechnungen umfasst. Dieser Plan wird generiert, während der Computer bereits an vorherigen Aufgaben arbeitet, was es dem Scheduler ermöglicht, vorauszuschauen und die nächsten Schritte vorzubereiten, ohne den aktuellen Fluss zu unterbrechen.

Der Kern dieses Ansatzes ist ein Wechsel in der Art und Weise, wie die Software die Arbeit betrachtet. Zuvor erstellte das System eine High-Level-Liste von Aufgaben und ermittelte erst dann die spezifischen Details, wie etwa das Kopieren von Speicher, wenn es Zeit für die Ausführung war. Dies führte oft zu Verzögerungen, da das System mitten in einer Berechnung anhalten musste, um Abhängigkeiten zu analysieren. Die neue Methode zerlegt jede Aufgabe in ihre kleinsten Komponenten, wie etwa die Zuweisung eines spezifischen Speicherblocks oder das Senden eines kleinen Datenstücks an einen benachbarten Prozessor. Durch die Anordnung dieser winzigen Schritte in einem einzigen, miteinander verbundenen Graphen kann das System genau sehen, welche Schritte gleichzeitig ablaufen können. Dies ermöglicht es dem Computer, Kommunikation mit Berechnung zu überlappen, was bedeutet, dass Daten zwischen den Prozessoren bewegt werden können, während die Chips mit Rechenarbeit beschäftigt sind, anstatt darauf zu warten, dass einer fertig ist, bevor der andere beginnt.

Um diese Idee zu testen, integrierten die Forscher ihr System in ein Software-Framework namens Celerity, das darauf ausgelegt ist, komplexe Simulationen auf GPU-Clustern auszuführen. Sie ließen drei verschiedene wissenschaftliche Anwendungen laufen, um zu sehen, wie gut der neue Scheduler im Vergleich zur Standardversion abschnitt. Eine Anwendung simulierte die Gravitationskraft zwischen Milliarden von Teilchen, eine andere modellierte, wie Schall in einem Raum reflektiert wird, und die dritte verfolgte, wie Wellen durch ein Medium wandern. In jedem Fall maßen sie, wie viel schneller das Programm lief, wenn sie mehr GPUs hinzufügten – eine Metrik, die als Strong Scaling bezeichnet wird. Die Ergebnisse zeigten, dass der neue Ansatz konsequent besser abschnitt als das Basissystem, insbesondere wenn die Anzahl der Prozessoren groß wurde. Auf einem System mit 128 GPUs ermöglichte der neue Scheduler der Raum-Simulationsanwendung, mehr als doppelt so schnell zu laufen wie die alte Methode, während die Teilchensimulation ebenfalls eine signifikante Geschwindigkeitssteigerung verzeichnete.

Eine zentrale Innovation dieser Arbeit ist eine Technik namens Scheduler Lookahead, die ein spezifisches Problem im Zusammenhang mit der Speichernutzung löst. In vielen Simulationen kann sich die Menge der Daten, die ein Programm speichern muss, von einem Schritt zum nächsten ändern. Oh mir einer Möglichkeit, diese Änderungen vorherzusagen, könnte die Software einen kleinen Speicherblock zuweisen, nur um kurz darauf festzustellen, dass er zu klein ist, was sie dazu zwingt, einen größeren zuweisen und alle Daten umzukopieren. Dieser Resizing-Prozess ist langsam und kann wertvolle Zeit verschwenden. Das neue System blickt voraus auf die anstehenden Aufgaben, um zu sehen, ob sich die Speicheranforderungen erhöhen. Wenn es ein Muster erkennt, bei dem die Datengröße zunehmen wird, wartet es mit der Speicherzuweisung, bis es die endgültige Größe kennt, und vermeidet so den kostspieligen Resizing-Schritt vollständig. Dies ist besonders effektiv für Anwendungen, bei denen die Daten stetig wachsen, da das System in der Lage ist, die korrekte Menge an Speicher in einem einzigen Schritt zuzuweisen.

Die Forscher entwickelten auch eine Systemarchitektur, die die Arbeit der Planung von der Arbeit des Ausführens trennt. Sie erstellten einen dedizierten Thread, oder eine separate Ausführungslinie, die ausschließlich dafür verantwortlich ist, diese detaillierten Instruktions-Graphen aufzubauen. Währenddessen übernehmen andere Threads die eigentliche Ausführung der Instruktionen auf den GPUs. Diese Trennung stellt sicher, dass der Prozess der Planung der nächsten Schritte niemals den Weg der aktuell ausgeführten Schritte blockiert. Die beiden Prozesse laufen nebeneinander her und kommunizieren über eine optimierte Warteschlange, die Instruktionen vom Planer an den Ausführer weitergibt. Dieses Design minimiert die Zeit, die das System mit Warten verbringt, und stellt sicher, dass die GPUs mit nützlicher Arbeit beschäftigt bleiben, anstatt untätig dazusitzen, während die Software überlegt, was als Nächstes zu tun ist.

Die Experimente wurden auf dem Leonardo-Supercomputer in Italien durchgeführt, einer Maschine mit tausenden Prozessoren und Hochgeschwindigkeitsverbindungen. Das Team nutzte reale wissenschaftliche Codes, um sicherzustellen, dass ihre Ergebnisse in praktischen Szenarien Bestand haben. Sie fanden heraus, dass die neue Methode zwar nicht die fundamentalen Grenzen dessen veränderte, wie viele Daten gespeichert werden können oder wie groß ein Problem sein kann, sie aber die Effizienz der Verteilung dieser Arbeit erheblich verbesserte. Die Verbesserungen waren am deutlichsten bei Anwendungen, bei denen die Datenzugriffsmuster komplex oder veränderlich waren, da das System die Zeit, die für Kommunikation und Speicherverwaltung aufgewendet werden muss, besser verbergen konnte. Für Anwendungen mit sehr kurzen Berechnungsschritten reduzierte der neue Scheduler den Overhead so weit, dass das System selbst mit einer großen Anzahl von Prozessoren effizient skalieren konnte.

Diese Arbeit zeigt, dass die Art und Weise, wie Software die interne Logistik eines Supercomputers verwaltet, genauso wichtig ist wie die reine Leistung der Hardware selbst. Indem die Forscher die schwere Last des Schedulings aus dem kritischen Pfad in einen parallelen Prozess verlagerten, haben sie gezeigt, dass es möglich ist, diese massiven Maschinen mit maximaler Effizienz am Laufen zu halten. Der Instruction-Graph-Ansatz bietet eine Möglichkeit, das komplexe Geflecht aus Abhängigkeiten, das in modernen parallelen Programmen existiert, zu visualisieren und zu verwalten, indem er einen, der einst ein Engpass war, in eine optimierte Pipeline verwandelt. Da Supercomputer in Größe und Komplexität weiter wachsen, werden Techniken wie diese unerlässlich sein, um sicherzustellen, dass Wissenschaftler das Beste aus ihren Investitionen herausholen und Probleme lösen können, die zuvor zu groß oder zu langsam zu bewältigen waren.