Developing a scalable sheduling algorithm for the global optimization of parallel patterns on hetrogeneous architectures

Szuszies, Thorben; Schmitz, Adrian; Wassermann, Christian; Müller, Matthias S.; Unger, Walter

doi:10.18154/RWTH-2024-08001

Developing a scalable sheduling algorithm for the global optimization of parallel patterns on hetrogeneous architectures = Entwicklung eines skalierbaren Scheduling Algorithmusses für die globale Optimierung von parallelen Mustern auf Heterogenen Architekturen

Szuszies, Thorben^RWTH*

2024

VerantwortlichkeitsangabeThorben Szuszies

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource: Illustrationen

Masterarbeit, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Müller, Matthias S. (Thesis advisor)^RWTH* ; Unger, Walter (Thesis advisor)^RWTH* ; Schmitz, Adrian (Consultant)^RWTH* ; Wassermann, Christian (Consultant)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2024-08-09

Online
DOI: 10.18154/RWTH-2024-08001
URL: https://publications.rwth-aachen.de/record/992091/files/992091.pdf

Einrichtungen

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die parallele Programmierung ist in vielen Bereichen der Wissenschaft und Technik weit verbreitet. Große Systeme mit spezialisierter Hardware werden eingesetzt, um die wachsende Nachfrage nach mehr Rechenleistung zu befriedigen. Damit diese Systeme ihr volles Potenzial entfalten können, ist Expertenwissen über die einzelnen Systeme erforderlich. Für diese Systeme wurde das PPL-Projekt [26][38][44] entwickelt, um den High-Level-Code automatisch zu optimieren. In dieser Arbeit wird ein neuer Scheduling-Ansatz für dieses Projekt entwickelt, der nicht auf der Lösung eines MILP basiert. Die grundlegende Basis für diesen Scheduling-Ansatz ist der Beam-Search-Algorithmus, ein heuristischer Suchalgorithmus, der nur einen Teil aller möglichen Schedulings erforscht. Dieser Algorithmus wird für das Scheduling-Problem weiter spezialisiert, indem mehrere Tasks gleichzeitig geschedult werden mit dem Ziel am Ende der Suche das global beste Scheduling zu finden. Zusätzlich werden a Prior Pruning Strategien eingeführt, um den Suchraum weiter zu reduzieren. Darüber hinaus werden verschiedene a posteriori Pruning-Strategien für das Scheduling-Problem erforscht und bewertet. Die Erstellung des Suchbaums des Beam-Search wird zusätzlich durch eine Datenbank erweitert, um die in früheren Phasen gesammelten Informationen wieder zu verwenden und die Geschwindigkeit der Suche zu verbessern. Zusätzlich wird eine parallele Version dieses Ansatzes unter Verwendung von OpenMP erforscht. Um die Korrektheit dieses Ansatzes sicherzustellen, wird eine intensive Testumgebung eingeführt. Die verschiedenen untersuchten Pruning-Strategien werden im Hinblick auf Laufzeit und Ergebnisqualität gegeneinander evaluiert. Außerdem werden die unterschiedlichen eingeführten Spezialisierungen für den Beam-Search auf ihren Nutzen getestet. Dieser Ansatz wird dann mit dem aktuellen Scheduling-Ansatz des PPL-Tools mit Eingaben derselben Größen verglichen. Die wichtigste Information, die aus der Evaluierung hervorgeht, ist, dass dieser neue Ansatz mit dem alten Ansatz konkurrieren kann, da er die Laufzeit verbessern kann. Je nach gewählter Pruning-Strategie variiert diese Verbesserung. Allerdings schränken zwei eingeführte Komponenten die Skalierbarkeit dieses Ansatzes ein. Der Ansatz, der mehrere Tasks auf einmal schedult, führt bei größeren Eingaben zu einem exponentiellen Overhead. Die Hinzufügung der Datenbank schränkt die Verwendbarkeit, von OpenMP aufgrund der erforderlichen umfangreichen Synchronisation, ein.

Parallel programming is widely used in many domains of science and engineering. Large-scale systems with specialized hardware are used to solve the growing demand for more computational power. Utilizing these systems to their full potential requires expert knowledge of each system. For these systems, the PPL-project [26][38][44] is developed to optimize the high-level code automatically. This thesis develops a new scheduling approach for this tool, which is not based on solving a MILP. The fundamental base for this scheduling approach is the beam search algorithm, a heuristic search algorithm that explores only parts of all possible scheduling. This search strategy is further specialized for the scheduling problem by introducing step-based partial schedules with the goal of finding the best global scheduling. Additional a prior pruning strategies are added to reduce the search space further. Furthermore, different posterior pruning strategies are explored and evaluated for the scheduling problem. The creation of the search tree of beam search is then enhanced by a database to reuse information gathered in earlier stages to improve the search performance. Additionally, a parallel version of this approach is explored using OpenMP to improve the performance further. To ensure the correctness of this approach, an intense testing suite is introduced. The different explored pruning strategies are evaluated against each other regarding runtime and result quality. Furthermore, the different introduced specializations of the beam search are evaluated. This beam search approach is then compared to the current PPL tools scheduling approach with inputs of the same size. The critical information gathered by the evaluation is that this new beam search approach can compete with the old approach by improving the runtime. Depending on the chosen pruning strategy, this increase will vary. However, two introduced components limit the scalability of this approach. The step-based approach introduces an exponential overhead for larger inputs. The database addition limits the usability of OpenMP due to the heavy need for synchronization.

OpenAccess:
PDF
(additional files)