Geheimnisse des unmöglichen GPU-Computing

Unsere Erfahrung in der Verwendung eines Computerclusters von 480 AMD RX 480 GPUs zur Lösung mathematischer Probleme. Als Problem haben wir den Beweis des Theorems einem Artikel von Professor A. Chudnov entnommen " Zyklische Zerlegung von Sätzen, die Digraphen und zyklische Spielklassen mit garantierter Auszahlung trennen ." Die Aufgabe besteht darin, die Mindestanzahl von Teilnehmern an einer Koalition in Koalitionsspielen vom Typ Nim zu finden, was den Gewinn einer der Parteien garantiert.

CPU-Entwicklung

Der erste Prozessor, der wirklich Massenverteilung bekam, ist 8086 von Intel, der 1978 entwickelt wurde. Die Taktrate von 8086 betrug nur 8 MHz. Einige Jahre später erschienen die ersten Prozessoren, in denen sich 2, 4 und sogar 8 Kerne befanden. Jeder Kern erlaubte es, seinen Code unabhängig von den anderen auszuführen. Zum Vergleich: Der moderne Intel Core i9-7980XE-Prozessor arbeitet mit einer Frequenz von 2,6 GHz und enthält 18 Kerne. Wie Sie sehen, steht der Fortschritt nicht still!

GPU-Entwicklung

Gleichzeitig mit der Entwicklung von Zentralprozessoren wurden auch Grafikkarten entwickelt. Grundsätzlich sind ihre Eigenschaften für Computerspiele wichtig, bei denen neue Technologien besonders farbenfroh sind und sich das Rendern von 3D-Bildern allmählich der fotografischen Qualität nähert. Zu Beginn der Entwicklung von Computerspielen wurde die Berechnung des Bildes auf der CPU durchgeführt, aber der Erfindungsreichtum der 3D-Grafikentwickler wurde bald erreicht, die es schafften, selbst die offensichtlichen Dinge zu optimieren ( InvSqrt () ist ein gutes Beispiel). Daher tauchten Coprozessoren mit speziellen Anweisungen zur Durchführung von 3D-Berechnungen auf Grafikkarten auf. Mit der Zeit wuchs die Anzahl solcher Teams, was einerseits eine flexiblere und effizientere Arbeit mit dem Image ermöglichte und andererseits den Entwicklungsprozess komplizierte.

Seit 1996 wurden Grafikbeschleuniger S3 ViRGE, 3dfx Voodoo, Diamond Monster und andere produziert. 1999 veröffentlichte nVidia den GeForce 256-Prozessor und führte den Begriff GPU ein - einen Grafikprozessor. Es ist bereits universell, es kann sich mit geometrischen Berechnungen, Koordinatentransformation, Platzierung von Beleuchtungspunkten und Arbeiten mit Polygonen befassen. Der Unterschied zwischen der GPU und anderen Grafikchips bestand darin, dass es neben speziellen Befehlen eine Reihe von Standardbefehlen gab, mit denen Sie Ihren eigenen Rendering-Algorithmus implementieren konnten. Dies bot einen erheblichen Vorteil, da Spezialeffekte hinzugefügt werden konnten und nicht nur solche, die bereits in die Grafikkarte programmiert sind. Beginnend mit der GeForce 8000/9000 wurden Stream-Prozessoren in der GPU angezeigt - bereits vollwertige Computer. Ihre Anzahl lag je nach Modell zwischen 16 und 128. In der modernen Terminologie werden sie als einheitliche Shader-Einheiten oder einfach als Shader-Einheiten bezeichnet. Die heute hergestellten AMD Vega 64-GPUs enthalten 4096 Shader-Einheiten, und die Taktfrequenz kann 1536 MHz erreichen!

Was enthält eine GPU?

