Thorsten Blaß

Im Übersetzerbau (und auch an anderen Stellen) gibt es Analyseverfahren, bei denen Informationen solange durch einen Graphen propagiert und dabei verändert werden, bis sich das Analyseergebnis als Fixpunkt einstellt. In diesem Projekt entwickelten wir den Programmrahmen ParCAn, in dem verschiedene derartige Verfahren parallel und dadurch schneller auf der Graphikkarte ablaufen können.

Der Forschungsschwerpunkt des Jahres 2016 lag auf der Weiterentwicklung eines Synchronisationsmechanismus für GPUs. Bekannte Synchronisationsverfahren für die CPU (z. B. Spin-Lock) können nicht ohne weitere Anpassung auf der GPU verwendet werden, weil sie aufgrund spezieller Eigenschaften der GPU-Architektur zu Dead- bzw. Livelocks führen. Synchronisation wird jedoch (auch bei vorwiegend datenparallen Graphimplementierungen) benötigt, wenn sich Abhängigkeiten dynamisch ergeben. Der im Projekt entwickelte GPU-Synchronisationsmechanismus löst zwei wesentliche, auf GPUs nicht-triviale Probleme: Erstens verhindern wir Dead- bzw. Livelocks. Zweites erreichen wir einen maximalen Parallelitätsgrad, indem datenparallele Threads, die an nicht-kollidierenden Stellen der Datenstruktur arbeiten, nicht blockiert werden sondern die Datenstruktur zeitgleich verändern können. Beispiele sind Threads, die disjunkte Stellen eines Graphen modifizieren, ohne die strukturelle Integrität des Graphen zu beeinflussen. Bei unserem Ansatz hat der Programmierer die Möglichkeit, Regeln zu formulieren, unter welchen Umständen eine derartige parallele Ausführung eines kritischen Abschnitts erlaubt ist. Zur Laufzeit wird dann geprüft, welcher Grad an Parallelität ausgenutzt werden kann.

In den folgenden Arbeitsschritten wird der Synchronisationsmechnismus um einen Ablaufplaner erweitert, der kollidierende Zugriffe auf eine Datenstruktur so umsortiert, dass die SIMD-Ausführungsweise der GPU weniger Serialisierung bedingt, als ohne diese Umsortierung. Dadurch steigt der Paralellitätsgrad. Die zugrundeliegende Idee nutzt aus, dass GPUs Threads in einer Hierarchie von Organisationseinheiten verwalten. Stellt der oben beschriebene Synchronisationsmeachnismus einen kollidierenden Zugriff auf einer Hierarchieebene fest, wird auf der nächstkleineren Organisationseinheit erneut auf das Vorhandensein des Konflikts geprüft. Falls dieser dort nicht besteht, dann ist eine parallele Ausführung von wenigen Threads möglich, was immer noch besser ist als die größere Hierarchieebene sequentiell auszuführen. Ziel des Ablaufplaners ist es dann, die entdeckten Kollisionen so über die Organisationseinheiten zu verteilen, dass möglichst viele Threads parallel ausgeführt werden können. Da diese Ablaufplanung zur Laufzeit ausgeführt wird, muss sie effizient und selbst parallel sein sowie evtl. ausnutzen, dass neuere GPUs zur Laufzeit weitere Threads dynamisch starten können.

Graphen sind eine fundamentale Datenstruktur zur Repräsentation der Beziehungen zwischen Daten (z.B. soziale Netzwerke, Analyse der Verlinkung von Webseiten). Zu analysierende Graphen können Millionen/Milliarden von Knoten/Kanten enthalten. GPUs können Graphen mit mehreren 1000 Threads parallel verarbeiten. Graph-Analysen arbeiten nach dem Bulk Synchrones Parallel (BSP) Model. Eine Graph-Analyse zerfällt in drei, strikt getrennte, Phasen: Rechnen, Kommunikation und Synchronisation. Letztere beiden setzen Interaktion mit dem Host (CPU) voraus, welche sich negativ auf die Laufzeit auswirken. Unser GPU-basierter Übersetzer arbeitet ebenfalls nach dem BSP Model: Ein Entwickler modifiziert Code, dieser wird in einen (Kontrollfluss-) Graphen transformiert und auf der GPU analysiert. Jede Code-Veränderung löst diesen Zyklus aus. Der Graph muss also sehr schnell aufgebaut und auf die GPU transferiert werden.

