Zeitschriftenartikel
Peelsched: a Simple and Parallel Scheduling Algorithm for Static Taskgraphs
Lade...
Volltext URI
Dokumententyp
Text/Journal Article
Datum
2011
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Quelle
PARS: Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware: Vol. 28, No. 1
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
We present a new algorithm, which we call P EELSCHED, to schedule a set of tasks with precedence constraints and communication costs onto a parallel computer with homogeneous processing units. The algorithm is deterministic and simple, and can be parallelized itself. The new algorithm is based on the usage of structural graph properties, in particular series-parallel or N-free graphs, but can be used on any DAG. We provide an implementation and validate it against a benchmark suite of task graphs. We find that the algorithm's scheduling results are comparable to strictly sequential schedulers.