Die GPU-Architektur unterscheidet sich von der CPU durch eine große Anzahl von Kernen und einen minimalistischen Befehlssatz, der hauptsächlich auf Vektor-Computing abzielt. Auf Architekturebene wurden Probleme des Parallelbetriebs einer großen Anzahl von Kernen und des gleichzeitigen Zugriffs auf den Speicher behoben. Moderne GPUs enthalten 2 bis 4 Tausend Shader-Einheiten, die zu Recheneinheiten (Compute Unit) zusammengefasst werden. Beim parallelen Rechnen ist das Problem des gleichzeitigen Zugriffs auf den Speicher besonders akut. Wenn jeder der Stream-Prozessoren versucht, in die Speicherzelle zu schreiben, landen diese Befehle in der Sperre und müssen in die Warteschlange gestellt werden, was die Leistung erheblich verringert. Daher führen Stream-Prozessoren Anweisungen in kleinen Gruppen aus: Während eine Gruppe die Berechnungen durchführt, lädt die andere die Register usw. Sie können die Kerne auch zu Arbeitsgruppen mit gemeinsamem Speicher und internen Synchronisationsmechanismen kombinieren.

Ein weiteres wichtiges Merkmal der GPU ist das Vorhandensein von Vektorregistern und Vektor-ALUs, die Operationen gleichzeitig für mehrere Komponenten des Vektors ausführen können. Dies ist hauptsächlich für 3D-Grafiken erforderlich, aber da unsere Welt dreidimensional ist, hindert uns nichts daran, sie für viele physikalische Berechnungen zu verwenden. In Gegenwart von freien Vektor-ALUs können sie auch zur Berechnung skalarer Größen verwendet werden.

Sie sind so unterschiedlich, CPU und GPU

Für den vollen Betrieb des Computersystems sind beide Gerätetypen wichtig. Zum Beispiel führen wir ein Schritt-für-Schritt-Programm aus, einen bestimmten sequentiellen Algorithmus. Es gibt keine Möglichkeit, den fünften Schritt des Algorithmus auszuführen, daher werden die Daten dafür in Schritt vier berechnet. In diesem Fall ist es effizienter, eine CPU mit großem Cache und hoher Taktrate zu verwenden. Es gibt jedoch ganze Klassen von Aufgaben, die sich gut für die Parallelisierung eignen. In diesem Fall ist die Wirksamkeit der GPU offensichtlich. Das häufigste Beispiel ist die Berechnung der Pixel eines gerenderten Bildes. Die Vorgehensweise für jedes Pixel ist nahezu gleich, Daten zu 3D-Objekten und Texturen befinden sich im RAM der Grafikkarte, und jeder Stream-Prozessor kann unabhängig seinen eigenen Teil des Bildes berechnen.

Hier ist ein Beispiel für eine moderne Aufgabe - das Training eines neuronalen Netzwerks. Eine große Anzahl identischer Neuronen muss trainiert werden, dh um die Gewichtskoeffizienten jedes Neurons zu ändern. Nach solchen Änderungen ist es notwendig, Testsequenzen zum Training durch das neuronale Netzwerk zu leiten und Fehlervektoren zu erhalten. Solche Berechnungen sind für die GPU gut geeignet. Jeder Stream-Prozessor kann sich wie ein Neuron verhalten, und während der Berechnung muss die Lösung nicht sequentiell erstellt werden. Alle unsere Berechnungen werden gleichzeitig ausgeführt. Ein weiteres Beispiel ist die Berechnung aerodynamischer Strömungen. Es ist notwendig, das mögliche Verhalten der entworfenen Brücke unter dem Einfluss von Wind herauszufinden, ihre aerodynamische Stabilität zu simulieren, die optimalen Installationsorte für Verkleidungen zu finden, um den Luftstrom anzupassen oder den Widerstand gegen Windresonanz zu berechnen. Erinnern Sie sich an die berühmte „Tanzbrücke“ in Wolgograd? Ich denke, dass niemand in diesem Moment auf der Brücke sein möchte ...

Das Verhalten des Luftstroms an jedem Punkt kann durch dieselben mathematischen Gleichungen beschrieben werden und diese Gleichungen parallel auf einer großen Anzahl von Kernen lösen.

GPU in den Händen von Programmierern

Um Berechnungen auf der GPU durchzuführen, werden eine spezielle Sprache und ein Compiler verwendet. Es gibt verschiedene Frameworks für die Durchführung allgemeiner GPU-Berechnungen: OpenCL, CUDA, C ++ AMP, OpenACC. Die ersten beiden waren weit verbreitet, aber die Verwendung von CUDA ist nur durch die GPUs von nVidia begrenzt.