Publikationen im Bereich der Graph-Analysen beschränken sich darauf, das Rechnen zu beschleunigen und auch nur dies zu vermessen. Die Ende-zu-Ende Zeit der Ausführung eines Programmes wird nicht berücksichtigt. Der Einfluss der Kommunikation und Synchronisation wird außer Acht gelassen, hat aber einen entscheidenden Einfluss auf die Laufzeit.

Für unseren GPU gestützten Übersetzer, betrachten wir alle drei Phasen des BSP-Models. 2017 veröffentlichten wir ein Papier, das die Synchronisation erheblich beschleunigt. Ferner fokussierten wir uns auf die Kommunikation. In diesem Kontext bedeutet Kommunikation das Kopieren des Graphen auf die GPU (und zurück). Während diese Zeit stark von der Datenstruktur des Graphen abhängt, beeinflusst sie auch die Dauer der Rechenphase. Weil bislang noch keine Untersuchung in der Literatur vorhanden ist, die die Datenstrukturen systematisch hinsichtlich ihrer Effizienz im Kontext von GPUs untersucht, implementierten wir einerseits mehrere Benchmarks, die unterschiedliche Eigenschaften von Graphen abfragen (Zugriff nur auf Vorgänger/Nachfolger, zufälliger Zugriff auf Knoten). Andererseits implementierten wir 8 Datenstrukturen zur Darstellung von Graphen auf der GPU. Die daraus resultierenden Kombinationen wurden mit, strukturell verschiedenen, Eingabegraphen vermessen. Die Ergebnisse sollen Entwickler bei der passenden Wahl der Datenstruktur für ihr GPU-Problem unterstützen.

Im Jahr 2018 schlossen wir die im Vorjahr begonnen Arbeiten an einer Studie zur Effizienz von Graphstrukturen auf der GPU ab und haben weitere Optimierungen an ParCAn vorgenommen. Um die Leistungsfähigkeit unseres Frameworks zu untersuchen, haben wir es in das LLVM-Übersetzersystem integriert. Umfangreiche Vergleichsmessungen zeigten, dass wir mit ParCAn den LLVM-Übersetzungsprozess um bis zu 40% beschleunigen konnten. Die zugehörige Publikation wurde auf einer Fachkonferenz (28th International Conference on Compiler Construction) als Bestes Papier
ausgezeichnet.
Im Jahr 2019 wurde ParCAn an das veränderte Ausführungsmodell neuer NVIDIA GPU-Architekturen angepasst. Mit Einführung der Volta-Architektur können Aktivitäten unabhängig Fortschritt erzielen. Jede Aktivität besitzt seinen eigenen Befehlszähler und Aufrufstapel. Vorher teilten sich Gruppen von Aktivitäten (Warps), den gleichen Befehlszähler und Aufrufstapel. Aktivitäten in einem Warp führten entweder die selbe Anweisung aus oder waren inaktiv (engl.: lock-step execution). Da jetzt Aktivitäten unabhängig voneinander Fortschritt erzielen können, besteht jetzt die Gefahr von Nebenläufigkeitsfehlern innerhalb von Warps.

Der Programmcode von ParCAn wurde nach Programmstellen durchsucht, die durch das geänderte Ausführungsmodell zu Nebenläufigkeitsfehlern führen könnten. Die Anwendung wurde entsprechend angepasst. Somit lässt sich ParCAn auch auf den neusten NVIDIA Architekturen korrekt ausführen.
Im Jahr 2020 wurde das Forschungsprojekt erfolgreich beendet. Es konnte gezeigt werden, dass durch die Parallelisierung der besonders kostenintensiven Datenflussanalysen die Übersetzungszeit in unserer Testumgebung um bis zu 31% reduziert werden kann.  Das Forschungsprojekt zeigt somit erfolgreich einen Weg hin zum parallelisierten Übersetzer auf, der den Anforderungen heutiger Softwareprojekte besser entspricht. Die Wichtigkeit dieses Forschungsthema wurde 2019 durch einen „Best Paper Award“ auf der renommierten Fachkonferenz „Compiler Construction“ unterstrichen, siehe CC-Literaturangabe.

