Performanzabschätzung von parallelen Programmen durch symbolische Ausführung

Die Steigerung der Leistungsfähigkeit aktueller Prozessgenerationen wird durch das Hinzufügen von zusätzlichen Rechenkernen erreicht. Durch die hieraus gegebene Möglichkeit der nebenläufigen Ausführung von unabhängigen Teilstücken einer Anwendung kann die Ausführungszeit signifikant verringert werden. Damit eine Anwendung von Parallelisierung profitieren kann, müssen hierfür passende Stellen im Quellcode vom Entwickler erkannt und parallelisiert werden.
Durch eine Bestimmung von Ausführungskosten können teure Pfade erkannt und analysiert werden. Da sich die Laufzeiten einer Anwendung durch unterschiedliche Eingabeparameter ändern, müssen diese entsprechend gewählt werden. Um passende Eingaben zu erzeugen, kann das Prinzip der symbolischen Ausführung verwendet werden. Hierbei wird der Kontrollfluss analysiert und die Variablenbelegung so angepasst, dass eine hohe Abdeckung ermöglicht wird. Ein großes Problem der symbolischen Ausführung stellt die Pfad-Explosion dar. Die fortschreitende Teilung von Pfaden an Verzweigungspunkten führt zu einem exponentiellen Wachstum der Anzahl an Pfaden. Ab einem bestimmten Punkt kann deren Anzahl zu groß werden, als dass sie die Testanwendung sinnvoll verwalten könnte. ... mehr

Das Ziel dieser Arbeit ist es, einen Entwickler dabei zu unterstützen, in einer bereits vorhandenen Anwendung Schleifen mit Parallelisierungspotential im Quellcode zu finden. Hierzu soll das auf der Compiler-Infrastruktur LLVM aufbauende Test-Programm KLEE erweitert werden. Die primäre Aufgabe von KLEE ist es, durch symbolische Ausführung Ausführungspfade durch Anwendungen zu bestimmen und deren Wege auf vorgegebene Fehlerfälle zu untersuchen.

Mit Hilfe der symbolischen Ausführung sollen Variablenbelegungen bestimmt werden, die zu hohen Ausführungskosten bei einem Pfad führen. Durch die Analyse der Pfade auf Hot-Spots, also Bereiche, die besonders hohe Kosten verursachen, wird es einem Entwickler ermöglicht, gezielt diese auf ihr Parallelisierungspotential zu untersuchen.

Um dem Problem der Pfad EXplosion entgegen zu wirken, muss die Implementierung sinnvoll zwischen den Ausführungspfaden wählen können. Es sollen nur die Pfade weiter analysiert werden, bei denen absehbar ist, dass sie zu interessanten Problemstellen führen.