Untersuchung und Entwicklung von Taskpools zur dynamischen Lastbalancierung in irregulären Anwendungen

Projektdetails

• Geldgeber: DFG

Projektbeteiligte

• Projektleiter: Prof. Dr. Thomas Rauber 
• Projektmitarbeiter: Dr. Ralf Hoffmann, PD Dr. Matthias Korch, Andreas Prell, M.Sc.
  

Projektbeschreibung

Taskpools dienen zur dynamischen Lastverteilung in irregulären Anwendungen. Die Anwendungen erzeugen dazu anhand ihrer Eingabe in einer Initialisierungsphase eine Reihe von Tasks, die im Taskpool gespeichert werden. Diese Tasks werden ausgeführt, indem alle beteiligten Prozessoren solange Task aus dem Taskpool entnehmen und ausführen, bis alle Tasks abgearbeitet wurden. Während seiner Ausführung kann ein Task neue Tasks erzeugen. Visualisiert man die Hierarchie der Taskerzeugung, so entsteht ein azyklischer gerichteter Graph, der aus mehreren Bäumen besteht. Läßt man Abhängigkeiten zwischen Tasks zu, die nicht aus den Hierarchiebeziehungen stammen, so kann man wesentlich komplexere Graphen erhalten.

Um eine effiziente Ausführung taskbasierter Algorithmen zu erreichen, lassen sich zwei unterschiedliche Strategien verfolgen. Die erste Möglichkeit besteht darin, durch heuristische Verfahren die Latenz des entstehenden Ablaufplanes des Taskgraphen zu optimieren. Dieses Vorgehen hat den Vorteil, daß man sich auf diese Weise an die bestmögliche asymptotische Laufzeit des Algorithmus annähert. Allerdings ist die heuristische Auswahl von Tasks unter Umständen sehr teuer, da eventuell viele Bedingungen berücksichtigt werden müssen und globale Informationen über den Taskgraphen erforderlich sind. Demgegenüber versucht der zweite Ansatz, die Zeit, die für den Zugriff auf den Taskpool erforderlich ist, zu minimieren. Dazu wird eine beliebige Ausführungsreihenfolge der Tasks erlaubt, und einfache Datenstrukturen werden verwendet, deren Manipulation sehr schnell durchgeführt werden kann. Zusätzlich werden die Datenstrukturen so organisiert, daß Wartezeiten und Synchronisationsoverhead reduziert werden. Dieser zweite Ansatz hat den Vorteil, daß der durch den Taskpool verursachte Overhead verringert wird. Er setzt aber voraus, daß nur ausführbare Tasks in den Taskpool eingefügt werden und daß die Struktur des Taskgraphen auch bei beliebiger Ausführungsreihenfolge der Tasks auf der gegebenen Prozessoranzahl zu einem guten Ablaufplan führt.

Ziele des Projekts sind die Suche nach neuen Organisationsformen der Taskpools mit geringerem Overhead bzw. besserer Skalierbarkeit, die Nutzung bzw. Implementierung von effizienten Synchronisationsmechanismen und die Entwicklung paralleler Datenstrukturen, die einen verzögerungsfreien Zugriff auf gemeinsam genutzte Daten erlauben. Betrachtet werden insbesondere Parallelrechner mit gemeinsamem Hauptspeicher. ​

In der aktuellen Projektphase werden adaptive Lastverteilungsstrategien für (heterogene) Multicore-Systeme untersucht, um taskbasierte Applikation auf solchen Rechnern mit geeigneten Programmiermodellen effizient ausführen zu können. Aktuelle Prozessoren wie der Cell-Prozessor und zukünftige Architekturen stellen neue Herausforderungen an die Programmierer. Für die hohe Anzahl von verfügbaren Kernen müssen genügend Berechnungen parallel ausführbar sein. Die Rechenkapazität kann dabei für verschiedene Kerne unterschiedlich sein, wenn zum Beispiel einige Kerne für manche Berechnungen optimiert sind. Auch ökologische Aspekte spielen vermehrt eine Rolle, sodass die Taktfrequenz einzelner Kerne dynamisch angepasst wird, um Energie zu sparen, Überhitzung vorzubeugen oder kurzzeitig eine höhere Rechenleistung bereitzustellen. Diese dynamischen Aspekte müssen im Programmiermodell berücksichtigt werden.