Durch die Verwendung der GPU als Zielarchitektur wurden weitere forschungsrelevante Fragen beantwortet, die ebenfalls publiziert wurden.

Einige Analysen sammeln ihre Informationen in einer globalen Datenstruktur, die von allen Aktivitäten gleichzeitig modifiziert werden kann. Gerade auf der GPU mit ihrer Vielzahl an gleichzeitig laufenden Aktivitäten stellt dies hohe Anforderungen an eine effiziente Synchronisation beim Zugriff auf die gemeinsam genutzte Datenstruktur. So wurde im Rahmen des Forschungsprojektes ein effizientes Rahmenwerk zum Herstellen von gegenseitigen Ausschluss implementiert, siehe LNCS-Literaturangabe. Bisherige Ansätze führten unweigerlich zu Verklemmungen, dem Blockieren des Programms. Zudem wurde die Effizienz des Rahmenwerks durch die Verwendung einer Variante des Inspektions-Ausführungs-Paradigmas erhöht.

Eine andere Fragestellung befasste sich mit der Effizienz von Graphstrukturen auf GPUs. Im Kern implementiert ParCAn einen Graphtraversierungsalgorithmus. Das zu übersetzende Programm wird in einen Graphen umgewandelt, dem Kontrollflussgraphen (KFG), auf dem die Analysen ausgeführt werden. Durch die Vielzahl an parallelen Zugriffen stellt der KFG für die Leistungsfähigkeit von ParCAn eine kritische Datenstruktur dar. Aus diesem Grund wurde eine umfangreiche Studie durchgeführt, in der die Leistung von Graph-Datenstrukturen verglichen wurden. Die Ergebnisse wurden genutzt, um für ParCAn die bestmögliche Datenstruktur zur Repräsentation des KFG zu verwenden. Aus den Messdaten wurden allgemeine Kriterien zur Effizient einer Datenstruktur abgeleitet. Diese Kriterien - dargestellt als Entscheidungsbaum - ermöglichen es Entwicklern auch außerhalb des ParCAn-Kontextes, für ihre statischen Graphalgorithmen die am besten geeigneten Datenstrukturen zu wählen. Die Ergebnisse der Studie wurden auf dem GPGPU-Workshop vorgestellt, siehe Literaturangaben.

ErLaDeF ist unsere Testumgebung für die Erforschung neuer Programmiersprachen und Compiler-Techniken. Unser Zielbereich ist die Infrastruktur, die nötig ist, um Programmieren von eingebetteten parallelen Systemen (insbesondere im Echtzeitbereich) zu vereinfachen.

Im Bereich der eingebetteten Systeme und der Echtzeit-Software gibt es feste Grenzen für den Verbrauch an Betriebsmitteln wie Hauptspeicher oder Rechenzeit. Ein typischer Steuerrechner z. B. darf für eine Regelungsaufgabe im Allgemeinen nicht beliebig viel Zeit verbrauchen, um eine Fehlfunktion des gesteuerten Systems zu verhindern.  Die Hardware-Entwicklung der letzten Jahre hat dazu geführt, dass vermehrt Mehrkern-Prozessoren in eingebetteten Systemen eingesetzt werden. Um die damit verbundene Leistungssteigerung auszunutzen, ist es daher nötig, die Steuerungs- und Systemsoftware, die auf diesen eingebetteten Systemen laufen soll, ebenfalls zu parallelisieren, ohne dabei die Anforderungen an Echtzeitfähigkeit und Resourcenverbrauch zu verletzen.

Wir erforschen verschiedene Strategien, um diese Parallelisierung von Software in den Griff zu bekommen: Vereinfachung der Fähigkeiten von Programmiersprachen, automatische Parallelisierung, Bibliotheken mit Entwurfsmustern für die parallele Programmierung, tiefgehende Analyse im Übersetzer, Model Checking und Beschleunigung von Übersetzeranalyse bis hin zur interaktiven Nutzung.

