h1

000992091 001__ 992091
000992091 005__ 20240918052114.0
000992091 0247_ $$2datacite_doi$$a10.18154/RWTH-2024-08001
000992091 037__ $$aRWTH-2024-08001
000992091 041__ $$aEnglish
000992091 082__ $$a004
000992091 1001_ $$0P:(DE-82)993134$$aSzuszies, Thorben$$b0$$urwth
000992091 245__ $$aDeveloping a scalable sheduling algorithm for the global optimization of parallel patterns on hetrogeneous architectures$$cThorben Szuszies$$honline
000992091 246_3 $$aEntwicklung eines skalierbaren Scheduling Algorithmusses für die globale Optimierung von parallelen Mustern auf Heterogenen Architekturen$$yGerman
000992091 260__ $$aAachen$$bRWTH Aachen University$$c2024
000992091 300__ $$a1 Online-Ressource: Illustrationen
000992091 3367_ $$02$$2EndNote$$aThesis
000992091 3367_ $$0PUB:(DE-HGF)19$$2PUB:(DE-HGF)$$aMaster Thesis$$bmaster$$mmaster
000992091 3367_ $$2BibTeX$$aMASTERSTHESIS
000992091 3367_ $$2DRIVER$$amasterThesis
000992091 3367_ $$2DataCite$$aOutput Types/Supervised Student Publication
000992091 3367_ $$2ORCID$$aSUPERVISED_STUDENT_PUBLICATION
000992091 502__ $$aMasterarbeit, RWTH Aachen University, 2024$$bMasterarbeit$$cRWTH Aachen University$$d2024$$gFak01$$o2024-08-09
000992091 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
000992091 5203_ $$aDie 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.$$lger
000992091 520__ $$aParallel 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.$$leng
000992091 591__ $$aGermany
000992091 7001_ $$0P:(DE-82)IDM01074$$aMüller, Matthias S.$$b1$$eThesis advisor$$urwth
000992091 7001_ $$0P:(DE-82)IDM04394$$aUnger, Walter$$b2$$eThesis advisor$$urwth
000992091 7001_ $$0P:(DE-82)IDM05459$$aSchmitz, Adrian$$b3$$eConsultant$$urwth
000992091 7001_ $$0P:(DE-82)IDM05561$$aWassermann, Christian$$b4$$eConsultant$$urwth
000992091 8564_ $$uhttps://publications.rwth-aachen.de/record/992091/files/992091.pdf$$yOpenAccess
000992091 8564_ $$uhttps://publications.rwth-aachen.de/record/992091/files/992091_AV.pdf$$yRestricted
000992091 8564_ $$uhttps://publications.rwth-aachen.de/record/992091/files/992091_sources.zip$$yRestricted
000992091 909CO $$ooai:publications.rwth-aachen.de:992091$$popenaire$$popen_access$$pVDB$$pdriver$$pdnbdelivery
000992091 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000992091 9141_ $$y2024
000992091 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)993134$$aRWTH Aachen$$b0$$kRWTH
000992091 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM01074$$aRWTH Aachen$$b1$$kRWTH
000992091 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM04394$$aRWTH Aachen$$b2$$kRWTH
000992091 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM05459$$aRWTH Aachen$$b3$$kRWTH
000992091 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM05561$$aRWTH Aachen$$b4$$kRWTH
000992091 9201_ $$0I:(DE-82)123010_20140620$$k123010$$lLehrstuhl für Hochleistungsrechnen (Informatik 12)$$x0
000992091 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1
000992091 9201_ $$0I:(DE-82)022000_20140101$$k022000$$lIT Center$$x2
000992091 961__ $$c2024-09-17T15:16:19.949063$$x2024-08-27T13:38:28.889398$$z2024-09-17T15:16:19.949063
000992091 9801_ $$aFullTexts
000992091 980__ $$aI:(DE-82)022000_20140101
000992091 980__ $$aI:(DE-82)120000_20140620
000992091 980__ $$aI:(DE-82)123010_20140620
000992091 980__ $$aUNRESTRICTED
000992091 980__ $$aVDB
000992091 980__ $$amaster