PATESIA - Parallelisierungstechniken für eingebettete Systeme in der AutomatisierungstechnikDieses 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.
Im Jahr 2015 wurde die Erkennung von ähnlichen Änderungen verbessert. Der
erste Schritt bestand darin, die Eignung von Clustering-Algorithmen zu
untersuchen, um das bisherige naive Verfahren zur Identifizierung ähnlicher
Änderungen zu ersetzen. Dazu wurden spezielle Heuristiken und Metriken
entwickelt, um ähnliche Änderungen automatisiert gruppieren zu können. Darauf
aufbauend wurden die Ergebnisse verschiedener Clustering-Verfahren miteinander
verglichen. So konnte gegenüber dem bisherigen Ansatz eine deutliche
Verbesserung erreicht werden. Die zweite Verbesserung zielt darauf ab, die
erhaltenen Gruppen ähnlicher Änderungen zusätzlich automatisiert zu verfeinern.
Zu diesem Zweck wurden verschiedene Verfahren aus dem Umfeld des
maschinellen Lernens zur Ausreißererkennung untersucht, um Änderungen, die
fälschlicherweise einer Gruppe zugeordnet wurden, wieder zu entfernen.
Die aktuellen Ergebnisse von unserem Werkzeug SIFE sind hier zu finden (letztes Update:
2014-05-09). Teile des Projekts werden im Rahmen des "ESI-Anwendungszentrum" gefördert.
| Projektleitung: Prof. Dr. Michael Philippsen
Beteiligte: Dr.-Ing. Stefan Kempf, PD Dr. Ronald Veldema, Dr.-Ing. Thorsten Blaß
Laufzeit: 1.6.2009 - 31.12.2014
Förderer: ESI-Anwendungszentrum
Kontakt: Dotzler, Georg
|