Effizientes Lösen von Anfangswertproblemen gewöhnlicher Differentialgleichungssysteme mithilfe von Autotuning-Techniken

Während der letzten Jahrzehnte sind parallele Computersysteme mit enormer Rechenleistung, Tausenden von Prozessoren und immer tieferen und komplexeren Speicherhierarchien entwickelt worden. Wenngleich ihre Nutzung die Möglichkeit schafft, extrem rechenintensive Probleme zu lösen, stellt ihre zunehmende Komplexität die Software-Entwickler vor immense Herausforderungen, da die Leistung eines Programms sehr stark von den Eigenschaften der Zielplattform, wie Multicore- und Cache-Architektur, abhängt. Aufgrund dessen muss der Programmcode für jede einzelne Zielplattform optimiert werden, damit eine hohe Programmleistung erreicht werden kann. Die rapid wachsende Vielfalt an unterschiedlichen parallelen Plattformen und ihre schnelle Markteinführung macht jedoch das manuelle Optimieren des Programmcodes, auch manuelles Tuning genannt, zu einem zeitraubenden und kostspieligen Prozess. Zusätzlich wird das manuelle Tuning dadurch erschwert, dass die Leistung vieler Programme von den Eingabedaten abhängt. Folglich müssen solche Programme obendrein für jede mögliche Kombination von Eingabedaten optimiert werden. Automatisches Tuning von Software (Autotuning) ist eine vielversprechende Technik, um ein manuelles Tuning zu vermeiden. Die Grundidee des Autotunings besteht darin, mehrere Varianten eines Programms basierend auf Programmtransformationen und Optimierungstechniken wie Loop-Interchange, Loop-Tiling oder Scheduling (Ablaufplanung) zu erzeugen. Dann wird aus generierten Varianten die Variante mit der besten Laufzeit auf der Zielplattform gewählt. Diese Arbeit befasst sich mit dem Entwurf von Autotuning-Techniken zur Beschleunigung der Lösung von Anfangswertproblemen gewöhnlicher Differentialgleichungssysteme auf modernen Computersystemen. Dazu wird eine ausgewählte Klasse von Lösungsverfahren für nicht steife Anfangswertprobleme gewöhnlicher Differentialgleichungen (ODEs), nämlich eine Klasse expliziter Prädiktor-Korrektor-Verfahren vom Runge-Kutta-Typ, betrachtet. Die Umsetzung der Berechnungsvorschrift dieser Verfahren führt zu einer tief verschachtelten Schleifenstruktur, die ein großes Potenzial unterschiedlicher Schleifentransformationen und verschiedener Arten von Parallelität besitzt. In dieser Dissertation werden Online-Autotuning-Algorithmen für die sequentielle und die parallele Ausführung der betrachteten Verfahren vorgestellt. Das Online-Autotuning wird durch Offline-Benchmarks unterstützt und nutzt die zeitschrittorientierte Berechnungsstruktur von ODE-Verfahren aus, um zur Laufzeit geeignete Programmparameter und die schnellste Implementierungsvariante auf der Zielplattform zu wählen. Die präsentierten Autotuning-Algorithmen beinhalten eine Methode zur automatischen Auswahl geeigneter Blockgrößen für Implementierungsvarianten mit Loop-Tiling. Geeignete Blockgrößen werden durch eine Kombination aus einem analytischen Modell, basierend auf der Berechnung der Größe von Arbeitsräumen und unter Berücksichtigung von Eigenschaften der Cache-Hierarchie der Zielplattform, und einer empirischen Suche bestimmt.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bayreuth

Year

2015

Author dc:creator

• Kalinnik, Natalia

Contributors dc:contributor

• Rauber, Thomas

Repository record source_url

https://epub.uni-bayreuth.de/id/eprint/2034/

OAI identifier oai:identifier

oai:epub.uni-bayreuth.de:2034