Synchronisationsfreie Graphstruktur auf der GPU

BearbeiterIn:Daniel Wust
Titel:Synchronisationsfreie Graphstruktur auf der GPU
Typ:bachelor thesis
Betreuer:Blaß, T.; Veldema, R.; Philippsen, M.
Status:abgeschlossen am 6. November 2014
Vorausetzungen:
Thema:

Hintergrund:
Im Übersetzerbau muss man bei der Implementierung von Code-Analysen meist einen Mittelweg zwischen Genauigkeit und Laufzeitaufwand wählen. Je nach gewähltem Weg wird die Genauigkeit zulasten der Laufzeit erhöht oder umgekehrt. Besonders bei der Alias-Analyse ist dieses Problem eklatant. Je genauer das Programm analysiert werden soll, desto länger benötigt die Analyse. Eine Alias-Analyse wird benutzt, um herauszufinden, ob eine Speicherstelle auf unterschiedliche Wege adressiert wird. Zwei Zeiger in einem Programm sind Aliase, wenn sie dieselbe Speicherstelle adressieren. Bei der Analyse von Aliasen wird ein Graph (Heap-Graph) aufgebaut, der die jeweiligen Alias-Beziehungen darstellt. In diesen Heap-Graphen entsprechen Knoten jeweils Speicherstellen (bzw. Variablen/Objekten). Kanten beschreiben eine Alias-Beziehung zwischen zwei verbundenen Knoten. Eine genauere Kenntnis von Alias-Beziehungen ermöglicht aggresivere Optimierungen.

Thema:
Am Lehrstuhl wird gegenwärtig an einem parallelen Übersetzerwerkzeug (ErLaDeF) geforscht. Ziel ist unter anderen, beliebige Code-Analysen zu beschleunigen. Dabei soll die Genauigkeit von Analysen erhöht werden, ohne eine signifikante Erhöhung der Laufzeit herbeizuführen. Um dies zu leisten, greift das Framework auf die massive Parallelität von Grafikkarten zurück (Stichwort: GPGPU). Jede Analyse wird in eine für die Grafikkarte ausführbare Form transformiert.
Für das Framework wurde bereits eine Alias-Analyse implementiert. Die verwendete Struktur zum Darstellen des Heap-Graphen ist allerdings noch nicht optimal, da beim Einfügen von Kanten und Knoten Synchronisationsmechanismen benötigt werden und die Threads dadruch nur noch sequentiellen Zugriff auf die Graphstruktur haben.
Im Rahmen dieser Arbeit (BA/MA) soll eine (allgemeine) Graphstruktur entworfen und implementiert (CUDA) werden, die für eine Verwendung auf der GPU optimiert ist. Hierzu zählt besonders der Verzicht auf Mittel zur Synchronisation. Das Einfügen von neuen Knoten und Kanten soll die Parallelität eines Programmes nicht beschneiden. Die in dieser Arbeit erstellte Implementierung soll in die existierende Alias-Analyse integriert werden. Als API sollen beispielsweise die folgenden Methoden implementiert werden: addNode(Node), addEdge(Node, Node), removeEdge(Node, Node).

Meilensteine:

  • Einarbeitung in CUDA und das Übersetzerwerkzeug.
  • Entwurf einer Graph-Implementierung unter besonderer Berücksichtigung der Eigenschaften einer GPU.
  • Implementierung des Entwurfes in CUDA.
  • Evaluierung der Implementierung.
  • Zusammenschreiben.
watermark seal