Internally funded project
Acronym: ErLaDeF
Start date : 01.01.2012
End date : 30.11.2014
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.
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.