Während des letzten Jahrzehnts ist der Grad der in der Hardware verfügbaren Parallelität schnell und entscheidend gewachsen. Leider ist es keine leichte Aufgabe, ein vorhandenes sequenzielles Programm in ein paralleles umzuwandeln. Obwohl moderne Compiler in der Lage sind, die in einfachen Schleifen vorhandene Parallelität zu erkennen, kann eine Vielzahl sequenzieller Programme nicht von diesem Vorgehen profitieren, da solche Compiler möglicherweise eine gröbere, aber manchmal besser skalierbare Parallelisierung nicht berücksichtigen.

Um die Produktivität der Programmierer zu steigern, haben Softwareentwickler im Laufe der Jahre eine umfassende Liste von Entwurfsmustern für sequenzielle Programme erstellt. Diese Muster verbessern die Qualität, Wiederverwendbarkeit und Wartbarkeit der Software. Um parallele Programmierung zu vereinfachen, wurden in ähnlicher Weise Entwurfsmuster für parallele Programme eingeführt. Diese Muster bieten wiederverwendbare Lösungen für häufig auftretende Probleme und helfen dabei, Fehler in parallelen Implementierungen wie Deadlocks und Race Conditions zu vermeiden, die sehr schwer zu finden sind. Obwohl parallele Muster für Programmierer hilfreich sind, ist dennoch viel Aufwand erforderlich, um in der Softwarearchitektur geeignete Stellen für ihren Einsatz zu finden. Dieses Problem wird noch verschärft, wenn die Aufgabe darin besteht, ein sequenzielles Programm zu parallelisieren, das von jemand anderem geschrieben wurde. Ein Programmierer oder Softwarearchitekt muss nicht nur über fundierte Kenntnisse paralleler Entwurfsmuster, sondern auch des Zielprogramms verfügen.

Es existieren bereits Werkzeug, um parallele Muster in den Datenabhängigkeitsgraphen einer sequenziellen Anwendung zu identifizieren, sie unterstützen jedoch normalerweise höchstens ein oder zwei parallele Muster. Die vorliegende Dissertation stellt dagegen ein Framework zur automatischen Erkennung einer viel größeren Vielfalt paralleler Muster im Entwurfsraum für algorithmischer Strukturen sequenzieller Anwendungen vor.

Zur Identifikation paralleler Muster analysieren wir die Abhängigkeitsgraphen jeder Region der untersuchten Anwendung. Wir verwenden verschiedene neuartige Ansätze wie Template-Matching und Regressionsanalyse, um die Anwendbarkeit paralleler Muster in einer Coderegion zu erkennen. Darüber hinaus werden Codeblöcke in einer Region entsprechend der Struktur der erkannten Muster klassifiziert. Diese Klassifizierung erleichtert die Umwandlung einer sequenziellen Anwendung in ihre parallele Version. Schließlich wurde eine Metrik definiert, die dabei hilft, die am besten geeigneten parallelen Muster aus mehreren in derselben Region erkannten Muster auszuwählen.

Der entwickelte Ansatz unterstützt die Identifikation von sechs parallelen Mustern in der algorithmischen Struktur sequenzieller Anwendungen: Pipeline, Multi-Loop-Pipeline, Task-Parallelität, geometrische Dekomposition, Do-All und Reduktion. Diese Muster wurden erfolgreich in Programmen aus vier verschiedenen Benchmark-Suiten identifiziert. Die Ergebnisse wurden durch einen Vergleich mit bereits vorhandenen parallelen Versionen dieser Programme validiert. In denjenigen Fällen, in denen keine vorhandenen parallelen Implementierungen verfügbar waren, wurden die Muster selbst implementiert, wodurch erhebliche Beschleunigungen erzielt werden konnten.