- 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)
Master Thesis
Masterarbeit, RWTH Aachen University, 2024
Abstract
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.
Institutions
- IT Center [022000]
- Department of Computer Science [120000]
- Chair of High Performance Computing (Computer Science 12) [123010]