Eintrag in der Universitätsbibliographie der TU Chemnitz
Volltext zugänglich unter
URN: urn:nbn:de:bsz:ch1-qucosa2-790089
Dietze, Robert
Rünger, Gudula ; Hardt, Wolfram (Gutachter)
Suchbasierte Algorithmen für das Scheduling unabhängiger paralleler Tasks
Search-based Algorithms for the Scheduling of Independent Parallel Tasks
Kurzfassung in deutsch
In parallelen Anwendungen, die auf Grundlage des Programmiermodells der gemischten Parallelität implementiert wurden, lassen sich meist unabhängige Programmteile (Tasks) identifizieren, die sowohl parallel zueinander als auch selbst parallel ausgeführt werden können.Zur Reduzierung der Ausführungszeit solcher Anwendungen auf einem parallelen System wird eine zeitliche und räumliche Zuordnung dieser parallelen Tasks zu den Prozessoren benötigt, welche mithilfe von Schedulingverfahren ermittelt werden kann.
Jedoch ist bereits das Scheduling voneinander abhängiger Single-Prozessor-Tasks auf ein paralleles System mit zwei Prozessoren NP-schwer, weshalb zur Lösung von Schedulingproblemen häufig List-Scheduling-Heuristiken verwendet werden.
Das Scheduling unabhängiger paralleler Tasks ist aufgrund der vielen zusätzlichen Zuordnungsmöglichkeiten deutlich komplexer und erfordert daher dedizierte Lösungsverfahren.
Einen vielversprechenden Ansatz zur Lösung komplexer Schedulingprobleme bilden suchbasierte Verfahren, die lokale oder globale Suchstrategien zur Lösungsfindung nutzen.
In der vorliegenden Arbeit wird untersucht, inwieweit sich derartige Verfahren für das Scheduling unabhängiger paralleler Tasks auf heterogene Systeme bestehend aus Multicore-Rechnern mit unterschiedlichen Eigenschaften eignen.
Zu diesem Zweck werden vier suchbasierte Schedulingverfahren entwickelt und untersucht.
Konkret werden zwei modifizierende und zwei inkrementelle Verfahren vorgestellt, die von Suchverfahren wie der A*-Suche und Metaheuristiken wie der Tabu-Suche und des Simulated Annealing inspiriert sind.
Zusätzlich wird eine Kostenmodellierung in Form von parametrisierten Laufzeitformeln präsentiert, mit der die Ausführungszeiten der parallelen Tasks auf heterogenen Systemenmodelliert werden können.
Die Verfahren werden in Laufzeitmessungen auf heterogenen Rechnerplattformen untereinander und mit existierenden List-Scheduling-Heuristiken verglichen.
Als Anwendungen für die Messungen werden sowohl Programme der SPLASH-3-Benchmark-Suite als auch eine praxisnahe Simulationsanwendung zur Bauteilbelastung untersucht.
Die Ergebnisse zeigen, dass alle vier Verfahren im Vergleich zu existierenden List-Scheduling-Heuristiken eine signifikante Reduktion der Ausführungszeit erreichen können.
| Universität: | Technische Universität Chemnitz | |
| Institut: | Professur Praktische Informatik | |
| Fakultät: | Fakultät für Informatik | |
| Dokumentart: | Dissertation | |
| Betreuer: | Rünger, Gudula (Prof. Dr.) | |
| URL/URN: | https://nbn-resolving.org/urn:nbn:de:bsz:ch1-qucosa2-790089 | |
| SWD-Schlagwörter: | Scheduling , Parallelverarbeitung , Suchverfahren , Metaheuristik | |
| Freie Schlagwörter (Deutsch): | Scheduling , Parallele Tasks , Suchverfahren , Heterogene Architekturen , Kostenmodellierung | |
| DDC-Sachgruppe: | 004.35 | |
| Sprache: | deutsch | |
| Tag der mündlichen Prüfung | 26.04.2022 | |
| OA-Lizenz | CC BY 4.0 |
