Loop Parallelization in the Polyhedron Model - Just in Time (PolyJIT)
Final Report Abstract
Nach Kombination aller Arbeitspakete konnte PolyJIT den üblichen Anwendungsbereich polyedrischer Optimierungen deutlich erweitern. Das zur Verfügung stehende Laufzeitwissen ermöglicht auch die Optimierung von Schleifensatzen, die auf statische Methoden nicht ansprechen. Die praktische Implementierung hat zudem gezeigt, dass bei Programmen außerhalb der Domäne des Hochleistungsrechnens der Laufzeitoverhead der Just-In-Time Kompilation einen äußerst kritischen Faktor in der Performanz des Gesamtsystems darstellt. Die eingesetzten Heuristiken konnten den negativen Einfluß der Kompilation zur Laufzeit nicht in allen Fällen verhindern. Im folgenden fassen wir einige zentrale Ergebnisse aller abgeschlossenen Arbeitspakete zusammen. PJIT-EVAL. Mit BenchBuild wurde das Ziel dieses Pakets weit über den Plan hinaus erfüllt. Alle im Projekt erstellten Experimente stehen als wiederverwendbare Elemente innerhalb von Benchbuild zur Verfügung. Desweiteren lassen sich alle Experimente ohne Modifikation an der Experimentkonfiguration auf neuen Projekten wiederholen. Die Entwicklung und Nutzung von BenchBuild wird als unabhängiges Projekt, mit besonderem Fokus auf wiederverwendbare und reproduzierbare Experimente, fortgeführt. PJIT-COMP. Sämtliche Arbeitspakete wurden innerhalb des prototypischen JIT-Compilers PolyJIT implementiert. Dieser nutzt das weit verbreitete Compilerframework LLVM und profitiert damit automatisch von dessen Weiterentwicklung. Durch eine lose Kopplung lässt sich PolyJIT leicht an zukünftige Versionen von LLVM anpassen, um den Wartungsaufwand zu minimieren. PJIT-ANW. Die kontinuierliche Evaluierung bereits waärend der Entwicklung der Ersetzung von Parameterwerten zeigte, dass diese einfache Substitution zur Laufzeit die am häufigsten anwendbare Erweiterung gegenüber der statischen Variante des Polyedermodells war. Die Parameterwertersetzung konnte dem klassischen Polyedermodell neue Schleifensatze zuführen. Darüber hinaus konnten auch bereits statisch optimierbare Schleifensätze weiter vereinfacht werden, wodurch die Codegenerierung performantere Ergebnisse erzielen konnte. Eine laufzeitbasierte Erkennung von Aliasfreiheit bei Array-Speicherzugriffen wurde parallel zu PolyJIT auch in Polly entwickelt und integriert. Innerhalb Pollys ist dies Teil einer generischen Überprufung von zur Übersetzungszeit getroffenen Annahmen (bspw. Aliasfreiheit). Hierbei wird optimierter Code zur Übersetzungszeit unter den getroffenen Annahmen generiert und anschließend die Ausführung zur Laufzeit bedingt unter Einhaltung selbiger durchgeführt. In PolyJIT können die zu Grunde liegenden Arrays als Identifikator für generierte Versionen dienen. So können etwaige notwendige Laufzeittests nach einmaliger Prüfung für zukünftige Aufrufe entfernt werden. Selbiges trifft auch auf dynamischen Kontrollfluss, wie er in PJIT-ANW3 beschrieben wurde, zu. Bei der Evaluierung unter realen Bedingungen stellte sich heraus, dass der Anteil an Schleifensätzen, die durch diese Erweiterungen signifikant beschleunigt werden können, geringer ausfällt als durch Ersetzung von Parameterwerten. PJIT-METH. Der Einsatz von Profilinginformationen nimmt starken Einfluss auf die praktische Anwendbarkeit von PolyJIT. Unter realen Bedingungen kostet der Laufzeitoverhead bedingt durch die starke Beanspruchung der JIT-Kompilation häufig die erzeugten Geschwindigkeitsvorteile. Mit Hilfe des implementierten Profilings werden die Laufzeiten von sequenziellen und parallelen Schleifensätzen kontinuierlich ermittelt und als Eingabe für eine Kostenfunktion benutzt. Da die Laufzeit der parallelisierten Schleifensätze auch die Codegenerierung bzw. die Variantenselektion beinhaltet, können damit Schleifensätze, deren Laufzeit im Verhaltnis zur Codegenerierungszeit zu gering war, von der weiteren Bearbeitung durch PolyJIT ausgeschlossen werden. Dieses Paket vermindert das Aufkommen von stark negativen Laufzeitresultaten, wie sie noch im Zwischenbericht auftraten. Der Ersatz der Kostenfunktion durch ein geeignetes und umfassenderes Kostenmodell kann hier noch deutliche Fortschritte bringen. Die Hinzunahme von Laufzeiteigenschaften wie z.B. die verfügbare Größe des Prozessorcaches und des absoluten Speicherbedarfs eines Schleifensatzes führte auf den evaluierten Programmen nicht zu signifikanten Leistungsgewinnen im Vergleich zu generisch durch PolyJIT optimierten Programmen. Wir führen dies primär auf das verwendete bereits existierende Kostenmodell zuruck und sind der Ansicht, dass weitere Versuche in dieser Richtung deutliche Fortschritte erzielen können.
Publications
- On the Variety of Static Control Parts in Real-World Programs: from Affine via Multi-dimensional to Polynomial and Just-inTime. In Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques (IMPACT), Vienna, Austria, January 2014. 10 pages
Andreas Simbürger, Armin Größlinger
(See online at https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.640.2664) - BenchBuild: A Large-Scale Empirical-Research Toolkit. Technical Report MIP-1602, Fakultat für Informatik und Mathematik, Universität Passau, Juni 2016. 6 Seiten
Andreas Simburger, Florian Sattler, Armin Größlinger, and Christian Lengauer
- PolyJIT: Polyhedral Optimization Just in Time. International Journal of Parallel Programming (IJPP), Volume 47, 2019
Andreas Simburger, Sven Apel, Armin Größlinger, and Christian Lengauer
(See online at https://doi.org/10.1007/s10766-018-0597-3)
