TU Darmstadt / ULB / TUprints

Enhancing the Speed and Automation of Assisted Parallelization

Norouzi, Mohammad (2022):
Enhancing the Speed and Automation of Assisted Parallelization. (Publisher's Version)
Darmstadt, Technische Universität Darmstadt,
DOI: 10.26083/tuprints-00022884,
[Ph.D. Thesis]

[img] Text
Mohammad_Norouzi_PhD_Dissertation.pdf
Copyright Information: CC-BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (3MB)
Item Type: Ph.D. Thesis
Status: Publisher's Version
Title: Enhancing the Speed and Automation of Assisted Parallelization
Language: English
Abstract:

Parallelization is a technique that boosts the performance of a program beyond optimizations of the sequential algorithm. Utilizing the technique requires deep program knowledge and is usually complex and time-consuming. Software tools have been proposed to discover parallelism opportunities. Tools relying on static analysis follow a conservative path and tend to miss many opportunities, whereas dynamic analysis suffers from a vast runtime overhead, often resulting in a slowdown of 100x. In this dissertation, we present two methods that help programmers parallelize programs. We abandon the idea of fully automated parallelization and instead pinpoint programmers to potential parallelism opportunities in the source code. Our first method detects data dependences using a hybrid approach, mitigating the limitations of both static and dynamic analyses. Our second method exploits the identified dependences to provide practical hints for parallelizing a sequential program. Data dependence analysis can be performed statically or dynamically. Static analysis is fast, but it overestimates the number of data dependences. Dynamic analysis records dependences that actually occur during program execution but suffers from high runtime overhead and is also input sensitive. We have proposed a hybrid approach that considerably reduces the overhead and does not overestimate data dependences. Our approach first detects memory-access instructions that create statically-identifiable data dependences. Then, it excludes these instructions from the instrumentation, avoiding their associated overhead at runtime. We have implemented our approach in DiscoPoP, a parallelism discovery tool, and evaluated it with 49 benchmarks from three benchmark suites (i.e., Polybench, NPB, and BOTS) and two simulation applications (namely, EOS-MBPT and LULESH). The median reduction of the profiling time across all programs was 76%. Additionally, we proposed a method that uses the identified dependences to make recommendations on how to parallelize a program with OpenMP. OpenMP allows programmers to annotate code sections in a program with parallelization constructs. Programming with OpenMP is not easy. Programmers need to determine which construct to insert where in the source code to maximize performance and preserve correctness. Another task is classifying variables inside the constructs according to their data-sharing semantics. Performing these tasks manually is complex and error-prone. We have proposed an approach that automates these tasks. Our approach receives as input parallel design patterns derived from the extracted data dependences and maps them to appropriate OpenMP constructs and source-code lines. Further, it classifies the variables within those constructs. After integrating our parallelization approach into DiscoPoP, we used it to parallelize our test programs. We compared their execution times with their sequential versions. We observed a speedup of up to 1.35x for EOS-MBPT and 8x for LULESH. For the benchmarks, we further compared our parallelizations with those generated by three state-of-the-art parallelization tools: We produced faster codes in most cases with an average speedup relative to any of the three ranging from 1.8 to 2.7. Also, we automatically reclassified variables of OpenMP programs parallelized manually or with the help of these tools, reducing their execution time by up to 29%. Moreover, we found that the inherent input sensitivity of the dynamic dependence analysis, if running the target program with a range of representative inputs, does not make the resulting parallel programs harder to validate than those parallelized manually. Finally, our approach has been extended to suggest offloading suitable kernels onto the GPU using OpenMP.

Alternative Abstract:
Alternative AbstractLanguage

Parallelisierung eröffnet die Möglichkeit, die Performanz eines Programms über die Optimierung des sequenziellen Algorithmus hinaus zu steigern. Ihre Anwendung erfordert fundierte Kenntnisse des Programms und ist in der Regel sowohl komplex als auch zeitaufwendig. Um mögliche Parallelität zu erschließen, kann auf verschiedene Softwaretools zurückgegriffen werden. Tools, welche auf statischen Analysen basieren, parallelisieren in der Regel viel zu konservativ, während dynamische Analysen meist enormen Laufzeit-Overhead verursachen, wobei Verlangsamungen um das 100-fache keine Seltenheit sind. Diese Dissertation stellt zwei Methoden vor, welche Programmierer darin unterstützt, Programme zu parallelisieren. Wir abschieden uns von der Idee der vollautomatisierten Parallelisierung und weisen Programmierer stattdessen auf potenzielle Parallelisierungsmöglichkeiten im Quellcode hin. Die Methoden umfassen im Einzelnen eine hybride Datenabhängigkeitsanalyse, welche den Beschränkungen statischer als auch dynamischer Analysen entgegenwirkt, und eine Technik, die die identifizierten Abhängigkeiten nutzt, um Programmierern praktische Hinweise zur Parallelisierung eines sequenziellen Programms zu geben. Eine Datenabhängigkeitsanalyse kann statisch oder dynamisch durchgeführt werden. Die statische Analyse ist schnell, überschätzt jedoch die Anzahl der Datenabhängigkeiten. Die dynamische Analyse zeichnet Abhängigkeiten auf, welche tatsächlich während der Programmausführung auftreten, aber ist zeitaufwendig und zusätzlich inputsensitiv. Wir haben uns daher für einen hybriden Ansatz entschieden, der den Overhead erheblich reduziert und die Datenabhängigkeiten nicht überschätzt. Unsere Methode erkennt zuerst Speicherzugriffsbefehle, die statisch identifizierbare Datenabhängigkeiten bilden. Anschließend werden diese Anweisungen von der Instrumentierung ausgeschlossen und der damit verbundene Laufzeit-Overhead vermieden. Wir haben die Methode in DiscoPoP, ein Werkzeug zur Erkennung von Parallelität, integriert und mit 49 Benchmarks aus drei Benchmark-Suiten (Polybench, NPB und BOTS) sowie zwei Simulationsanwendungen (EOS-MBPT und LULESH) evaluiert. Der Median der Laufzeitreduktion über alle Programme lag bei 76%. Darüber hinaus haben wir eine Methode vorgestellt, welche die identifizierten Abhängigkeiten verwendet, um Parallelisierungshinweise auf OpenMP-Ebene zu liefern. OpenMP ermöglicht es Programmierern, Codeabschnitte in einem Programm mit Parallelisierungskonstrukten zu annotieren. Die Programmierung mit OpenMP ist nicht einfach. Programmierer müssen bestimmen, welches Konstrukt in welche Quellcodezeile eingefügt werden soll, um die Leistung zu maximieren und gleichzeitig die Korrektheit zu bewahren. Eine weitere Aufgabe besteht darin, Variablen innerhalb der Konstrukte gemäß ihrer Datenaustausch-Semantik zu klassifizieren. Die manuelle Ausführung dieser Aufgaben ist komplex und fehleranfällig. Um dieses Problem zu umgehen, haben wir einen automatischen Ansatz gewählt. Dabei werden parallele Entwurfsmuster, die von den extrahierten Datenabhängigkeiten abgeleitet wurden, auf geeignete OpenMP-Konstrukte und Quellcodezeilen abgebildet. Zudem werden innerhalb der Konstrukte verwendete Variablen klassifiziert. Wir haben DiscoPoP um unseren Parallelisierungsansatz erweitert und die Ausführungszeit der mithilfe von DiscoPoP parallelisierten Testprogramme mit ihren sequenziellen Versionen verglichen. Dabei konnte eine bis zu 1,35-fache Beschleunigung für EOS-MBPT und eine 8-fache für LULESH beobachtetet werden. Bei den Benchmarks haben wir ferner unserer Parallelisierung mit der von drei etablierten Parallelisierungswerkzeugen verglichen: In den meisten Fällen wurde von DiscoPoP schnellerer Code erzeugt – mit einem durchschnittlichen Speedup von 1,8 bis 2,7 gegenüber den anderen Werkzeugen. Darüber hinaus haben wir Variablen von OpenMP-Programmen, die manuell oder mit Hilfe dieser Tools parallelisiert wurden, automatisch neu klassifiziert und so die Ausführungszeiten der Programme um bis zu 29% reduziert. Schließlich konnten wir zeigen, dass die aus der inhärent inputsensitiven dynamischen Datenabhängigkeits-Analyse resultierenden parallelen Programme, wenn man das ursprüngliche sequenzielle Programm mit einer Reihe repräsentativer Inputs ausführt, in der Praxis nicht schwieriger zu validieren sind als händisch parallelisierte Programme. Schließlich haben wir das Verfahren erweitert, um geeignete Kernels in einem Programm mit Hilfe von OpenMP auf eine GPU auszulagern.

German
Place of Publication: Darmstadt
Collation: 145 Seiten in verschiedenen Zählungen
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Parallel Programming
Date Deposited: 24 Nov 2022 13:10
Last Modified: 25 Nov 2022 07:11
DOI: 10.26083/tuprints-00022884
URN: urn:nbn:de:tuda-tuprints-228849
Referees: Wolf, Prof. Dr. Felix ; Haehnle, Prof. Dr. Reiner ; Jannesari, Prof. Dr. Ali
Date of oral examination: 2 December 2021
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/22884
PPN: 502052678
Export:
Actions (login required)
View Item View Item