guest ::
Optimizing pruning strategies for heterogeneous machine scheduling using beam search = Optimierung von Filter Strategien für Heterogenes Maschine Scheduling unter Verwendung von Beam Search
2025
Masterarbeit, RWTH Aachen University, 2025
Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
Genehmigende Fakultät
Fak01
Hauptberichter/Gutachter
; ;
Tag der mündlichen Prüfung/Habilitation
2025-09-09
Online
DOI: 10.18154/RWTH-2025-08051
URL: https://publications.rwth-aachen.de/record/1018913/files/1018913.pdf
Einrichtungen
Inhaltliche Beschreibung (Schlagwörter)
beam search (frei) ; machine scheduling problems (frei) ; pruning (frei)
Thematische Einordnung (Klassifikation)
DDC: 004
Kurzfassung
Modern high-performance computing (HPC) systems incorporate heterogeneous hard-ware devices, such as CPUs and different types of accelerators. Clusters used by different institutes vary in their hardware configurations, making it challenging to develop efficient parallel programs that can run optimally on various systems. The parallel pattern language project (PPL) [44] aims to optimize parallel programs for different heterogeneous high-performance computing systems. The machine scheduling problem of the global optimization of the PPL project is one of the most challenging problems. This thesis develops an optimized beam search approach to replace the mixed-integer linear programming (MILP) approach for scheduling problems. The proposed approach is based on the beam search algorithm, a heuristic search method that explores a search tree by expanding the most promising nodes within a limited set. The essential technique used in the approach is pruning, which reduces the search space by eliminating intermediate nodes. In a-priori pruning, the refined definition of equivalence classes and vectors is introduced to group devices based on their similarity. Multiple strategies for candidate generation are explored and evaluated. The combination of different a-posteriori pruning strategies is integrated into this work. Additionally, OpenMP is used to parallelize the beam search algorithm to improve the scheduling time. The candidate generation strategies are evaluated and compared based on scheduling time and quality of the results. The optimized beam search approach is com-pared with the previous beam search and MILP approaches. The experimental results show that this work removes the exponential growth of the previous approaches and has multilinear time complexity
OpenAccess: 
PDF
(additional files)
Dokumenttyp
Master Thesis
Format
online
Sprache
English
Interne Identnummern
RWTH-2025-08051
Datensatz-ID: 1018913
Beteiligte Länder
Germany
|
The record appears in these collections: |