• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Suchbasierte Algorithmen für das Scheduling unabhängiger paralleler Tasks

Dietze, Robert 09 May 2022 (has links)
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.

Page generated in 0.016 seconds