Jakob Krainz

Um sicherzustellen, dass Fehler im Programmdesign schon früh im Entwicklungsprozess gefunden werden, ist es nützlich, Fehler möglichst schon während des Editierens des Programms zu finden.  Dazu sollte die verwendete Analyse so schnell sein, dass ein interaktiver Einsatz möglich ist.  Eine Möglichkeit, dies umzusetzen, ist der Einsatz von inkrementeller Analyse, bei der die Analyseergebnisse von Teilen eines Programms zu Gesamtergebnissen kombiniert werden.  Vorteil von inkrementeller Programmanalyse ist, dass bei kleineren Änderungen ein großer Teil der Analyseergebnisse wieder verwendet werden kann, wie auch z.B. Analyseergebnisse von u.U. verwendeten Programmbibliotheken. Hierdurch kann der Analyseaufwand drastisch reduziert werden, wodurch die Analyse interaktiv nutzbar wird.
Unsere Analyse basiert darauf, für (Teile von) einzelnen Funktionen zu bestimmen, welche Auswirkungen die Ausführung auf den Zustand des Programms zur Laufzeit haben kann.  Hierzu wird der Laufzeitzustand eines Programms abstrakt durch einen Graphen dargestellt, der die im Speicher befindlichen Variablen und Objekte und ihre Verzeigerung beschreibt.  Die Funktion wird symbolisch ausgeführt und dabei wird bestimmt, welche Änderungen an dem Laufzeitzustand bzw. an dem diesen darstellenden Graphen verursacht werden können.  Um die Effekte von Hintereinanderausführung von Programmteilen, Funktionsaufrufen, Schleifen, etc. zu bestimmen, können die Änderungsbeschreibungen der Programmteile dann zu größeren Änderungsbeschreibungen kombiniert werden.  Die Analyse geht dabei Bottom-Up vor, analysiert also eine aufgerufene Funktion vor der aufrufenden Funktion (wobei Rekursion analysierbar ist).

Im Jahr 2015 lag der Schwerpunkt der Forschung darauf, die eingesetzten Algorithmen und Datenstrukturen weiter zu entwickeln. So konnte die für die Analyse eines gegebenen Programmes benötigte Laufzeit deutlich verringert werden. Zum anderen dürfen die zu analysierenden Programme mehr und mächtigere Features und Elemente der Programmiersprache benutzen.

Im Jahr 2016 lag der Schwerpunkt der Forschung darauf, die eingesetzten Algorithmen und Datenstrukturen weiter zu entwickeln. Im Fokus lagen hierbei zum einen die Skalierbarkeit der Analyse bis hin zu Programmen mit mehr als 1 Mio. Anweisungen und zum anderen die inkrementelle Analyse, bei der die Analyseergebnisse von unveränderten Programmteilen weiterverwendet werden, was die Analyse bei typischen Software-Entwicklungspraktiken (großes Code-Volumen, meist sehr kleine Änderungen) deutlich beschleunigt.

Im Jahr 2017 lag der Schwerpunkt unserer Forschung darauf, die eingesetzten Algorithmen und Datenstrukturen weiter zu entwickeln. Zusätzlich zu einer besseren Skalierbarkeit der Analyse bei großen zu analysierenden Programmen und einer Weiterentwicklung der inkrementellen Analyse (bei der die Analyseergebnisse von unveränderten Programmteilen weiterverwendet werden), lag der Fokus darauf, die Analyse anschaulich zu dokumentieren, ihre Korrektheit nachzuvollziehen und eine theoretische Grundlage zu konstruieren.

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.