Grafikprozessoren, kurz GPUs, sind längst nicht mehr nur für die Darstellung von Bildern und Videos zuständig. Ihre Fähigkeit, tausende von Kernen parallel zu nutzen, macht sie auch für die Beschleunigung von Berechnungen im Maschinenlernen, Simulationen oder komplexen Algorithmen äußerst attraktiv. Doch die wahre Herausforderung bei der Nutzung von GPUs liegt nicht nur in der bloßen Portierung eines bestehenden CPU-Programms, sondern in der effizienten Anpassung und Optimierung, um die Besonderheiten der GPU-Architektur gewinnbringend auszunutzen. Anhand eines außergewöhnlichen Projekts, das auf den ersten Blick wenig praktischen Nutzen bietet, lassen sich jedoch bedeutende Erkenntnisse gewinnen, wie Entwickler ihre Software besser für GPUs optimieren können. Dieses Vorhaben beschäftigt sich mit der Beschleunigung des Kartenspiels „Beggar My Neighbour“ und zeigt exemplarisch die Stolpersteine und Erfolgsmomente bei GPU-Optimierungen auf.
Das ursächliche Problem, das bearbeitet wurde, ist eine Suche nach der längsten möglichen Spielsequenz in „Beggar My Neighbour“. Das Kartenspiel ist dabei kirre einfach aufgebaut, basiert aber auf extrem vielen möglichen Spielverläufen, die rein parallel untersucht werden können. Bemerkenswert ist, dass die Anzahl potenziell einzigartiger Spieldeals astronomisch hoch ist und damit eine hervorragende Gelegenheit zur parallelen Berechnung bietet. Gleichzeitig ist der Algorithmus durch seine verzweigten Logiken und Zustandsübergänge komplex genug, um die Grenzen verschiedener Optimierungsstrategien auszutesten. Der Ausgangspunkt war ein C++-Programm auf der CPU, das bereits optimiert wurde, um mit mehreren Kernen und Threads sehr effizient viele Spielverläufe pro Sekunde zu simulieren.
Mit einem Spitzenwert von etwa 2,9 Millionen Spielverläufen pro Sekunde auf einem Laptop war dies jedoch nur die Basis für die weitere Optimierung. Mit der Portierung auf die GPU wurde schnell klar, dass eine einfache Übernahme des Codes keine unmittelbare Leistungssteigerung bewirkte. Im Gegenteil: Die Ausführung auf der GPU war im ersten Anlauf langsamer als die CPU-Version, was zunächst enttäuschend wirkte. Doch das ist auch nachvollziehbar, denn GPUs und CPUs unterscheiden sich grundlegend in Aufbau und Zielsetzung. CPUs sind für schnelles Abarbeiten komplexer verzweigter Logik mit viel Cache und ausgefeiltem Branch-Prediction-Mechanismus ausgelegt, während GPUs viele einfache Kerne bereitstellen, die effizient parallel laufen, aber schlechter mit divergierenden Abläufen und umfangreicher verzweigter Logik zurechtkommen.
Hier setzt eine zentrale Erkenntnis ein: Um GPUs sinnvoll zu nutzen, müssen Entscheidungslogiken und Programmfluss so gestaltet werden, dass möglichst alle Threads synchron ähnliche Instruktionen ausführen. Branchenbegriffe wie Thread Divergenz beschreiben den Effekt, dass bei ungleichförmiger Steuerung viele Kerne warten müssen, was die Parallelität stark einschränkt und Leistung kostet. Eine erste Optimierung bestand darin, die Block- und Threadgröße auf mindestens 32 Threads pro Block einzustellen. So wird eine Hardwareeinheit namens Warp optimal ausgelastet. Danach wurde die innere Spiellogik umstrukturiert.
Anstatt verzweigte Bedingungen zu verwenden, wurde die gesamte Steuerung in eine Zustandsmaschine überführt, die anhand einer Lookup-Tabelle die nächsten Zustände und Aktionen bestimmt. Dadurch sollten alle Threads synchron denselben Programmfluss durchlaufen, wobei sich nur die Daten unterscheiden. Theoretisch verringert dies die Thread Divergenz und verbessert die Effizienz. Diese Umstellung brachte jedoch zunächst keine große Geschwindigkeitssteigerung. Im Gegenteil, die reine Umcodierung in eine Lookup-Table führte sogar zu Einbußen beim CPU und GPU.
Grund hierfür war, dass mehr Speicherzugriffe notwendig wurden und zusätzliche Datenstrukturen gehandhabt werden mussten. Allerdings zeigte sich eine leichte Verbesserung beim Parallelverhalten, was ein Schritt in die richtige Richtung war. Eine weitere wichtige Erkenntnis aus den Messungen, die mit dem Nvidia Nsight Compute Tool durchgeführt wurden, war, dass Funktionen, die unterschiedlich lang ausgeführt wurden und unterschiedliche Wartezeiten hatten, ebenfalls zu Divergenz führten, da Threads innerhalb eines Warps unterschiedlich schnell fertig wurden. Um dem entgegenzuwirken, wurde die Logik so modifiziert, dass Spielende und Neustart eines Spiels innerhalb einer einzigen Schleife behandelt werden konnten. Dadurch durchliefen fast alle Threads synchron mehrere Spielrunden, was die Divergenz nachhaltig reduzierte.
Trotz dieser Fortschritte stand noch immer eine große Herausforderung an: die Speicherzugriffe. Der Code lief auf der GPU noch immer vielfach langsamer, als es die mögliche Speicherbandbreite und Rechenleistung theoretisch erlauben sollte. Die Analyse enthüllte, dass die vielgenutzten globalen Speicherzugriffe den größten Engpass bildeten. Moderne GPUs haben verschiedene Arten von Speicher mit unterschiedlichen Zugriffsgeschwindigkeiten. Insbesondere Shared Memory, der in etwa auf Cache-Niveau arbeitet, kann wesentlich schneller bedient werden als der große globale Speicher.
Also wurde der Ansatz verfolgt, die Daten für den Backlog von Spielen, die gleichzeitig abgearbeitet werden, aus dem großen Hauptspeicher in den wesentlich kleineren, aber schnelleren Shared Memory pro Block zu verlagern. Trotz der begrenzten Größe von wenigen Kilobyte pro Block konnte so die Arbeit in überschaubare Abschnitte eingeteilt werden, die schnell und effizient bearbeitet wurden. Diese Umstellung führte zu einem dramatischen Performance-Sprung auf der GPU – von einigen Millionen auf rund 40 Millionen Spielverläufe pro Sekunde. Der letzte Schritt bestand darin, die Datentypen sparsamer zu gestalten. Ursprünglich wurden viele Zustände und Kartenwerte als 32-Bit-Integer repräsentiert, obwohl deutlich kleinere Datentypen ausreichend gewesen wären.
Durch die Verwendung von 8-Bit-Werten und bit-kompakten Strukturen konnte der Speicherverbrauch nochmals erheblich verringert werden, sodass mehr Daten in den schnellen Shared Memory passten und die Bandbreite den zunehmend kritischen Flaschenhals weniger stark belastete. Dadurch wurde die Leistung erneut übertroffen, so dass schließlich mehr als 100 Millionen Spielverläufe pro Sekunde erreicht wurden – eine Größenordnung, die den ursprünglichen CPU-Wert um über das 30-Fache übertrifft. Die Analyse mittels Nsight Compute zeigte abschließend zwar weiterhin, dass der Kernalgorithmus auf dem Speicherzugriff limitiert ist und keine 100-prozentige Auslastung der Recheneinheiten erreicht wird, allerdings sind weitere Verbesserungen nur durch noch tiefere Eingriffe in Algorithmus und Datenlayout zu erwarten. Das Fazit aus diesem fast „sinnlosen“ Experiment zeigt deutlich, dass einfache Portierungen von CPU-Code auf GPU oft nicht ausreichen, um die Vorteile der massiven Parallelität wirklich auszuschöpfen. Stattdessen erfordern GPUs eine bewusste Umgestaltung des Programmflusses und der Datenstrukturen mit Augenmerk auf Minimierung von Thread-Divergenz, optimaler Nutzung von Shared Memory und Reduktion von Speicherbelastung.
Darüber hinaus ist es essentiell, systematisch Analysewerkzeuge wie Nsight Compute einzusetzen, um Engpässe auf Schlüsselstellen im Code zu identifizieren und gezielt zu optimieren. Nur so können Entwickler realistisch die oft versprochenen Geschwindigkeitsgewinne auf modernen GPUs erzielen. Die Erkenntnisse aus der Optimierung eines naheliegenderweise trivialen Spiels sind daher keineswegs bedeutungslos. Sie sind ein beispielhaftes Lehrstück zur Genese von Hochleistungs-GPU-Algorithmen, das in verschiedensten Anwendungsfeldern nachhallt. Ob in der Künstlichen Intelligenz, wissenschaftlichen Simulationen oder anderen parallelen Berechnungen – die hier gewonnenen Einsichten helfen, durch bewusstes Programmieren das Maximum aus der GPU-Hardware herauszuholen.
Die Geduld, mit der schrittweise kleine Verbesserungen erarbeitet, gemessen und neu bewertet wurden, ist ebenfalls eine Entscheidungsempfehlung für Entwickler. Oft dauert es mehrere Iterationsrunden, bis vermeintlich einfache Änderungen deutliche Effekte haben. Die Nutzung von spezialisierten Messwerkzeugen, sorgfältige Analyse von Thread-Verhalten und ein tiefes Verständnis der zugrundeliegenden Hardware sind dabei unverzichtbar. Zusammenfassend illustriert dieses fast sinnlose GPU-Optimierungsexperiment eindrücklich die Komplexität und gleichzeitig das Potenzial von GPU-Programmierung. Für Entwickler heißt das: Ohne Anstrengungen in der Code-Strukturierung, Anpassung von Datentypen und Speicherlayout sowie präzise Analyse lassen sich die Stärken moderner Grafikhardware kaum effektiv nutzen.
Diese Lektionen bleiben wertvoll, weit über den originären Anwendungsfall hinaus.
