- Titel
- Suchbasierte Algorithmen für das Scheduling unabhängiger paralleler Tasks
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:ch1-qucosa2-790089
- Übersetzter Titel (EN)
- Search-based Algorithms for the Scheduling of Independent Parallel Tasks
- Datum der Einreichung
- 25.10.2021
- Datum der Verteidigung
- 26.04.2022
- Abstract (DE)
- 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 Systemen modelliert 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.
- Verweis
- The Search-based Scheduling Algorithm HP* for Parallel Tasks on Heterogeneous Platforms
DOI: 10.1002/cpe.5898 - Search-based Scheduling for Parallel Tasks on Heterogenous Platforms
DOI: 10.1007/978-3-030-48340-1_26 - Analysis and Modeling of Resource Contention Effects based on Benchmark Applications
DOI: 10.1109/HPCS.2018.00062 - Integrating generic FEM simulations into complex simulation applications
DOI: 10.12694/scpe.v18i2.1285 - Water-Level scheduling for parallel tasks in compute-intensive application components
DOI: 10.1007/s11227-016-1711-1 - Freie Schlagwörter (DE)
- Scheduling, Parallele Tasks, Suchverfahren, Heterogene Architekturen, Kostenmodellierung
- Klassifikation (DDC)
- 004.35
- Normschlagwörter (GND)
- Scheduling, Parallelverarbeitung, Suchverfahren, Metaheuristik
- GutachterIn
- Prof. Dr. Gudula Rünger
- Prof. Dr. Wolfram Hardt
- BetreuerIn Hochschule / Universität
- Prof. Dr. Gudula Rünger
- Den akademischen Grad verleihende / prüfende Institution
- Technische Universität Chemnitz, Chemnitz
- Version / Begutachtungsstatus
- publizierte Version / Verlagsversion
- URN Qucosa
- urn:nbn:de:bsz:ch1-qucosa2-790089
- Veröffentlichungsdatum Qucosa
- 09.05.2022
- Dokumenttyp
- Dissertation
- Sprache des Dokumentes
- Deutsch
- Lizenz / Rechtehinweis
CC BY 4.0