% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@MASTERSTHESIS{Szuszies:992091,
author = {Szuszies, Thorben},
othercontributors = {Müller, Matthias S. and Unger, Walter and Schmitz, Adrian
and Wassermann, Christian},
title = {{D}eveloping a scalable sheduling algorithm for the global
optimization of parallel patterns on hetrogeneous
architectures},
school = {RWTH Aachen University},
type = {Masterarbeit},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2024-08001},
pages = {1 Online-Ressource: Illustrationen},
year = {2024},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; 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.},
cin = {123010 / 120000 / 022000},
ddc = {004},
cid = {$I:(DE-82)123010_20140620$ / $I:(DE-82)120000_20140620$ /
$I:(DE-82)022000_20140101$},
typ = {PUB:(DE-HGF)19},
doi = {10.18154/RWTH-2024-08001},
url = {https://publications.rwth-aachen.de/record/992091},
}
guest ::