OpenCL wurde 2009 von Apple veröffentlicht. Später traten Intel, IBM, AMD, Google und nVidia der Khronos-Gruppe bei und kündigten ihre Unterstützung für den gemeinsamen Standard an. Seitdem erscheint alle anderthalb bis zwei Jahre eine neue Version des Standards, die jeweils immer ernsthaftere Verbesserungen bringt.

Bisher entspricht die Sprache OpenCL C ++ Version 2.2 dem C ++ 14-Standard, unterstützt die gleichzeitige Ausführung mehrerer Programme innerhalb des Geräts, die Interaktion zwischen ihnen über interne Warteschlangen und Pipelines und ermöglicht die flexible Verwaltung von Puffern und virtuellem Speicher.

Echte Aufgaben

Ein interessantes Problem aus der Spieltheorie, an dessen Lösung wir teilgenommen haben, ist der Beweis des Satzes aus einem Artikel von Professor A. Chudnov " Zyklische Zerlegung von Sätzen, die Digraphen und zyklische Spielklassen mit garantierter Auszahlung trennen ." Die Aufgabe besteht darin, die Mindestanzahl von Teilnehmern an einer Koalition in Koalitionsspielen vom Typ Nim zu finden, was den Gewinn einer der Parteien garantiert.

Aus mathematischer Sicht ist dies eine Suche nach einer unterstützenden zyklischen Sequenz. Wenn Sie die Sequenz in Form einer Liste von Nullen und Einsen darstellen, kann die Überprüfung auf Unterstützung durch logische bitweise Operationen implementiert werden. Aus programmtechnischer Sicht ist eine solche Sequenz ein langes Register, beispielsweise 256 Bit. Der zuverlässigste Weg, um dieses Problem zu lösen, besteht darin, alle Optionen außer den aus offensichtlichen Gründen unmöglichen zu sortieren.

Die Ziele der Problemlösung sind Probleme einer effektiven Signalverarbeitung (Erkennung, Synchronisation, Koordinatenmessung, Codierung usw.).

Die Komplexität der Lösung dieses Problems besteht darin, eine Vielzahl von Optionen zu sortieren. Wenn wir beispielsweise nach einer Lösung für n = 25 suchen, sind dies 25 Bits, und wenn n = 100, dann sind dies bereits 100 Bits. Wenn wir die Anzahl aller möglichen Kombinationen nehmen, dann ist es für n = 25 2 ^ 25 = 33 554 432 und für n = 100 sind es bereits 2 ^ 100 = 1 267 650 600 228 229 401 496 703 205 376 Kombinationen. Die Zunahme der Komplexität ist einfach kolossal!

Diese Aufgabe ist gut parallelisiert, was bedeutet, dass sie ideal für unseren GPU-Cluster ist.

Programmierer gegen Mathematik

Ursprünglich lösten Mathematiker dieses Problem in Visual Basic in Excel, sodass es ihnen gelang, primäre Lösungen zu erhalten, aber die geringe Leistung von Skriptsprachen ermöglichte es uns nicht, weit voranzukommen. Die Entscheidung für n = 80 dauerte anderthalb Monate ... Wir neigen unsere Köpfe vor diesen geduldigen Menschen.

In der ersten Phase haben wir den Task-Algorithmus in C implementiert und auf der CPU gestartet. Dabei stellte sich heraus, dass beim Arbeiten mit Bitsequenzen vieles optimiert werden kann.
Als nächstes haben wir den Suchbereich optimiert und Doppelarbeit vermieden. Auch eine Analyse des vom Compiler generierten Assembler-Codes und die Optimierung des Codes für die Compiler-Funktionen ergab ein gutes Ergebnis. All dies ermöglichte eine signifikante Steigerung der Berechnungsgeschwindigkeit.