Parallelisierung von Programmen zur Laufzeit

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 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 lesende!) überprüft, ob eine Datenabhängigkeit zu einem Schreibzugriff besteht. Falls keine Datenabhängigkeiten gefunden werden, wird die Schleife parallel ausgeführt - anderenfalls sequentiell.

Im Jahr 2013 konnten wir die Analyse verfeinern, indem wir in der Analyse beachten, dass die Speicherzugriffe der sequenziellen Ausführung der ersten Schleifen vor den parallelen Ausführungen der restlichen Schleifen stattfindet. Dadurch ist in mehr schwierigen Fällen eine Parallelisierung möglich. Zusätzlich sorgt das dafür, dass falls eine Schleife nicht parallel ausgeführt werden kann, unsere Analyse nur geringen Overhead verursacht.

Im Jahr 2014 konnten wir das Verfahren so verbessern, dass mit der Ausführung der ersten Schleifeniterationen zusammen mit der Analyse begonnen werden kann. Um das zu ermöglichen, musste die Analyse so verbessert werden, dass sie auch dann noch zuverlässig funktioniert, wenn sich die Daten (durch die gleichzeitige Ausführung) ändern. Durch diese Verbesserung konnten wir den Overhead für nicht-parallelisierbare Schleifen erheblich senken. Außerdem haben wir eine Programmiersprache entwickelt, die diejenigen Schleifen wie den beschriebenen zur Laufzeit parallelisiert, welche der Programmierer als Kandidaten zur Parallelisierung markiert hat. Eine Analyse prüft zuvor, ob die Schleifen illegale Konstrukte enthalten, mit denen der Parallelisierer noch nicht umgehen kann. Ansonsten wird Code erzeugt, der die Schleifen zur Laufzeit inspiziert und dann potenziell parallel ausführt.

Entwurfsmuster für parallele Programmierung

Eine Bibliothek von Entwurfsmustern der parallelen Programmierung erlaubt es einem Programmierer, bekannte Strategien auszuwählen und bei ihrer Implementierung auf erprobten, effizienten Code zur ̈uckzugreifen. Wir erforschen, welche Entwurfsmuster für parallele Programmierung und insbesondere Kommunikation in parallelen Programmen es überhaupt gibt, und wann diese angewendet werden können. Aus unserer bereits über 30 verschiedene Kommunikationsmuster enthaltenden Bibliothek versuchen wir in diesen Projekt für einen gegebenen Anwendungsfall automatisiert das zu seinen Anforderungen passende Entwurfsmuster zu selektieren. Im Jahr 2013 haben wir diese Bibliothek um NUMA-taugliche Kommunikationskanäle zur Verwendung auf Network-on-Chip Prozessoren erweitert.

Skriptsprache Pylon für eingebettete Systeme

Pylon ist eine statisch getypte Skriptsprache und kommt zwecks einfacher Erlernbarkeit mit wenigen Schlüsselwörtern aus. Ein Großteil der Komplexität (z.B. Typinferenz) ist in den Übersetzer verschoben. Der Programmierer muss sich keine Gedanken über Datentypen machen. Trotzdem bleibt das Programm statisch typisiert. Alleine aus dem Wert einer Zuweisung kann der Übersetzer den gerade benötigten Datentyp ableiten (Duck-Typing). Da die Sprache zudem implizit parallel ist, erfordert die Parallelisierung einer Anwendung kein Expertenwissen.
Beim Entwurf der Sprache wurde darauf geachtet, auf Sprachkonstrukte zu verzichten, welche die Analysierbarkeit erschweren (z.B. Zeiger, Vererbung, Polymorphie usw.), bzw. diese durch leichter analysierbare Alternativen zu ersetzen, die in früheren Projekten erarbeitet wurden. Der Fokus liegt darauf, den Anwender schon bei der Erstellung von robustem Programmcode bestmöglich zu unterstützen und Fehler statisch zu melden, die bei anderen Sprachen erst zu Laufzeit auftreten.

Interaktive Programmanalyse

Um sicherzustellen, dass Fehler im Programmdesign möglichst schon früh im Entwicklungsprozess gefunden werden, ist es nötig, Fehler möglichst schon während des Editierens des Programms zu finden. Dazu muss die verwendete Analyse so schnell sein, dass interaktiver Einsatz möglich ist. Wir arbeiten an zwei Ansätzen, dies zu verwirklichen.

