- Entwicklung eines skalierbaren Scheduling Algorithmusses für die globale Optimierung von parallelen Mustern auf Heterogenen Architekturen
Szuszies, Thorben; Müller, Matthias S. (Thesis advisor); Unger, Walter (Thesis advisor); Schmitz, Adrian (Consultant); Wassermann, Christian (Consultant)
Aachen : RWTH Aachen University (2024)
Masterarbeit
Masterarbeit, RWTH Aachen University, 2024
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.
Einrichtungen
- IT Center [022000]
- Fachgruppe Informatik [120000]
- Lehrstuhl für Hochleistungsrechnen (Informatik 12) [123010]