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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:79008 |
| Date | 09 May 2022 |
| Creators | Dietze, Robert |
| Contributors | Rünger, Gudula, Hardt, Wolfram, Technische Universität Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German |
| Detected Language | German |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 10.1002/cpe.5898, 10.1007/978-3-030-48340-1_26, 10.1109/HPCS.2018.00062, 10.12694/scpe.v18i2.1285, 10.1007/s11227-016-1711-1 |
Page generated in 0.0021 seconds