Die nächste Stufe der Optimierung war die Profilerstellung. Die Messung der Ausführungszeit verschiedener Abschnitte des Codes zeigte, dass in einigen Zweigen des Algorithmus die Belastung des Speichers signifikant anstieg und eine übermäßige Verzweigung des Programms aufgedeckt wurde. Aufgrund dieses „kleinen“ Fehlers wurde fast ein Drittel der CPU-Leistung nicht verbraucht.

Ein sehr wichtiger Aspekt bei der Lösung solcher Probleme ist die Genauigkeit des Schreibens von Code. Niemand kennt die richtigen Antworten auf dieses Problem und dementsprechend gibt es keine Testvektoren. Es gibt nur den ersten Teil der Lösungspalette, die Mathematiker gefunden haben. Die Zuverlässigkeit neuer Lösungen kann nur durch die Genauigkeit des Schreibens von Code garantiert werden.

Die Phase der Vorbereitung des Programms für die Lösung auf der GPU ist also gekommen und der Code wurde so geändert, dass er in mehreren Threads funktioniert. Das Steuerprogramm ist nun damit beschäftigt, Aufgaben zwischen Threads zu verteilen. In einer Umgebung mit mehreren Threads hat sich die Berechnungsgeschwindigkeit um das Fünffache erhöht! Dies wurde durch den gleichzeitigen Betrieb von 4 Threads und die Kombination von Funktionen erreicht.

Zu diesem Zeitpunkt traf die Entscheidung die korrekten Berechnungen bis zu n = 80 in 10 Minuten, während diese Berechnungen in Excel anderthalb Monate dauerten! Kleiner Sieg!

GPU und OpenCL

Es wurde beschlossen, OpenCL Version 1.2 zu verwenden, um maximale Kompatibilität zwischen verschiedenen Plattformen zu gewährleisten. Das erste Debugging wurde auf der Intel-CPU und dann auf der Intel-GPU durchgeführt. Dann wechselten sie von AMD zur GPU.

Der OpenCL 1.2-Standard unterstützt ganzzahlige Variablen mit 64 Bit. Die 128-Bit-Dimension wird von AMD nur eingeschränkt unterstützt, wird jedoch in zwei 64-Bit-Zahlen kompiliert. Aus Kompatibilitätsgründen und um die Leistung zu optimieren, wurde beschlossen, eine 256-Bit-Nummer als Gruppe von 32-Bit-Nummern darzustellen, logische bitweise Operationen, die so schnell wie möglich auf der internen ALU-GPU ausgeführt werden.
Ein OpenCL-Programm enthält einen Kernel - eine Funktion, die den Einstiegspunkt eines Programms darstellt. Daten zur Verarbeitung werden von der CPU in den RAM der Grafikkarte heruntergeladen und in Form von Puffern - Zeigern auf ein Array von Eingabe- und Ausgabedaten - an den Kernel übertragen. Warum ein Array? Wir führen Hochleistungsrechnen durch, wir benötigen viele Aufgaben, die gleichzeitig ausgeführt werden. Der Kernel wird in mehreren Instanzen auf dem Gerät ausgeführt. Jeder Kern kennt seine Kennung und nimmt seine eigene Eingabe aus einem gemeinsam genutzten Puffer. Der Fall, wenn die einfachste Lösung die effektivste ist. OpenCL ist nicht nur eine Sprache, sondern auch ein umfassender Rahmen, in dem alle Details des wissenschaftlichen und Game-Computing gründlich durchdacht sind. Dies erleichtert dem Entwickler das Leben. Sie können beispielsweise viele Threads starten, der Task-Manager platziert sie auf dem Gerät selbst. Diejenigen Aufgaben, die nicht sofort ausgeführt wurden, werden in die Warteschlange gestellt und gestartet, sobald die Recheneinheiten frei werden. Jede Kernelinstanz verfügt über einen eigenen Speicherplatz im Ausgabepuffer, in dem die Antwort nach Abschluss der Arbeit platziert wird.

