Blaß T (2022)
Publication Language: German
Publication Type: Thesis
Publication year: 2022
Publisher: FAU University Press
City/Town: Erlangen
Pages Range: xix, 324 Seiten
ISBN: 978-3-96147-494-3
DOI: 10.25593/978-3-96147-494-3
Eine Datenflussanalyse (DFA) analysiert, wie Daten innerhalb eines Eingabeprogramms weitergegeben werden und welche Abhängigkeiten daraus resultieren. Diese Informationen werden von nachfolgenden Optimierungen zur Steigerung der Effizienz des Eingabeprogramms verwendet. Je präziser die ermittelten Informationen sind, desto weitreichender und aggressiver können Optimierungen das Eingabeprogramm verändern. Der Grad an gewünschter Präzision der Analyseergebnisse wirkt sich auf die Laufzeit der Analyse aus. Zudem werden typischerweise mehrere Analysen während des Übersetzungsprozesses ausgeführt. DFA hat daher den größten Anteil an der Laufzeit von Übersetzern.
Traditionelle DFA arbeitet iterativ auf dem Kontrollflussgraph (KFG). Das Datenflusswissen (DFW) wird sequentiell für jeden Knoten des KFG berechnet und entlang der Kanten propagiert. Eine DFA terminiert, wenn sich das DFW nicht mehr ändert (Fixpunktalgorithmus). Anstatt das DFW - wie bisher üblich - sequentiell zu berechnen, präsentiert diese Arbeit einen neuen Ansatz, der die Berechnungen parallel ausführt. Dies verkürzt die Laufzeit einer Analyse erheblich, da ein Fixpunkt schneller gefunden wird als mit dem traditionellen Ansatz. Hinzu kommt, dass während des Übersetzungsvorgangs Analysen mehrfach ausgeführt werden. Somit reduziert sich die Laufzeit des Übersetzungsvorgangs insgesamt. Aufgrund der Größe von KFGn (bis zu mehreren Millionen Knoten) ist eine große Anzahl an Aktivitäten (engl.: Threads) erforderlich, um möglichst viele Berechnungen parallel auszuführen. Desktop-Prozessoren (engl.: Central Processor Unit, CPU) bieten nur wenige Aktivitäten, was die Skalierbarkeit erheblich einschränkt. Für den beschriebenen Anwendungsfall (datenparallel, große Anzahl an Aktivitäten) bieten sich Graphikkarten (engl.: Graphic Processor Unit, GPU) als Zielarchitektur an.
Mit GPUs enthält jeder Standardrechner eine massive parallele Recheneinheit. Die GPU-Architektur ist auf einen hohen Instruktionsdurchsatz optimiert und eignet sich daher besonders für die Ausführung datenparalleler Algorithmen. Diese Klasse von Algorithmen wendet die gleiche Anweisung auf unterschiedliche Datenelemente gleichartiger Daten an. Im Gegensatz zu CPUs erlauben GPUs die Ausführung von mehreren tausend Aktivitäten parallel zueinander, und noch viel mehr (hunderttausende) können vorgehalten und effizient eingeplant werden. Durch die hohe Verfügbarkeit von GPUs ist der vorgestellte Ansatz auf Standardrechnern anwendbar.
Im Rahmen der Umsetzung haben sich weitere Fragestellungen mit aktuellem Forschungsbedarf im GPU-Umfeld ergeben.
Einige Analysen (z.B. Alias-Analyse) speichern DFW in einer globalen Datenstruktur. Versuchen Aktivitäten, die gemeinsame Datenstruktur gleichzeitig an derselben Stelle zu verändern, korrumpiert dies die Datenstruktur. Für CPUs existieren eine Vielzahl an Synchronisationsmechanismen, die den nebenläufigen Zugriff ermöglichen. Keiner dieser Mechanismen funktioniert zuverlässig auf der GPU. Diese Arbeit präsentiert einen Ansatz, der globale Synchronisation ermöglicht, dabei aber den Grad an Parallelität so wenig wie möglich einschränkt. Im Gegensatz zu bereits existierenden Lösungen ist der hier präsentierte Ansatz schnell und frei von Verklemmungen (engl.: Deadlock).
Es existiert bereits eine Vielzahl von Graph-Datenstrukturen zur Speicherung des KFG, bisher indes noch keine Untersuchung, welche der unterschiedlichen Datenstrukturen sich am besten für ein bestimmtes statisches Graph-Problem eignet. Eine hier vorgenommene umfangreiche Studie, basierend auf 31,3 Millionen Messwerten, füllt diese Lücke. Aus der Analyse der Messwerte resultiert ein Entscheidungsbaum, der als Entscheidungshilfe dienen kann, die für ein Problem effizienteste Datenstruktur zu finden. Anhand der Ergebnisse wurde die Datenstruktur zur Speicherung des KFG ausgewählt.
Das unter Berücksichtigung der beiden vorgenannten Punkte und weiterer GPU-spezifischer Optimierungen entstandene Rahmenwerk zur parallelen Programmanalyse reduziert die Laufzeit des Übersetzungsvorgangs des hochoptimierten LLVM-Übersetzerrahmenwerks um bis zu 31,3%.
APA:
Blaß, T. (2022). Ein datenparalleler Ansatz zur Beschleunigung von Datenflussanalysen mittels GPU (Dissertation).
MLA:
Blaß, Thorsten. Ein datenparalleler Ansatz zur Beschleunigung von Datenflussanalysen mittels GPU. Dissertation, Erlangen: FAU University Press, 2022.
BibTeX: Download