Unser erster Ansatz basiert darauf, die Probleme der Programmanalyse durch verbesserte Algorithmen zu lösen. Ein wichtiges Hilfsmittel ist dabei eine verzögerte Analyse, bei der ein Programmteil erst dann analysiert wird, wenn die zugehörigen Analyseergebnisse benötigt werden. Die Analyse soll auch inkrementell ablaufen, d.h. bei kleinen Änderungen im Programm-Code soll nur möglichst wenig des Programms neu analysiert werden. Dazu zerlegen wir ein Programm rekursiv in Teile und berechnen anschließend, welche Auswirkungen und Effekte diese Teile während einer Ausführung des Programms haben; diese Auswirkungen und Effekte speichern wir zusammenfassend in symbolischen Beschreibungen, die dann dazu verwendet werden, um die Fehler beim Zusammenspiel der zugehörigen Teile des Programms zu finden, um die Auswirkungen von größeren Teilen des Programms zu beschreiben und um bei Änderung eines Bestandteils des Programms nicht das komplette Programm neu analysieren zu müssen, sondern stattdessen die symbolischen Beschreibungen aller unveränderten Programmteile wieder zu verwenden.
In 2013 lag der Schwerpunkt der Forschung auf der Erstellung von sowohl präzisen als auch kompakten Datenstrukturen zur Repräsentation der Effekte und Auswirkungen von Programmteilen, sowie der Erarbeitung von effizienten Algorithmen zur Erstellung und Nutzung dieser Datenstrukturen.

Im Jahr 2014 haben wir unser Werkzeug zur interaktiven Programmanalyse weiterentwickelt, um größere Code-Bestände zu analysieren und die Analyseergebnisse für spätere Verwendung aufzubewahren.  Dadurch wird auch Code präzise analysierbar, der (vorab analysierte) größere Bibliotheken benutzt.
Unser zweiter Ansatz basiert darauf, die Programmanalyse selbst zu parallelisieren und dadurch auf interaktive Geschwindigkeit zu beschleunigen.

Im Jahr 2013 haben wir begonnen, grundlegende Übersetzeranalysen in eine datenparallele Darstellung zu bringen. Dazu ist ein Rahmenprogramm für Prädikatspropagation in der Entwicklung. Diese datenparallelen Algorithmen sind dann einfach auf viele verschiedene Multi-Core Architekturen und GPUs portier

Objektorientierte Sprachen bieten im Allgemeinen die Möglichkeit, mittels Konstruktoren dynamisch Objekte zu erstellen. Der hierfür benötigte Speicher wird vom Laufzeitsystem angefordert. Im Unterschied zu Desktop-Systemen ist bei eingebetteten Systemen der Speicher noch sehr limitiert. Eine häufige Verwendung des new-Operators kann dazu führen, dass zur Laufzeit nicht genügend Speicher zu Verfügung steht und das Programm unerwartet beendet wird.

Im Jahr 2015 wurde daher eine Analyse entwickelt, um dieses Problem bereits zur Entwicklungszeit zu erkennen und an den Entwickler rückzumelden. Dazu ermittelt die Analyse die Lebensspanne einer Referenz auf ein Objekt. Existiert keine Referenz mehr auf dieses Objekt, kann das Objekt aus dem Speicher entfernt werden. Wir setzen hierzu das aus der automatischen Speicherbereinigung als Reference Counting (RC) bekannte Verfahren statisch und interaktiv während der Entwicklung eines Programmes ein, um Fehler zum frühestmöglichen Zeitpunkt zu erkennen. Wurde ein Objekt detektiert, das keine Referenzen mehr hat, muss der Programmierer es durch gezieltes Einfügen von Anweisungen löschen (z.B. delete) oder wiederverwenden. Damit kann der Speicherverbrauch einer Anwendung bereits zur Entwicklungszeit abgeschätzt werden. Die weitgehend sprachunabhängige Analyse basiert auf Pylon und dem im Vorjahr entwickelten parallelen Propagationsframework für Prädikate.

