TU Darmstadt / ULB / TUbiblio

Identification of Suitable Parallelization Patterns for Sequential Programs

Huda, Zia ul (2021)
Identification of Suitable Parallelization Patterns for Sequential Programs.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00019668
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (Abstract)

During the past decade, the degree of parallelism available in hardware has grown quickly and decisively. Unfortunately, transforming an existing sequential program into a parallel one is not an easy task. Although modern compilers are able to detect the parallelism available in simple loops, a wide range of sequential programs cannot profit from these strategies because such compilers may miss coarser-grained but sometimes more scalable parallelism.

To strengthen programmer productivity, over the years software engineers created a comprehensive list of sequential design patterns. These patterns improve the quality, re-usability, and maintainability of the software. Similarly, to ease the burden of parallel programming, parallel design patterns have been introduced. These patterns provide reusable solutions for common problems and help avoid concurrency bugs such as deadlocks and data races, which are very difficult to locate. Although parallel patterns are helpful for programmers, much effort is still needed to find appropriate places to apply them in the software architecture. This problem is exacerbated if one’s job is to parallelize a sequential program written by someone else. A programmer or software architect needs to have deep knowledge of not only parallel patterns but also of the target program.

Tools have been developed to identify parallel patterns in the data-dependence graphs of a sequential application but they usually support at most one or two parallel patterns. This dissertation presents a framework to automatically detect a much broader variety of parallel patterns in the algorithm structure design space of sequential applications.

For the identification of parallel patterns, we analyze the dependence graphs of each region of the application under study. We use different novel approaches, such as template matching and regression analysis to detect parallel patterns in a region. Furthermore, code blocks in a region are classified according to the appropriate support structure of the detected pattern. This classification eases the transformation of a sequential application into its parallel version. Finally, we defined a metric that helps select the best suitable parallel pattern out of multiple patterns detected in the same region.

We support the identification of six parallel patterns in the algorithm structure of sequential applications: pipeline, multi-loop pipeline, task parallelism, geometric decomposition, do-all and reduction. We successfully identified these patterns in applications from four different benchmark suites. We confirmed our results by comparing them with pre-existing parallel versions of these applications. We also implemented the detected patterns on our own in those cases where parallel implementations were not available and achieved considerable speedups.

Typ des Eintrags: Dissertation
Erschienen: 2021
Autor(en): Huda, Zia ul
Art des Eintrags: Erstveröffentlichung
Titel: Identification of Suitable Parallelization Patterns for Sequential Programs
Sprache: Englisch
Referenten: Wolf, Prof. Dr. Felix ; Gerndt, Prof. Dr. Michael ; Jannesari, Prof. Dr. Ali
Publikationsjahr: 2021
Ort: Darmstadt
Kollation: v, 112, XXI Seiten
Datum der mündlichen Prüfung: 29 Juli 2021
DOI: 10.26083/tuprints-00019668
URL / URN: https://tuprints.ulb.tu-darmstadt.de/19668
Kurzbeschreibung (Abstract):

During the past decade, the degree of parallelism available in hardware has grown quickly and decisively. Unfortunately, transforming an existing sequential program into a parallel one is not an easy task. Although modern compilers are able to detect the parallelism available in simple loops, a wide range of sequential programs cannot profit from these strategies because such compilers may miss coarser-grained but sometimes more scalable parallelism.

To strengthen programmer productivity, over the years software engineers created a comprehensive list of sequential design patterns. These patterns improve the quality, re-usability, and maintainability of the software. Similarly, to ease the burden of parallel programming, parallel design patterns have been introduced. These patterns provide reusable solutions for common problems and help avoid concurrency bugs such as deadlocks and data races, which are very difficult to locate. Although parallel patterns are helpful for programmers, much effort is still needed to find appropriate places to apply them in the software architecture. This problem is exacerbated if one’s job is to parallelize a sequential program written by someone else. A programmer or software architect needs to have deep knowledge of not only parallel patterns but also of the target program.

Tools have been developed to identify parallel patterns in the data-dependence graphs of a sequential application but they usually support at most one or two parallel patterns. This dissertation presents a framework to automatically detect a much broader variety of parallel patterns in the algorithm structure design space of sequential applications.

For the identification of parallel patterns, we analyze the dependence graphs of each region of the application under study. We use different novel approaches, such as template matching and regression analysis to detect parallel patterns in a region. Furthermore, code blocks in a region are classified according to the appropriate support structure of the detected pattern. This classification eases the transformation of a sequential application into its parallel version. Finally, we defined a metric that helps select the best suitable parallel pattern out of multiple patterns detected in the same region.

We support the identification of six parallel patterns in the algorithm structure of sequential applications: pipeline, multi-loop pipeline, task parallelism, geometric decomposition, do-all and reduction. We successfully identified these patterns in applications from four different benchmark suites. We confirmed our results by comparing them with pre-existing parallel versions of these applications. We also implemented the detected patterns on our own in those cases where parallel implementations were not available and achieved considerable speedups.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
Status: Verlagsversion
URN: urn:nbn:de:tuda-tuprints-196682
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Parallele Programmierung
Hinterlegungsdatum: 12 Okt 2021 13:09
Letzte Änderung: 14 Okt 2021 12:01
PPN:
Referenten: Wolf, Prof. Dr. Felix ; Gerndt, Prof. Dr. Michael ; Jannesari, Prof. Dr. Ali
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 29 Juli 2021
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen