TU Darmstadt / ULB / TUprints

Discovery of Potential Parallelism in Sequential Programs

Li, Zhen (2016)
Discovery of Potential Parallelism in Sequential Programs.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
thesis.pdf
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (4MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Discovery of Potential Parallelism in Sequential Programs
Language: English
Referees: Wolf, Prof. Dr. Felix ; Clauss, Prof. Dr. Philippe
Date: 1 September 2016
Place of Publication: Darmstadt
Date of oral examination: 28 October 2016
Abstract:

In the era of multicore processors, the responsibility for performance gains has been shifted onto software developers. Once improvements of the sequential algorithm have been exhausted, software-managed parallelism is the only option left. However, writing parallel code is still difficult, especially when parallelizing sequential code written by someone else. A key task in this process is the identification of suitable parallelization targets in the source code. Parallelism discovery tools help developers to find such targets automatically. Unfortunately, tools that identify parallelism during compilation are usually conservative due to the lack of runtime information, and tools relying on runtime information primarily suffer from high overhead in terms of both time and memory. This dissertation presents a generic framework for parallelism discovery based on dynamic program analysis, supporting various types of parallelism while incurring practically affordable overhead. The framework contains two main components: an efficient data-dependence profiler and a set of parallelism discovery algorithms based on a language-independent concept called Computational Unit.

The data-dependence profiler serves as the foundation of the parallelism discovery framework. Traditional dependence profiling approaches introduce a tremendous amount of time and memory overhead. To lower the overhead, current methods limit their scope to the subset of the dependence information needed for the analysis they have been created for, sacrificing generality and discouraging reuse. In contrast, the profiler shown in this thesis addresses the problem via signature-based memory management and a lock-free parallel design. It produces detailed dependences not only for sequential but also for multi-threaded code without causing prohibitive overhead, allowing it to serve as a generic base for various program analysis techniques.

Computational Units (CUs) provide a language-independent foundation for parallelism discovery. CUs are computations that follow the read-compute-write pattern. Unlike other concepts, they are not restricted to predefined language constructs. A program is represented as a CU graph, in which vertexes are CUs and edges are data dependences. This allows parallelism to be detected that spreads across multiple language constructs, taking code refactoring into consideration. The parallelism discovery algorithms cover both loop and task parallelism.

Results of our experiments show that 1) the efficient data-dependence profiler has a very competitive average slowdown of around 80× with accuracy higher than 99.6%; 2) the framework discovers parallelism with high accuracy, identifying 92.5% of the parallel loops in NAS benchmarks; 3) when parallelizing well-known open-source software following the outputs of the framework, reasonable speedups are obtained. Finally, use cases beyond parallelism discovery are briefly demonstrated to show the generality of the framework.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
Uncontrolled Keywords: parallelism discovery, data-dependence profiling, program analysis, computational unit, parallel programming
URN: urn:nbn:de:tuda-tuprints-57412
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Parallel Programming
Date Deposited: 08 Nov 2016 10:10
Last Modified: 09 Jul 2020 01:26
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/5741
PPN: 390388424
Export:
Actions (login required)
View Item View Item