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

Titelangaben

Kalinnik, Natalia:
Effizientes Lösen von Anfangswertproblemen gewöhnlicher Differentialgleichungssysteme mithilfe von Autotuning-Techniken.
Bayreuth , 2015 . - XVIII, 202 S.
( Dissertation, 2015 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Angaben zu Projekten

Abstract

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.

Abstract in weiterer Sprache

During the last decades, parallel computer systems with tremendous computational power, thousands of processors and deep and complex memory hierarchies have been developed. Even though modern parallel architectures provide great opportunities to solve computationally intensive problems, their complexity confronts software developers with immense challenges, since the performance of programs strongly depends on the characteristics of the target platform, such as multi-core processor design and cache architecture. To
obtain optimal performance, applications would have to be tuned for each specific target architecture. But the rapidly growing variety of parallel platforms and the fast time to market makes such manual tuning a time-consuming and costly process. The problem of manual tuning is also compounded by the fact that the performance of many programs depends on input data. Consequently, such programs have to be tuned for every possible set of input data.

Auto-tuning is a promising way to avoid manual tuning. The key idea of auto-tuning is the generation of several implementation variants of an algorithm based on program transformations and optimization techniques such as loop
interchange, loop tiling, and scheduling. Then, the variant with the best performance on the target machine is selected from the set of
generated implementation variants.


This work targets auto-tuning for the efficient solution
of initial value problems (IVPs) of systems of ordinary differential equations (ODEs) on modern computer systems.
As an example for solution methods for IVPs, a class of explicit predictor--corrector methods of Runge--Kutta type is considered, which possesses a deeply nested loop
structure with potential for different loop transformations and different types of parallelism.

In this work online auto-tuning algorithms for the sequential and the parallel execution of a given method are presented. Online auto-tuning is supported by offline benchmarks and exploits the time-stepping nature of ODE
methods to selects suitable parameters for variants and the best implementation variant from a candidate pool at runtime during the first time steps.

The auto-tuning algorithms include the selection of suitable tile sizes for implementation variants containing tiled loops. Suitable tile sizes are selected by a combination of an analytical model, based on the working spaces of the loops and regarding the cache organization of the target platform, and an empirical search.