Internally funded project
Acronym: AutoParR
Start date : 01.01.2011
End date : 30.04.2016
Aktuell 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 .