ParCAn

Parallele Code-Analyse auf einer GPU

Im Übersetzerbau (und auch an anderen Stellen) gibt es Analyseverfahren, bei denen Informationen solange durch einen Graphen propagiert und dabei verändert werden, bis sich das Analyseergebnis als Fixpunkt einstellt. In diesem Projekt entwickelten wir den Programmrahmen ParCAn, in dem verschiedene derartige Verfahren parallel und dadurch schneller auf der Graphikkarte ablaufen können.

Der Forschungsschwerpunkt des Jahres 2016 lag auf der Weiterentwicklung eines Synchronisationsmechanismus für GPUs. Bekannte Synchronisationsverfahren für die CPU (z. B. Spin-Lock) können nicht ohne weitere Anpassung auf der GPU verwendet werden, weil sie aufgrund spezieller Eigenschaften der GPU-Architektur zu Dead- bzw. Livelocks führen. Synchronisation wird jedoch (auch bei vorwiegend datenparallen Graphimplementierungen) benötigt, wenn sich Abhängigkeiten dynamisch ergeben. Der im Projekt entwickelte GPU-Synchronisationsmechanismus löst zwei wesentliche, auf GPUs nicht-triviale Probleme: Erstens verhindern wir Dead- bzw. Livelocks. Zweites erreichen wir einen maximalen Parallelitätsgrad, indem datenparallele Threads, die an nicht-kollidierenden Stellen der Datenstruktur arbeiten, nicht blockiert werden sondern die Datenstruktur zeitgleich verändern können. Beispiele sind Threads, die disjunkte Stellen eines Graphen modifizieren, ohne die strukturelle Integrität des Graphen zu beeinflussen. Bei unserem Ansatz hat der Programmierer die Möglichkeit, Regeln zu formulieren, unter welchen Umständen eine derartige parallele Ausführung eines kritischen Abschnitts erlaubt ist. Zur Laufzeit wird dann geprüft, welcher Grad an Parallelität ausgenutzt werden kann.

In den folgenden Arbeitsschritten wird der Synchronisationsmechnismus um einen Ablaufplaner erweitert, der kollidierende Zugriffe auf eine Datenstruktur so umsortiert, dass die SIMD-Ausführungsweise der GPU weniger Serialisierung bedingt, als ohne diese Umsortierung. Dadurch steigt der Paralellitätsgrad. Die zugrundeliegende Idee nutzt aus, dass GPUs Threads in einer Hierarchie von Organisationseinheiten verwalten. Stellt der oben beschriebene Synchronisationsmeachnismus einen kollidierenden Zugriff auf einer Hierarchieebene fest, wird auf der nächstkleineren Organisationseinheit erneut auf das Vorhandensein des Konflikts geprüft. Falls dieser dort nicht besteht, dann ist eine parallele Ausführung von wenigen Threads möglich, was immer noch besser ist als die größere Hierarchieebene sequentiell auszuführen. Ziel des Ablaufplaners ist es dann, die entdeckten Kollisionen so über die Organisationseinheiten zu verteilen, dass möglichst viele Threads parallel ausgeführt werden können. Da diese Ablaufplanung zur Laufzeit ausgeführt wird, muss sie effizient und selbst parallel sein sowie evtl. ausnutzen, dass neuere GPUs zur Laufzeit weitere Threads dynamisch starten können.

Graphen sind eine fundamentale Datenstruktur zur Repräsentation der Beziehungen zwischen Daten (z.B. soziale Netzwerke, Analyse der Verlinkung von Webseiten). Zu analysierende Graphen können Millionen/Milliarden von Knoten/Kanten enthalten. GPUs können Graphen mit mehreren 1000 Threads parallel verarbeiten. Graph-Analysen arbeiten nach dem Bulk Synchrones Parallel (BSP) Model. Eine Graph-Analyse zerfällt in drei, strikt getrennte, Phasen: Rechnen, Kommunikation und Synchronisation. Letztere beiden setzen Interaktion mit dem Host (CPU) voraus, welche sich negativ auf die Laufzeit auswirken. Unser GPU-basierter Übersetzer arbeitet ebenfalls nach dem BSP Model: Ein Entwickler modifiziert Code, dieser wird in einen (Kontrollfluss-) Graphen transformiert und auf der GPU analysiert. Jede Code-Veränderung löst diesen Zyklus aus. Der Graph muss also sehr schnell aufgebaut und auf die GPU transferiert werden.

Publikationen im Bereich der Graph-Analysen beschränken sich darauf, das Rechnen zu beschleunigen und auch nur dies zu vermessen. Die Ende-zu-Ende Zeit der Ausführung eines Programmes wird nicht berücksichtigt. Der Einfluss der Kommunikation und Synchronisation wird außer Acht gelassen, hat aber einen entscheidenden Einfluss auf die Laufzeit.

