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 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.
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.
Analyse
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.
In diesem Berichtszeitraum 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.
Im Jahr 2014 haben wir auch 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.
Das Projekt stellt einen Beitrag des Lehrstuhls Informatik 2
zum IZ ESI dar, siehe auch http://www.esi.uni-erlangen.de .