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

Im Berichtszeitraum 2018 schlossen wir die im Vorjahr begonnen Arbeiten an einer Studie zur Effizienz von Graphstrukturen auf der GPU ab. Wir führten eine umfangreiche Analyse von 11 Graphstrukturen mit 10 (statischen) Graphalgorithmen, 19 Eingabegraphen und sechs unterschiedlichen Austauschformaten für Graphen durch. Die Messungen führten wir auf vier NVIDIA Graphikkarten mit unterschiedlichen Architekturen aus. Insgesamt analysierten wir 752 000 Datenpunkte. Daraus leiteten wir einen Entscheidungsbaum ab, der es einem Entwickler ermöglicht, die für seinen Algorithmus effizienteste Datenstruktur auszuwählen. Wir zeigten, dass die Geschwindigkeit von Graphalgorithmen durch Verwendung unseres Entscheidungsbaumes im Durchschnitt um bis zu 45% gesteigert werden kann. Diese Ergebnisse flossen in ParCAn ein.

Im Jahr 2018 haben wir folgende weitere Optimierungen an ParCAn vorgenommen.

• Nicht alle Instruktionen tragen etwas zum Analyseergebnis bei. Solche irrelevanten Instruktionen verzögern jedoch das Erreichen eines Fixpunkts, da Analyseinformationen trotzdem durch diese Instruktionen "geschleust" werden müssen. Wir implementierten daher einen parallelen Algorithmus auf der GPU, der solche Instruktionen aufspürt und entfernt. Dies reduziert die Länge des Pfades an dem entlang Prädikate propagiert werden müssen. Dies führt zum schnelleren Erreichen eines Fixpunktes.

• Weiterhin implementierten wir einen Algorithmus, der eine fairere Arbeitsaufteilung zwischen Threads eines Warps sicherstellt. Ohne diesen Algorithmus kann sich die Menge an zu verarbeitenden Analyseinformationen ungleichmäßig auf Threads verteilen, sodass Threads mit weniger Arbeit im Leerlauf sind, während andere Threads noch arbeiten müssen. Die Laufzeit wird aber durch die längste Ausführungszeit eines Threads bestimmt. Um dieses Ungleichgewicht zu vermeiden, unterstützen Threads, die ihre Analyseinformationen bereits verarbeitet haben, andere Threads. Wir nutzen hier Eigenschaften der GPU aus, um diese Arbeitsaufteilung ohne zeitaufwendige Synchronisationsmechanismen zu erreichen.

Um die Leistungsfähigkeit unseres Frameworks zu untersuchen, haben wir es in das LLVM-Übersetzersystem integriert. Wir wählten 4 LLVM-Analysen mit unterschiedlichen Eigenschaften aus und parallelisierten sie mit ParCAn. 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.