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.
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
- Blaß T., Philippsen M.:
Which Graph Representation to Select for Static Graph-Algorithms on a CUDA-capable GPU
12th Workshop on General Purpose Processing Using GPUs (Providence, RI, 13.04.2019 - 13.04.2019)
In: ACM (Hrsg.): Proceedings of the 12th Workshop on General Purpose Processing Using GPUs, New York, NY, USA: 2019
DOI: 10.1145/3300053.3319416
URL: http://ieeetcca.org/2018/12/16/12th-workshop-on-general-purpose-processing-using-gpu-gpgpu-2019-asplos-2019/
BibTeX: Download - Blaß T., Philippsen M.:
GPU-Accelerated Fixpoint Algorithms for Faster Compiler Analyses (Best Paper Award)
28th International Conference on Compiler Construction (Washington, D.C., 16.02.2019 - 17.02.2019)
In: ACM (Hrsg.): Proceedings of the 28th International Conference on Compiler Construction, New York, NY, USA: 2019
DOI: 10.1145/3302516.3307352
URL: http://www2.informatik.uni-erlangen.de/publication/download/cc19_parcan_blass.pdf
BibTeX: Download - Blaß T., Philippsen M., Veldema R.:
Efficient Inspected Critical Sections in Data-Parallel GPU Codes
30th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2017) (College Station, TX, 11.10.2017 - 13.10.2017)
In: Rauchwerger, Lawrence (Hrsg.): Proceedings of the 30th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2017), Cham: 2019
DOI: 10.1007/978-3-030-35225-7_15
URL: https://www2.cs.fau.de/publication/download/lcpc2017_blass.pdf
BibTeX: Download