- Optimierung von Filter Strategien für Heterogenes Maschine Scheduling unter Verwendung von Beam Search
He, Liangkun; Müller, Matthias S. (Thesis advisor); Lankes, Stefan (Thesis advisor); Schmitz, Adrian (Consultant)
Aachen : RWTH Aachen University (2025)
Master Thesis
Masterarbeit, RWTH Aachen University, 2025
Abstract
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
Institutions
- Department of Computer Science [120000]
- Chair of High Performance Computing (Computer Science 12) [123010]