Die Hauptaufgabe des OpenCL-Managers besteht darin, die parallele Ausführung mehrerer Kernelinstanzen sicherzustellen. Hier wird die über Jahrzehnte gesammelte wissenschaftliche und praktische Erfahrung angewendet. Während einige Kerne Daten in Register laden, arbeitet ein anderer Teil zu diesem Zeitpunkt mit dem Speicher oder führt Berechnungen durch. Infolgedessen ist der GPU-Kern immer vollständig geladen.
Der OpenCL-Compiler leistet gute Optimierungsarbeit, aber für Entwickler ist es einfacher, die Leistung zu beeinflussen. Die GPU-Optimierung erfolgt in zwei Richtungen: Beschleunigung der Codeausführung und Möglichkeit der Parallelisierung. Wie gut der Code vom Compiler parallelisiert wird, hängt von mehreren Faktoren ab: der Anzahl der belegten Arbeitsregister (die sich im langsamsten GPU-Speicher befinden - global), der Größe des kompilierten Codes (Sie müssen in 32 KB Cache passen), der Anzahl der verwendeten Vektor- und Skalarregister.

ComBox A-480 GPU oder eine Million Kerne

Dies ist der interessanteste Teil des Projekts, als wir von Excel zu einem Computercluster mit 480 AMD RX 480-Grafikkarten gewechselt sind. Groß, schnell, effizient. Völlig bereit, die Aufgabe zu erfüllen und die Ergebnisse zu erzielen, die die Welt noch nie zuvor gesehen hat.

Ich möchte darauf hinweisen, dass wir in allen Phasen der Verbesserung und Optimierung des Codes von Anfang an mit der Suche nach einer Lösung begonnen und die Antworten der neuen Version mit den vorherigen verglichen haben. Dadurch konnten wir sicher sein, dass die Codeoptimierung und -verbesserungen keine Fehler in die Lösungen einbrachten. Hier müssen Sie verstehen, dass es am Ende des Lehrbuchs keine richtigen Antworten gibt und niemand auf der Welt sie kennt.
Der Start des Clusters bestätigte unsere Annahmen zur Geschwindigkeit der Lösungen: Die Suche nach Sequenzen für n> 100 dauerte etwa eine Stunde. Es war erstaunlich zu sehen, wie neue Lösungen auf dem ComBox A-480-Cluster in wenigen Minuten verfügbar waren, während es auf der CPU viele Stunden dauerte.

In nur zwei Stunden des Computerclusters haben wir alle Lösungen bis zu n = 127 erhalten. Eine Überprüfung der Lösungen ergab, dass die erhaltenen Antworten zuverlässig sind und den im Artikel angegebenen Theoremen von Professor A. Chudnov entsprechen

Geschwindigkeitsentwicklung

Wenn Sie sich den Leistungsgewinn im Verlauf der Problemlösung ansehen, sind die Ergebnisse ungefähr wie folgt:

• eineinhalb Monate bis n = 80 in Excel;
• eine Stunde bis n = 80 auf Core i5 mit einem optimierten C ++ - Programm;
• 10 Minuten bis n = 80 auf Core i5 mit Multithreading;
• 10 Minuten bis n = 100 auf einer AMD RX 480 GPU;
• 120 Minuten bis n = 127 auf der ComBox A-480.

Perspektiven und Zukunft

Viele Aufgaben an der Schnittstelle von Wissenschaft und Praxis stehen noch aus, um unser Leben besser zu machen. Der Markt für die Vermietung von Rechenleistung ist gerade im Entstehen begriffen, und der Bedarf an parallelem Rechnen wächst weiter.

Mögliche Anwendungen des Parallel Computing:

• Aufgaben der automatischen Steuerung von Fahrzeugen und Drohnen;
• Berechnungen der aerodynamischen und hydrodynamischen Eigenschaften;
• Spracherkennung und visuelle Bilder;
• neuronales Netzwerktraining;
• Aufgaben der Astronomie und Astronautik;
• statistische und Korrelationsanalyse von Daten;
• Faltung von Protein-Protein-Verbindungen;
• Früherkennung von Krankheiten mit AI.

Eine andere Richtung ist Cloud Computing auf der GPU. Zum Beispiel vermieten Giganten wie Amazon, IBM und Google ihre Rechenleistung an die GPU. Heute können wir mit Zuversicht sagen, dass die Zukunft des Hochleistungs-Parallel-Computing GPU-Clustern gehören wird.