Das Projekt stellt einen Beitrag des Lehrstuhls Informatik 2 zum IZ ESI dar, siehe auch http://www.esi.uni-erlangen.de.

JaMP ist eine Implementierung des bekannten OpenMP Standards für Java. JaMP erlaubt es (unter anderem) Schleifen zu parallelisieren, ohne sich mit der low-level Thread-API von Java befassen zu müssen. Eine parallele Schleife hätte in JaMP folgende Form:
class Test {
 ...void foo() {
 ......//#omp parallel for
 ......for (int i=0;i .........a[i] = b[i] + c[i]
 ......}
 ...}
 }
 JaMP implementiert im Moment die Funktionalität von OpenMP 2.0 und Teile der Spezifikation 3.0 (z.B. die collapse clause). Die aktuelle JaMP Version erzeugt reinen Java Code und ist auf jeder JVM (die Java 1.5+ unterstützt) lauffähig. Die neueste Version kann sogar CUDA fähige Hardware verwenden um Schleifen auszuführen, wenn der Schleifenrumpf eine Transformation nach CUDA möglich macht. Ist die Transformation nicht möglich, wird nebenläufiger Code für gängige Multicore Prozessoren erzeugt. JaMP unterstütz auch die gleichzeitige Nutzung von mehreren Maschinen und Acceleratoren. Dieses wurde durch die Entwicklung von zwei Abstraktionsbibliotheken ermöglicht. Die untere Abstraktionsschicht bietet abstrakte Recheneinheiten, die von den eigentlichen Berechnungseinheiten wie CPUs und GPUs und ihrem Ort in einem Rechnerbündel abstrahieren. Eine weitere Abstraktionsschicht baut auf dieser Schicht auf und bietet Operationen um partitionierte und replizierte Arrays zu verwalten. Ein partitioniertes Array wird dabei automatisch über die abstrakten Berechnungseinheiten verteilt, wobei die Geschwindigkeiten der einzelnen Berechnungseinheiten berücksichtigt werden. Welcher abstrakte Arraytyp für ein Array in einem Java-Programm konkret eingesetzt wird, wird vom JaMP-übersetzer bestimmt, der erweitert wurde um ein Programm entsprechend zu analysieren.

Im Jahr 2010 wurde die JaMP-Umgebung erweitert, so dass die gleichzeitige Nutzung von mehreren Maschinen und Acceleratoren unterst ̈utzt wird. Dieses wurde durch die Entwicklung von zwei Abstraktionsbibliotheken erreicht. Die untere Schicht bietet abstrakte Recheneinheiten, die von den eigentlichen Berechnungseinheiten wie CPUs und GPUs und ihrem Ort in einem Rechnerb ̈undel abstrahieren. Die darauf aufbauende Schicht bietet partitionierte und replizierte Arrays. Ein partitioniertes Array wird dabei automatisch ̈uber die abstrakten Berechnungseinheiten verteilt, wobei die Geschwindigkeiten der einzelnen Berechnungseinheiten zwecks fairer Verteilung ber ̈ucksichtigt werden. Welcher abstrakte Array-Typ f ̈ur ein Array eines Java-Programms konkret eingesetzt wird, entscheidet der JaMP- ̈Ubersetzer mit Hilfe einer Code-Analyse.
Im Jahr 2012 wurde die JaMP-Umgebung erweitert, so dass Schleifen, die Java-Objekte verwenden, ebenfalls auf Rechnerbündeln ausführbar sind. Dabei werden zwei Klassen von Objekten unterschieden. Normale Shared-Objekte werden auf allen Berechnungseinheiten repliziert. Arrays, die Java als Objekte ansieht, können repliziert oder über die Berechnungseinheiten partitioniert werden. Dies ist unabhängig davon, ob es sich um ein Array von Objekten oder primitiven Datentypen handelt. Um die Laufzeit zu verkürzen, wurde mit der Java-Semantik gebrochen und die verzeigerte Objekt-Struktur des Programms wird nun für die Rechnerbündel auf eine flache Struktur abgebildet.
Im Jahr 2013 haben wir untersucht, wie man die Verwendung von Java-Objekten in parallelem OpenMP-Code optimieren kann. Es hat sich gezeigt, dass wir den Sprachumfang leicht einschränken müssen, indem wir Vererbung bei Objekten verbieten, die im parallelen Code eingesetzt werden. Das stellt sicher, dass zur Laufzeit keine anderen Typen als zur Übersetzungszeit vorliegen. Wir benutzen diese Eigenschaft, um Objekte in Arrays auf direkte Weise einbetten zu können. Dadurch wurde die Kommunikation mit den Recheneinheiten der GPU enorm beschleunigt und auch die Laufzeit auf den Berechnungseinheiten wurde leicht gesenkt.
Im Jahr 2014 wurde eine JaMP-Version für Android 4.0 entwickelt, die bisher nur das SIMD-Konstrukt von OpenMP unterstützt.
Im Jahr 2015 wurde das Task-Konzept (OpenMP 3.0) in JaMP integriert. Dadurch lassen .sich rekursive Algorithmen mit JaMP parallelisieren.

