TU Darmstadt / ULB / TUprints

Identification of Suitable Parallelization Patterns for Sequential Programs

Huda, Zia ul (2021):
Identification of Suitable Parallelization Patterns for Sequential Programs. (Publisher's Version)
Darmstadt, Technische Universität,
DOI: 10.26083/tuprints-00019668,
[Ph.D. Thesis]

[img]
Preview
Text
Identification_of_Suitable_Parallelization_Patterns_for_Sequential_Programs_Ul_Huda.pdf
Available under CC-BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Status: Publisher's Version
Title: Identification of Suitable Parallelization Patterns for Sequential Programs
Language: English
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.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
Place of Publication: Darmstadt
Collation: v, 112, XXI Seiten
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Parallel Programming
Date Deposited: 12 Oct 2021 13:09
Last Modified: 12 Oct 2021 13:10
DOI: 10.26083/tuprints-00019668
URN: urn:nbn:de:tuda-tuprints-196682
Referees: Wolf, Prof. Dr. Felix ; Gerndt, Prof. Dr. Michael ; Jannesari, Prof. Dr. Ali
Refereed: 29 July 2021
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19668
Export:
Actions (login required)
View Item View Item