Für unseren GPU gestützten Übersetzer, betrachten wir alle drei Phasen des BSP-Models. 2017 veröffentlichten wir ein Papier, das die Synchronisation erheblich beschleunigt. Ferner fokussierten wir uns auf die Kommunikation. In diesem Kontext bedeutet Kommunikation das Kopieren des Graphen auf die GPU (und zurück). Während diese Zeit stark von der Datenstruktur des Graphen abhängt, beeinflusst sie auch die Dauer der Rechenphase. Weil bislang noch keine Untersuchung in der Literatur vorhanden ist, die die Datenstrukturen systematisch hinsichtlich ihrer Effizienz im Kontext von GPUs untersucht, implementierten wir einerseits mehrere Benchmarks, die unterschiedliche Eigenschaften von Graphen abfragen (Zugriff nur auf Vorgänger/Nachfolger, zufälliger Zugriff auf Knoten). Andererseits implementierten wir 8 Datenstrukturen zur Darstellung von Graphen auf der GPU. Die daraus resultierenden Kombinationen wurden mit, strukturell verschiedenen, Eingabegraphen vermessen. Die Ergebnisse sollen Entwickler bei der passenden Wahl der Datenstruktur für ihr GPU-Problem unterstützen.

Im Jahr 2018 schlossen wir die im Vorjahr begonnen Arbeiten an einer Studie zur Effizienz von Graphstrukturen auf der GPU ab und haben weitere Optimierungen an ParCAn vorgenommen. Um die Leistungsfähigkeit unseres Frameworks zu untersuchen, haben wir es in das LLVM-Übersetzersystem integriert. Umfangreiche Vergleichsmessungen zeigten, dass wir mit ParCAn den LLVM-Übersetzungsprozess um bis zu 40% beschleunigen konnten. Die zugehörige Publikation wurde auf einer Fachkonferenz (28th International Conference on Compiler Construction) als Bestes Papier
ausgezeichnet.
Im Jahr 2019 wurde ParCAn an das veränderte Ausführungsmodell neuer NVIDIA GPU-Architekturen angepasst. Mit Einführung der Volta-Architektur können Aktivitäten unabhängig Fortschritt erzielen. Jede Aktivität besitzt seinen eigenen Befehlszähler und Aufrufstapel. Vorher teilten sich Gruppen von Aktivitäten (Warps), den gleichen Befehlszähler und Aufrufstapel. Aktivitäten in einem Warp führten entweder die selbe Anweisung aus oder waren inaktiv (engl.: lock-step execution). Da jetzt Aktivitäten unabhängig voneinander Fortschritt erzielen können, besteht jetzt die Gefahr von Nebenläufigkeitsfehlern innerhalb von Warps.

Der Programmcode von ParCAn wurde nach Programmstellen durchsucht, die durch das geänderte Ausführungsmodell zu Nebenläufigkeitsfehlern führen könnten. Die Anwendung wurde entsprechend angepasst. Somit lässt sich ParCAn auch auf den neusten NVIDIA Architekturen korrekt ausführen.
Im Jahr 2020 wurde das Forschungsprojekt erfolgreich beendet. Es konnte gezeigt werden, dass durch die Parallelisierung der besonders kostenintensiven Datenflussanalysen die Übersetzungszeit in unserer Testumgebung um bis zu 31% reduziert werden kann.  Das Forschungsprojekt zeigt somit erfolgreich einen Weg hin zum parallelisierten Übersetzer auf, der den Anforderungen heutiger Softwareprojekte besser entspricht. Die Wichtigkeit dieses Forschungsthema wurde 2019 durch einen „Best Paper Award“ auf der renommierten Fachkonferenz „Compiler Construction“ unterstrichen, siehe CC-Literaturangabe.

Durch die Verwendung der GPU als Zielarchitektur wurden weitere forschungsrelevante Fragen beantwortet, die ebenfalls publiziert wurden.

Einige Analysen sammeln ihre Informationen in einer globalen Datenstruktur, die von allen Aktivitäten gleichzeitig modifiziert werden kann. Gerade auf der GPU mit ihrer Vielzahl an gleichzeitig laufenden Aktivitäten stellt dies hohe Anforderungen an eine effiziente Synchronisation beim Zugriff auf die gemeinsam genutzte Datenstruktur. So wurde im Rahmen des Forschungsprojektes ein effizientes Rahmenwerk zum Herstellen von gegenseitigen Ausschluss implementiert, siehe LNCS-Literaturangabe. Bisherige Ansätze führten unweigerlich zu Verklemmungen, dem Blockieren des Programms. Zudem wurde die Effizienz des Rahmenwerks durch die Verwendung einer Variante des Inspektions-Ausführungs-Paradigmas erhöht.

Eine andere Fragestellung befasste sich mit der Effizienz von Graphstrukturen auf GPUs. Im Kern implementiert ParCAn einen Graphtraversierungsalgorithmus. Das zu übersetzende Programm wird in einen Graphen umgewandelt, dem Kontrollflussgraphen (KFG), auf dem die Analysen ausgeführt werden. Durch die Vielzahl an parallelen Zugriffen stellt der KFG für die Leistungsfähigkeit von ParCAn eine kritische Datenstruktur dar. Aus diesem Grund wurde eine umfangreiche Studie durchgeführt, in der die Leistung von Graph-Datenstrukturen verglichen wurden. Die Ergebnisse wurden genutzt, um für ParCAn die bestmögliche Datenstruktur zur Repräsentation des KFG zu verwenden. Aus den Messdaten wurden allgemeine Kriterien zur Effizient einer Datenstruktur abgeleitet. Diese Kriterien - dargestellt als Entscheidungsbaum - ermöglichen es Entwicklern auch außerhalb des ParCAn-Kontextes, für ihre statischen Graphalgorithmen die am besten geeigneten Datenstrukturen zu wählen. Die Ergebnisse der Studie wurden auf dem GPGPU-Workshop vorgestellt, siehe Literaturangaben.

Publikationen