Promovend: Jens Lang
Tag der Verteidigung: 09.12.2014
Kurzfassung:

Der Energieverbrauch bei der Ausführung von Simulationen auf Rechenclustern gewinnt im wissenschaftlichen Rechnen stark an Bedeutung. Die Doktorarbeit entwickelt Methoden, um die Ausführung wissenschaftlicher Simulationen automatisch an die zugrunde liegende Hardware anzupassen und damit effizienter zu machen. „Effizient“ ist hier sowohl in Bezug auf die Ausführungszeit als auch auf die Energie zu verstehen. Konkret wird modellbasiertes Autotuning eingesetzt, um zwei Anwendungen, die Schnelle Multipolmethode (FMM) und die Methode der Finiten Elemente (FEM), zeit- und energieeffizient auszuführen. Das modellbasierte Autotuning passt die Ausführung einer Anwendung an die genutzte Hardware und die Eingabedaten an, indem es entsprechend der Vorhersage eines Modells den effizientesten mehrerer Ausführungspfade wählt. Für die FMM, eine baumbasierte Teilchensimulation, wird ein Modell entwickelt, das die Kosten des Algorithmus bei verschiedenen Tiefen des Teilchenbaums vorhersagt. Mit diesem Modell wird die Baumtiefe mit minimaler Ausführungszeit bzw. minimalem Energieverbrauch bestimmt. Für die FEM, die Deformationen von Festkörpern berechnet, wird ein Modell entwickelt, das Ausführungszeit und Energieverbrauch des Algorithmus auf CPUs und Grafikprozessoren beschreibt. Mit diesem Modell wird ermittelt, wie die Rechenlast zwischen CPUs und Grafikprozessor verteilt werden muss, um eine möglichst kurze Ausführungszeit bzw. einen niedrigen Energieverbrauch zu erzielen.

Promovend: Thomas Reichel
Tag der Verteidigung: 11.11.2013
Kurzfassung:

Der weltweit steigende Bedarf an Energie und natürlichen Ressourcen, insbesondere an fossilen Brennstoffen und seltenen Metallen, sowie die angestrebte Reduktion des CO2-Ausstoßes führen zu steigenden Preisen für Energie und Rohstoffe. Der Energie- und Ressourcenbedarf muss daher neben der Funktionalität und den Kosten eines technischen Produkts in Planungs- und Entwicklungsprozesse einbezogen werden. Für eine Minimierung des Energie- und Ressourcenbedarfs sind insbesondere die frühen Phasen der Produktentwicklung von großem Interesse, da in diesen Phasen die wesentlichen Eigenschaften eines Produkts für den gesamten Lebenszyklus zu großen Teilen festgelegt werden. Durch die Forderung nach kürzeren Markteinführungszeiten bei gleichzeitigem Anstieg der Komplexität technischer Produkte ist der Einsatz von Softwaresystemen zur Unterstützung der Planungs- und Entwicklungsprozesse unabdingbar.

Die Zielstellung der vorliegenden Arbeit ist die Entwicklung und Realisierung von Methoden und Verfahren zur softwaretechnischen Unterstützung ausgewählter Abläufe der Produktentwicklung. Die gewählten Abläufe sind die Ausarbeitung von Anforderungsspezifikationen für technische Produkte, die Priorisierung von Anforderungen sowie die Analyse und Bewertung des Energiebedarfs von Werkzeugmaschinen. Der Schwerpunkt der Methoden und Verfahren liegt einerseits auf der Strukturierung und Koordinierung der Zusammenarbeit von Domänenexperten in den ausgewählten Abläufen der Produktentwicklung und andererseits auf der Erweiterung der Abläufe um Energie- und Ressourcenbetrachtungen. Die softwaretechnische Unterstützung der gewählten Abläufe ermöglicht es, die Komplexität der zu entwickelnden Produkte beherrschbar zu machen und den manuellen Aufwand der Domänenexperten in den Abläufen zu verringern.

Promovend: Michael Hofmann
Tag der Verteidigung: 09.03.2012
Kurzfassung:

Partikelsimulationen repräsentieren eine Klasse von daten- und rechenintensiven Simulationsanwendungen, die in unterschiedlichen Bereichen der Wissenschaft und der industriellen Forschung zum Einsatz kommen. Der hohe Berechnungsaufwand der eingesetzten Lösungsmethoden und die großen Datenmengen, die zur Modellierung realistischer Probleme benötigt werden, machen die Nutzung paralleler Rechentechnik hierfür unverzichtbar. Parallelrechner mit verteiltem Speicher stellen dabei eine weit verbreitete Architektur dar, bei der eine Vielzahl an parallel arbeitenden Rechenknoten über ein Verbindungsnetzwerk miteinander Daten austauschen können. Die Berechnung von Wechselwirkungen zwischen Partikeln stellt oft den Hauptaufwand einer Partikelsimulation dar und wird mit Hilfe schneller Lösungsmethoden, wie dem Barnes-Hut-Algorithmus oder der Schnellen Multipolmethode, durchgeführt. Effiziente parallele Implementierungen dieser Algorithmen benötigen dabei eine Sortierung der Partikel nach ihren räumlichen Positionen. Die Sortierung ist sowohl notwendig, um einen effizienten Zugriff auf die Partikeldaten zu erhalten, als auch Teil von Optimierungen zur Erhöhung der Lokalität von Speicherzugriffen, zur Minimierung der Kommunikation und zur Verbesserung der Lastbalancierung paralleler Berechnungen.

