Automatische Code-Parallelisierung zur LaufzeitAktuell konzentrieren wir uns bei der automatisierten Parallelisierung
auf Laufzeit-Parallelisierung. Das zu parallelisierende Programm wird
während seiner Ausführung auf Schleifen untersucht, die parallel
ausführbar sind. Unser Ansatz besteht darin, laufzeitintensive
Schleifen zunächst in zwei Durchläufen auf ihre Parallelisierbarkeit
zu untersuchen. Die Analysedurchläufe werden parallel zueinander und
parallel zu einer sequenziellen Ausführung der Schleife ab der ersten
Iteration ausgeführt. Im ersten Analysedurchlauf werden die Adressen
aller Schreibzugriffe auf den Hauptspeicher in einer gemeinsam
genutzten Datenstruktur gespeichert. Zugriffe auf diese Datenstruktur
müssen nicht synchronisiert werden, wenn sichergestellt wird, dass bei
konkurrierenden Schreibzugriffen überhaupt ein Wert geschrieben
wird. Im zweiten Durchlauf wird für jeden Speicherzugriff (auch für
lesende!) überprüft, ob eine Datenabhängigkeit zu einem Schreibzugriff
besteht. Damit die sequenzielle Ausführung parallel zur Analyse
gestartet werden kann, muss diese die Speicherzugriffe, die sie
durchführt, protokollieren und überprüfen. Falls keine
Datenabhängigkeiten gefunden werden, wird die Schleife parallel
ausgeführt. Anderenfalls wird die sequentielle Ausführung ohne
weitere Instrumentisierung fortgeführt.
Im Jahr 2015 haben wir begonnen, das Verfahren in eine bestehende
Javascript-Engine einzubauen. Die Wahl ist auf Javascriptcore aus
Webkit gefallen, weil dort in der letzten Optimierungsstufe LLVM
verwendet wird. Damit ist es einfacher möglich, das Verfahren auch für
andere LLVM Sprachen zu verwenden, oder auf Analysen zurückzugreifen,
die für LLVM entwickelt wurden. Javascriptcore verwendet ein
mehrstufiges JIT Verfahren. In der letzten (am meisten optimierten)
Stufe wird LLVM Zwischencode erzeugt, der dann von dem LLVM-Compiler
mit den dort verfügbaren Optimierungen übersetzt wird. An diesen Punkt
bauen wir unsere Parallelisierung ein. Wenn diese Optimierungsstufe
erreicht ist, ist sichergestellt, dass der Code oft ausgeführt wird
und sich unser aufwändiges Verfahren lohnt. Wir setzen unser Verfahren
vor der Erzeugung des LLVM Code an, um Zugriff auf die
JIT-Protokolldaten zu haben, die uns bei der Entscheidung
unterstützen, welche Schleifen parallelisiert werden sollen.
Das Projekt stellt einen Beitrag des Lehrstuhls Informatik 2 zum IZ
ESI dar, siehe auch http://www.esi.uni-erlangen.de .
| Projektleitung: Prof. Dr. Michael Philippsen
Beteiligte: PD Dr. Ronald Veldema, Dipl.-Inf. Daniel Brinkers
Laufzeit: 1.1.2011 - 31.12.2015
|