In Zeiten stagnierender Performanz von Einzelprozessoren obliegt die Leistungssteigerung von Programmen deren Entwicklern. Sind alle Möglichkeiten sequentieller Optimierung erschöpft, ist softwaregesteuerte Parallelität die einzig verbleibende Option. Das Schreiben von parallelem Code stellt jedoch immer noch eine Herausforderung dar, besonders wenn der Autor der sequenziellen Version nicht mehr verfügbar ist. Eine Hauptaufgabe ist deshalb die Erkennung potenzieller Parallelität im Quellcode. Werkzeuge zur Entdeckung potenzieller Parallelität vollziehen diese Suche automatisch. Geschieht dies zur Compilezeit, ist das Ergebnis aufgrund mangelnder Laufzeitinformationen eher konservativ. Hingegen leiden Tools, die auf Laufzeitinformationen basieren, vor allem unter großem Overhead – sowohl hinsichtlich Zeit als auch Speicher. Gestützt auf eine dynamische Programmanalysetechnik, präsentiert diese Dissertation ein allgemeines Framework zur Entdeckung verschiedener Arten potenzieller Parallelität mit geringem Overhead. Das Framework besteht aus zwei Hauptkomponenten: einem effizienten Profiler zur Erfassung von Datenabhängigkeiten sowie einer Menge von Algorithmen zur Entdeckung von Parallelität. Den Algorithmen zugrunde liegt das sprachunabhängige Konzept der Computational Units.

Der Profiler dient als Eckpfeiler des Frameworks. Traditionelle Ansätze zum Profiling von Datenabhängigkeiten verursachen signifikanten Overhead. Um diesen zu senken, konzentrieren sich aktuelle Ansätze unter Vernachlässigung von Allgemeingültigkeit und Wiederverwendbarkeit auf diejenige Teilmenge der Abhängigkeitsinformation, die für die jeweilige Analyse benötigt wird. Im Gegensatz dazu begegnet der in dieser Arbeit vorgestellte Profiler der Herausforderung durch signaturbasierte Speicherverwaltung sowie eine lockfreies paralleles Design. Er produziert sowohl für sequentiellen als auch für Thread-parallelisierten Code detaillierte Abhängigkeiten mit praktisch vertretbarem Overhead. Dadurch kann er als allgemeine Basis für ein breites Spektrum an Programmanalysetechniken eingesetzt werden.

Das Konzept der Computational Units (CUs) schafft ein sprachunabhängiges Fundament zur Entdeckung potenzieller Parallelität. CUs sind elementare Programmschritte, die dem Read-Compute-Write Muster folgen. Im Gegensatz zu alternativen Konzepten sind sie nicht auf vordefinierte Sprachkonstrukte beschränkt. Ein Programm wird durch einen CU-Graphen repräsentiert, in dem die Knoten den CUs und die Kanten den Datenabhängigkeiten entsprechen. Dadurch kann Parallelität unter Berücksichtigung von Code-Refaktorisierung auch über die Grenzen einzelner Sprachkonstrukte hinweg erkannt werden.

Die Ergebnisse unserer Experimente zeigen: 1) Der effiziente Abhängigkeitsprofiler bewirkt im Durchschnitt eine sehr konkurrenzfähige Verlangsamung von etwa einem Faktor 80 mit einer Genauigkeit von mehr als 99,6%. 2) Das Framework erkennt Parallelität in NAS Benchmarks mit hoher Genauigkeit. Es identifiziert 92,5% der parallelen Schleifen. 3) Beim Parallelisieren bekannter Open Source-Software gemäß der Ausgabe des Frameworks werden angemessene Geschwindigkeitsgewinne erzielt. Um schließlich die universelle Verwendbarkeit des Frameworks zu demonstrieren, werden beispielhaft Anwendungen jenseits der Erkennung von Parallelität diskutiert.