Die vorliegende Dissertation beschäftigt sich mit der Entwicklung eines effizienten parallelen Sortierverfahrens und der dafür benötigten Kommunikationsoperationen zur Datenumverteilung in Partikelsimulationen. Hierzu werden eine Vielzahl existierender paralleler Sortierverfahren für verteilten Speicher analysiert und mit den Anforderungen von Seiten der Partikelsimulationsanwendungen verglichen. Besondere Herausforderungen ergeben sich dabei hinsichtlich der Aufteilung der Partikeldaten auf verteilten Speicher, der Gewichtung zu sortierender Daten zur verbesserten Lastbalancierung, dem Umgang mit doppelten Schlüsselwerten sowie der Verfügbarkeit und Nutzung speichereffizienter Kommunikationsoperationen. Um diese Anforderungen zu erfüllen, wird ein neues paralleles Sortierverfahren entwickelt und in die betrachteten Anwendungsprogramme integriert. Darüber hinaus wird ein neuer In-place-Algorithmus für der MPI_Alltoallv-Kommunikationsoperation vorgestellt, mit dem der Speicherverbrauch für die notwendige Datenumverteilung innerhalb der parallelen Sortierung deutlich reduziert werden kann. Das Verhalten aller entwickelten Verfahren wird jeweils isoliert und im praxisrelevanten Einsatz innerhalb verschiedener Anwendungsprogramme und unter Verwendung unterschiedlicher, insbesondere auch hochskalierbarer Parallelrechner untersucht.

Promovend: Raphael Kunis
Tag der Verteidigung: 20.01.2011
Kurzfassung:

Eine Herausforderung der Parallelverarbeitung ist das Erreichen von Skalierbarkeit großer paralleler Anwendungen für verschiedene parallele Systeme. Das zentrale Problem ist, dass die Ausführung einer Anwendung auf einem parallelen System sehr gut sein kann, die Portierung auf ein anderes System in der Regel jedoch zu schlechten Ergebnissen führt. Durch die Verwendung des Programmiermodells der parallelen Tasks mit Abhängigkeiten kann die Skalierbarkeit für viele parallele Algorithmen deutlich verbessert werden. Die Programmierung mit parallelen Tasks führt zu Task-Graphen mit Abhängigkeiten zur Darstellung einer parallelen Anwendung, die auch als gemischt-parallele Anwendung bezeichnet wird. Die Grundlage für eine effiziente Abarbeitung einer gemischt-parallelen Anwendung bildet ein geeigneter Schedule, der eine effiziente Abbildung der parallelen Tasks auf die Prozessoren des parallelen Systems vorgibt. Für die Berechnung eines Schedules werden Schedulingalgorithmen eingesetzt.

Ein zentrales Problem bei der Bestimmung eines Schedules für gemischt-parallele Anwendungen besteht darin, dass das Scheduling bereits für Single-Prozessor-Tasks mit Abhängigkeiten und ein paralleles System mit zwei Prozessoren NP-hart ist. Daher existieren lediglich Approximationsalgorithmen und Heuristiken um einen Schedule zu berechnen. Eine Möglichkeit zur Berechnung eines Schedules sind layerbasierte Schedulingalgorithmen. Diese Schedulingalgorithmen bilden zuerst Layer unabhängiger paralleler Tasks und berechnen den Schedule für jeden Layer separat. Eine Schwachstelle dieser Schedulingalgorithmen ist das Zusammenfügen der einzelnen Schedules zum globalen Schedule. Der vorgestellte Algorithmus Move-blocks bietet eine elegante Möglichkeit das Zusammenfügen zu verbessern. Dies geschieht durch eine Verschmelzung der Schedules aufeinander folgender Layer.

Obwohl eine Vielzahl an Schedulingalgorithmen für gemischt-parallele Anwendungen existiert, gibt es bislang keine umfassende Unterstützung des Schedulings durch Programmierwerkzeuge. Im Besonderen gibt es keine Schedulingumgebung, die eine Vielzahl an Schedulingalgorithmen in sich vereint. Die Vorstellung der flexiblen, komponentenbasierten und erweiterbaren Schedulingumgebung SEParAT ist der zweite Fokus dieser Dissertation. SEParAT unterstützt verschiedene Nutzungsszenarien, die weit über das reine Scheduling hinausgehen, z.B. den Vergleich von Schedulingalgorithmen und die Erweiterung und Realisierung neuer Schedulingalgorithmen. Neben der Vorstellung der Nutzungsszenarien werden sowohl die interne Verarbeitung eines Schedulingdurchgangs als auch die komponentenbasierte Softwarearchitektur detailliert vorgestellt.

