Beschleunigung von Propagationsalgorithmen mittels Pfadkompression auf der GPU

BearbeiterIn:Andreas Lindsteding
Titel:Beschleunigung von Propagationsalgorithmen mittels Pfadkompression auf der GPU
Typ:
Betreuer:Blaß, T.; Veldema, R.; Philippsen, M.
Status:abgeschlossen am 22. April 2016
Vorausetzungen:
Thema:

Hintergrund
Am Lehrstuhl für Programmiersysteme (LS2) wird ein Framework zur allgemeinen, sprachunabhängigen Programmanalyse entwickelt.

Ziel ist es, Programmanalysen so zu beschleunigen, dass sie in Echtzeit den Programmcode analysieren und etwaige Fehler unmittelbar beim Tippen an den Entwickler zurückmelden. Dies schließt auch komplexe Analysen mit ein (z.B Alias Analyse, Escape Analyse, Heap Space Analyse, ...). Um diese Analysen zu beschleunigen, werden sie auf einen Propagationsalgorithmus abgebildet, der auf einer GPU (CUDA) ausgeführt wird.

Das LS2-Framework wird bereits erfolgreich eingesetzt, um in Programmen, die in einem vereinfachten Java-Dialekt bzw. einem eingeschränkten C-Dialekt (MISRA-C) entwickelt wurden, Fehler durch Analysen zu finden.

Thema
Ziel dieser Arbeit ist es, den Propagationsalgorithmus durch Pfadkompression zu beschleunigen. Der Propagationsalgorithmus arbeitet auf dem Kontrollflussgraphen (KFG) eines Programmes. Die Knoten enthalten jeweils die Anweisungen des Programms (minimale Grundblöcke). Die Kanten verweisen auf die nächst möglich auszuführende(n) Instruktion(en).

Für eine Analyse sind aber nicht alle Knoten eines KFG relevant. Knoten/Instruktionen, die keinen Einfluss auf eine Analyse haben, verlängern unnötigerweise die Laufzeit des Propagationsalgorithmus. Aufgabe wird es sein, diese Knoten zu identifizieren und zu verschmelzen, sodass der KFG so klein wie möglich wird.

Das Vorgehen soll an einem einfachen Beispiel für die Escape-Analyse gezeigt werden:

// Ohne Komprimierung:
1 x = new Z();
2 use(a);
3 use(b);
4 use(c);
5 return x;

// Mit Kompr.:
1 x = new Z();
2 compress{
3 skip: use(a);
4 skip: use(b);
5 skip: use(c);
6 }
6 tmp = x;

Die Zeilen 2-4 aus dem Beispiel ohne Komprimierung haben keinen Einfluss auf die Analyse. Trotzdem werden sie bei der Analyse berücksichtigt (jede Anweisung ist ein Knoten im KFG). Somit dauert es 5 Iterationen, bis die Analyse terminiert. Mit Pfadkompression werden diese Anweisungen in einem compress Block zusammengefasst. Die drei Instruktionen erscheinen jetzt nur noch als ein Knoten im KFG. Die Analyse terminiert jetzt nach 3 Iterationen. Bei größeren Programmen reduziert sich die Anzahl an benötigten Iterationen deutlicher.

Die Kompression des KFG soll parallel auf der Grafikkarte durchgeführt werden.

Für eine Bachelor-Arbeit genügt es, CUDA die Datenübertragung zwischen Host und GPU zu überlassen (CUDA 6).

Um dieses Thema als eine Master-Arbeit zu bearbeiten, müssen die folgenden Probleme zusätzlich bearbeitet werden:

  • Optimierte Datenübertragung von Host und GPU (explizite Kopiervorgänge).
  • Mehrere Programmanalysen sollen gleichzeitig auf der GPU laufen können. Um dies zu erlauben, muss der KFG kopiert (eine Kopie pro Analyse) und Analyse spezifisch komprimiert werden.

Meilensteine

  • Einarbeitung in CUDA + Inf2 Framework
  • Implementierung der Komprimierung anhand der Escape-Analyse (Master-Arbeit: auch Heap-Analyse)
  • Messungen
  • Ausarbeitung schreiben
watermark seal