Doctoral candidate: Robert Dietze
Colloquium on: 26.04.2022
Abstract (german only):

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 Systemenmodelliert 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.

Doctoral candidate: Thomas Jakobs
Colloquium on: 10.12.2021
Abstract (german only):

Neben einer kurzen Ausführungszeit rückt bei der Optimierung von Anwendungen und Algorithmen ein geringer Energieverbrauch der genutzten Rechenressourcen in den Fokus der aktuellen Forschung. Eine hohe Energie-Effizienz von Programmen wird dabei erreicht, indem der Energieverbrauch von Programmen und Technologien reduziert wird, ohne dafür die Ausführungszeit übermäßig zu erhöhen. Im parallelen wissenschaftlichen Rechnen ist der Bedarf an energie-effizienten Programmausführungen vor allem für Algorithmen der linearen Algebra gegeben, die als Unterfunktionen in einer Vielzahl von Anwendungen eingesetzt werden. Die Vektorisierung von Programmen durch die Prozessor- und Instruktionssatzerweiterung AVX zeigt Potenzial zur energie-effizienten Ausführung von Algorithmen der linearen Algebra, wobei die erzielte Energie-Effizienz von der Umsetzung der Implementierung abhängt.

Für die gezeigten Untersuchungen werden drei repräsentativ ausgewählte Algorithmen der linearen Algebra für die Ausführung auf AVX-Vektoreinheiten genutzt. Bei der AVX-Vektorisierung der Algorithmen werden verschiedene Programmvarianten erstellt, mit denen Ausführungszeit und Energieverbrauch bei der Ausführung ermittelt werden. Die Programmvarianten unterscheiden sich dabei unter anderem in der Anwendung von Programmtransformationen, wie Loop Tiling oder einer veränderten Speicherzugriffsstruktur. Zusätzlich wird gezeigt, wie die Umsetzung verschiedener Programmieransätze, wie Autovektorisierung oder unterschiedlicher Instruktionssätze, sowie Implementierungsvarianten durch die Auswahl der verwendeten Instruktionen, die Ausführungszeit und den Energieverbrauch der Programmausführung beeinflussen. Die so erstellten Programmvarianten werden auf modernen Prozessoren verschiedener Architekturfamilien mit unterschiedlichen Ausführungsparametern, wie der eingestellten Prozessorfrequenz, ausgeführt. Die Untersuchungen zeigen, dass sich Ausführungszeit und Energieverbrauch von Programmen durch die Vektorisierung reduzieren lassen. Die Auswahl der Programmtransformationen, des Programmieransatzes und der Ausführungsparameter für die energie-effiziente Ausführung von vektorisierten Programmen kann dabei anwendungsspezifisch aufgrund der Eigenschaften des ausgewählten Algorithmus getroffen werden.

Doctoral candidate: Jens Lang
Colloquium on: 09.12.2014
Abstract (german only):

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.

Doctoral candidate: Thomas Reichel
Colloquium on: 11.11.2013
Abstract (german only):

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.

Doctoral candidate: Michael Hofmann
Colloquium on: 09.03.2012
Abstract (german only):

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.

Doctoral candidate: Raphael Kunis
Colloquium on: 20.01.2011
Abstract (german only):

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.

Doctoral candidate: Michael Schwind
Colloquium on: 01.12.2010
Abstract (german only):

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.

Doctoral candidate: Jörg Dümmler
Colloquium on: 07.07.2010
Abstract (german only):

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.