Promovend: Michael Schwind
Tag der Verteidigung: 01.12.2010
Kurzfassung:

In dieser Dissertation werden Programmtransformationen für die Klasse der regulär-irregulären Schleifenkomplexe, welche typischerweise in komplexen Simulationscodes für Vielteilchensysteme auftreten, betrachtet. Dabei wird die Effizienz der resultierenden Programme auf modernen Multicore-Systemen untersucht. Reguläre Schleifenkomplexe zeichnen sich durch feste Schleifengrenzen und eine regelmäßige Struktur der Abhängigkeiten der Berechnungen aus, bei irregulären Berechnungen sind Abhängigkeiten zwischen Berechnungen erst zur Laufzeit bekannt und stark von den Eingabedaten abhängig. Die hier betrachteten regulären-irregulären Berechnungen koppeln beide Arten von Berechnungen eng. Die Herausforderung der effizienten Realisierung regulär-irregulärer Schleifenkomplexe auf modernen Multicore-Systemen liegt in der Kombination von Transformationstechnicken, die sowohl ein hohes Maß an Parallelität erlauben als auch die Lokalität der Berechnungen berücksichtigen.

Moderne Multicore-Systeme bestehen aus einer komplexen Speicherhierachie aus privaten und gemeinsam genutzten Caches, sowie einer gemeinsamen Speicheranbindung. Diese neuen architektonischen Merkmale machen es notwendig Programmtransformationen erneut zu betrachten und die Effizienz der Berechnungen neu zu bewerten. Es werden eine Reihe von Transformationen betrachtet, die sowohl die Reihenfolge der Berechnungen als auch die Reihenfolge der Abspeicherung der Daten im Speicher ändern, um eine erhöhte räumliche und zeitliche Lokalität zu erreichen. Parallelisierung und Lokalität sind eng verknüpft und beeinflussen gemeinsam die Effizienz von parallelen Programmen. Es werden in dieser Arbeit verschiedene Parallelisierungsstrategien für regulär-irreguläre Berechnungen für moderne Multicore-Systeme betrachtet.

Einen weiteren Teil der Arbeit bildet die Betrachtung rein irregulärer Berechnungen, wie sie typisch für eine große Anzahl von Vielteilchensimualtionscodes sind. Auch diese Simulationscodes wurden für Multicore-Systeme betrachtet und daraufhin untersucht, inwieweit diese auf modernen Multicore-CPUs skalieren. Die neuartige Architektur von Multicore-System, im besonderen die in hohem Maße geteilte Speicherbandbreite, macht auch hier eine neue Betrachtung solcher rein irregulärer Berechnungen notwendig. Es werden Techniken betrachtet, die die Anzahl der zu ladenden Daten reduzieren und somit die Anforderungen an die gemeinsame Speicherbandbreite reduzieren.

Promovend: Jörg Dümmler
Tag der Verteidigung: 07.07.2010
Kurzfassung:

Die Ausnutzung von gemischter Parallelität durch parallele Tasks führt im Vergleich mit reiner Datenparallelität und reiner Taskparallelität häufig zu effizienteren und flexibleren parallelen Implementierungen. In der vorliegenden Dissertation wird mit dem CM-task Programmiermodell eine Erweiterung des Standardmodells der parallelen Tasks vorgestellt. Damit wird die Modellierung von Kommunikationsoperationen zwischen zeitgleich ausgeführten parallelen Tasks unterstützt, was zur besseren Strukturierung von parallelen Anwendungen mit einem regelmäßigen Datenaustausch zwischen verschiedenen Programmteilen beiträgt. Für das CM-task Programmiermodell wird das zugehörige Schedulingproblem definiert und ein entsprechender Schedulingalgorithmus vorgestellt. Die Anwendungsentwicklung im CM-task Programmiermodell wird durch das CM-task Compilerframework unterstützt, das eine gegebene plattformunabhängige Spezifiktion eines parallelen Algorithmus schrittweise in ein plattformspezifisches Koordinationsprogramm übersetzt. Das Koordinationsprogramm enthält Programmcode zum Anlegen und Verwalten der benötigten Prozessorgruppen, zum Ausführen der vom Anwender bereitgestellten CM-tasks auf diesen Prozessorgruppen sowie zur Realisierung der benötigten Datenumverteilungsoperationen zwischen den Prozessorgruppen. Der Aufbau und die Schnittstellen des CM-task Compilerframeworks werden in der vorliegenden Dissertation detailliert beschrieben. Anhand verschiedener Anwendungen aus dem wissenschaftlichen Rechnens wird die Einsetzbarkeit des CM-task Programmiermodells und des CM-task Compilerframeworks demonstriert.