Dieses im Jahr 2009 gestartete Projekt befasst sich mit der Refaktorisierung und Parallelisierung von Anwendungen aus der Automatisierungstechnik. Die Programme laufen dabei auf speziellen eingebetteten Systemen. Diese Hardware bildet einen Industriestandard und kommt weltweit zum Einsatz. Da auch in eingebetteten Systemen zunehmend Multicore-Architekturen eingesetzt werden, muss bestehende, sequentielle Software für diese neuen Architekturen parallelisiert werden, um einen Zuwachs an Leistung zu gewinnen. Da die Programme typischerweise in der Industrie zur Regelung von Prozessen und zur Fertigungsautomatisierung eingesetzt werden, haben sie einen langen Lebenszyklus, um die Investitionskosten für die Unternehmen gering zu halten. Aufgrund der langen Einsatzzeit der Programme werden diese oftmals nicht mehr durch die ursprünglichen Entwickler gepflegt. Weiterhin wurde für die Programme oftmals ein hoher Aufwand betrieben, um eine zuverlässige Funktionsweise zu gewährleisten. Erweiterungen an der Software werden daher nur zögerlich vorgenommen.

Eine Migration dieser Altanwendungen auf neue Systeme und ihre anschließende Parallelisierung kann daher nicht von Hand vorgenommen werden, da sich dies als zu fehlerträchtig erweist. Es sind also Werkzeuge nötig, die diese Aufgaben automatisch vornehmen bzw. den Entwickler bei der Migration und Parallelisierung unterstützen.

Erforschung von Parallelisierungstechniken

Zur Parallelisierung von bestehenden Anwendungen aus der Automatisierungstechnik wurde ein spezieller Übersetzer entwickelt, der zunächst Programme aus der Automatisierungstechnik auf ihre automatische Parallelisierbarkeit untersuchte. Hierbei zeigte sich, dass eine automatische Parallelisierung mit existierenden Techniken nicht effizient durchführbar ist. Deshalb konzentriert sich dieses Teilprojekt auf zwei Schritte. Im ersten Schritt wurde eine Datenabhängigkeitsanalyse entwickelt, die potentielle kritische Abschnitte in einem parallelen Programm erkennt und diese dem Entwickler vorschlägt und deren Schutz in den Code einbaut. Die Analyse erlaubt es, atomare Blöcke zu identifiziert, die sehr gut mit den atomaren Blöcken übereinstimmen, die ein Experte im Code platzieren würde. Es wurde außerdem nachgewiesen, dass die Laufzeit nur unmaßgeblich beeinträchtigt wird, falls das Verfahren in seltenen Fällen kritische Abschnitte annimmt, die tatsächlich gar nicht existieren oder kritische Abschnitte ermittelt, die größer als tatsächlich notwendig sind.

Im zweiten Schritt wurden die bestehenden Verfahren Software-Transaktionaler-Speicher (STM) und Lock-Inferenz zur Implementierung atomarer Blöcke verfeinert und verbessert. In dem neuen Ansatz verwendet ein atomarer Block STM, solange Lock-Inferenz keine feingranulare Synchronisation garantieren kann, und wechselt zur Laufzeit von STM zu Lock-Inferenz, sobald feingranulare Synchronisation mit Locks möglich ist. Damit wird jeder atomare Block feingranular synchronisiert, wobei der Laufzeitaufwand von STM minimiert wird. Um die Effektivität des kombinierten Verfahrens zu steigern, wurden bestehende Lock-Inferenz-Algorithmen verbessern, um in mehr Fällen als bisher feingranular synchronisierte atomare Blöcke mit Lock-Inferenz zu implementieren. Es konnte gezeigt werden, dass das kombinierte Verfahren zur Implementierung atomarer Blöcke die Ausführungszeiten gegenüber einer reinen Umsetzung mit STM oder Lock-Inferenz um einen Faktor zwischen 1.1 und 6.3 beschleunigt. Obwohl feingranulare Synchronisation im Allgemeinen zu besserer Leistung als eine grobgranulare Lösung führt, gibt es Fälle, in denen eine grobgranulare Implementierung die gleiche Leistung zeigt. Daher wurde ein Laufzeitmechanismus für STM entwickelt, der ebenfalls mit der kombinierten Technik funktioniert. Dieser Mechanismus startet mit einer kleinen Anzahl an Locks, d.h. mit einer grobgranularen Synchronisierung, bei der Zugriffe auf unterschiedliche gemeinsame Variablen durch die selbe Schlossvariable synchronisiert werden. Falls dieses grobgranulare Locking dazu führt, dass zu viele Zugriffe auf unterschiedliche Variablen auf das selbe Lock warten müssen, dann erhöht die entwickelte Technik graduell die Anzahl an Locks. Dies erhöht die Granularität des Lockings, sodass unabhängige Zugriffe häufiger nebenläufig ausgeführt werden können. Dieser Laufzeitmechanismus zur dynamischen Anpassung der Locking-Granularität führt zu einer bis zu 3.0 mal besseren Laufzeiten als eine statische grobgranulare Lösung.

Das Teilprojekt wurde im Jahr 2014 abgeschlossen.

Erforschung von Migrationstechniken

Unsere Forschung zur Migration von Altanwendungen bestand ursprünglich aus dem Ansatz, veraltete Code-Konstrukte durch ein spezielles Werkzeug automatisch durch besseren Code ersetzen zu lassen. Die zu ersetzenden Code-Konstrukte und der verbesserte Code wurden dabei von Programmierern in einer speziell entwickelten Beschreibungssprache spezifiziert. Hierbei stellte sich jedoch die Handhabbarkeit dieses Werkzeugs für unerfahrene Entwickler als zu schwierig heraus.

Daher wurde mit der Entwicklung eines neues Werkzeugs begonnen, das zu ersetzende Code-Sequenzen automatisch aus Software-Versionsarchiven erlernt, diese dann generalisiert und Verbesserungen vorschlägt. Der Ansatz basiert darauf, dass zwei Versionen eines Programms miteinander verglichen werden. Unser Werkzeug extrahiert dabei, welche Änderungen sich zwischen den beiden Versionen ergeben haben und leitet daraus generalisierte Muster aus zu ersetzenden Code-Sequenzen und die dazugehörigen Code-Verbesserungen automatisch ab. Diese Muster werden in einer Datenbank gespeichert und können anschließend von unserem Werkzeug dazu verwendet werden, analoge Änderungen für den Quellcode anderer Programme vorzuschlagen.

Im Jahr 2014 wurde ein neues Verfahren zur symbolischen Code-Ausführung entwickelt, das die Anzahl falscher Vorschläge reduziert. Abhängig von der Anzahl und Generalität der Muster in der Datenbank kann es ohne das neue Verfahren zu unpassenden Vorschlägen kommen. Um die unpassenden Vorschläge zu verwerfen, wird das semantische Verhalten des Vorschlags mit dem semantischen Verhalten des Musters aus der Datenbank verglichen. Weichen beide zu sehr voneinander ab, wird der Vorschlag aus der Ergebnismenge entfernt. Die Besonderheit des Verfahrens besteht darin, dass es auf herausgelöste Code-Teilstücke anwendbar ist und keine menschliche Vorkonfiguration benötigt.

Die aktuellen Ergebnisse von unserem Werkzeug SIFE sind online zu finden (letztes Update: 2014-05-09).