Parallele Lösung gewöhnlicher Differentialgleichungssysteme mit Hilfe adaptiver Techniken

• Applicant: Professor Dr. Thomas Rauber
• Subject Area: Software Engineering and Programming Languages ; Theoretical Computer Science
• Term: from 2009 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 146845890

• Final Report Year: 2015

Final Report Abstract

Das Ziel des Projekts war der Entwurf von selbstadaptiven parallelen Algorithmen zur Beschleunigung der Lösung von Anfangswertproblemen gewöhnlicher Differentialgleichungssysteme auf aktuellen parallelen Rechnersystemen. Die Berechnungsvorschriften von ODE-Verfahren erlauben i. d. R. die Generierung einer Vielzahl von Implementierungsvarianten, die sich zwar in der Reihenfolge verwendeter Schleifen und den Datenstrukturen unterscheiden, jedoch numerisch äquivalent sind. Aufgrund von Unterschieden in der Schleifenstruktur ändert sich die Reihenfolge der Speicherzugriffe, was dazu führt, dass die Implementierungsvarianten ein unterschiedliches Laufzeit- und Skalierbarkeitsverhalten aufweisen. Welche Implementierungsvariante mit welchen Parametern (z. B. Blockgröße für Loop- Tiling) die schnellste ist, hängt von den Eigenschaften der Zielplattform wie der Cachearchitektur und der Charakteristik des zu lösenden Anfangswertproblems ab. Oft sind die Zusammenhänge komplex, und es müssen ausführliche Laufzeitmessungen durchgeführt werden, um eine effiziente Implementierungsvariante auszuwählen. Dies ist mit einem erheblichen Aufwand verbunden. Die Idee der Selbstadaptionstechniken ist daher, diese Aufgabe in die Software zu integrieren, um so den Nutzer zu entlasten. Im Fokus des Projekts standen explizite ODE-Verfahren. Die Anwendbarkeit der entwickelten selbstadaptiven Techniken auf explizite ODE-Verfahren wurde anhand expliziter Prädiktor-Korrektor-Verfahren (PC-Verfahren) vom Runge-Kutta-Typ (RK-Typ) und Extrapolationsverfahren gezeigt. Um selbstadaptive parallele Techniken und Algorithmen (auch Autotuning-Techniken genannt) für ODE-Verfahren zu entwickeln, wurde folgende Vorgehensweise erfolgreich angewandt: • Für die betrachteten ODE-Verfahren ist eine Auswahlmenge von parallelen Implementierungsvarianten erstellt worden, die sowohl allgemeine als auch für bestimmte Klassen von ODE-Systemen (dünnbesetzt, beschränkte Zugriffsdistanz) spezialisierte Implementierungsvarianten enthält. Die Varianten wurden auf verschiedenen Zielplattformen und für verschiedene ODE-Systeme hinsichtlich ihrer Skalierbarkeit und ihres Lokalitätsverhalten untersucht. Die erstellten Varianten bildeten eine Auswahlmenge, die als Basis für die entwickelten Selbstadaptionstechniken diente. • Es erfolgte eine Untersuchung der Anwendbarkeit des Ansatzes der automatisierten Selektion von Implementierungsvarianten zur Laufzeit am Beispiel sequentieller Varianten der Klasse expliziter PC- Verfahren vom RK-Typ. Daraus entstand ein Grundalgorithmus des Autotunings, der vorerst nur in der Auswahl einer effizienter Implementierungsvariante bestand und die Programmparameter, wie z. B. Blockgröße, unberücksichtigt ließ. Im nächsten Schritt wurde dieser um die automatische Auswahl von Blockgrößen für Loop-Tiling-Varianten ergänzt. • Danach ist ein paralleler selbstadaptiver ODE-Solver für gemeinsamen Adressraum entworfen worden. Die Methode der Blockgrößenauswahl wurde für parallele Implementierungsvarianten weiterentwickelt. Des Weiteren wurde eine Strategie zur Reduktion der Anzahl zu evaluierender Implementierungsvarianten in den selbstadaptiven Solver integriert. Die Strategie basiert auf der Abschätzung der Zeit, die zur Threadsynchronisation benötigt wird. • Es wurde ein selbstadaptiver ODE-Solver für verteilten Adressraum entwickelt. Dieser unterstützt verschiedene Optimierungsmöglichkeiten: die beste Implementierungsvariante kann bezüglich der Laufzeit, des Energieverbrauchs oder des Energy-Delay-Produkts gewählt werden. Zusätzlich bietet dieser die Möglichkeit der automatischen Anpassung der Anzahl parallel rechnender Prozesse zur Minimierung des Energieverbrauchs bzw. der zur Lösung benötigten Laufzeit. • In der Endphase des Projekts ist ein Compilerwerkzeug zur automatischen Generierung von Implementierungsvarianten entworfen worden. Durch den Einsatz der im Projekt entworfenen selbstadaptiven Algorithmen kann die Lösung von Anfangswertproblemen für gewöhnliche Differentialgleichungssysteme beschleunigt und so die Laufzeit von Simulationsexperimenten für diese Art mathematischer Modelle verkürzt werden. Dadurch werden Forschungsergebnisse früher verfügbar bzw. es können komplexere Problemstellungen innerhalb des gleichen Zeitrahmens untersucht werden.

Publications

• Applicability of dynamic selection of implementation variants of sequential iterated Runge-Kutta methods. In 2010 IEEE International Conference on Cluster Computing – Workshops and Tutorials. IEEE, 2010
  N. Kalinnik, M. Korch, and T. Rauber
  
• Mixed-parallel implementations of extrapolation methods with reduced synchronization overhead for large shared-memory computers. In 2010 IEEE 16th International Conference on Parallel and Distributed Systems (ICPADS 2010), pages 131–138. IEEE, 2010
  M. Korch, T. Rauber, and C. Scholtes
  
• Scalability and locality of extrapolation methods for distributed-memory architectures. In Proc. Euro-Par 2010, Part II, number 6272 in LNCS, pages 65–76. Springer, 2010
  M. Korch, T. Rauber, and C. Scholtes
  
• An efficient time-step-based self-adaptive algorithm for predictor-corrector methods of Runge-Kutta type. J. Computational Applied Mathematics, 236(3):394–410, 2011
  N. Kalinnik, M. Korch, and T. Rauber
  
• Dynamic selection of implementation variants of sequential iterated Runge-Kutta methods with tile size sampling. In Proceedings of the Second Joint WOSP/SIPEW International Conference on Performance Engineering, pages 189–200. ACM, 2011
  N. Kalinnik, M. Korch, and T. Rauber
  
• Memory-intensive applications on a many-core processor. In IEEE 13th International Conference on High Performance Computing and Communications (HPCC), pages 126–134, Los Alamitos, CA, USA, sept. 2011. IEEE
  M. Korch, T. Rauber, and C. Scholtes
  
• Parallel low-storage Runge-Kutta solvers for ODE systems with limited access distance. International Journal of High Performance Computing Applications, 25(2):236– 255, 2011
  M. Korch and T. Rauber
  
• Scalability and locality of extrapolation methods on large parallel systems. Concurrency and Computation: Practice and Experience, Volume 23, Issue 15, October 2011, Pages 1789-1815
  M. Korch, T. Rauber, and C. Scholtes
  (See online at https://doi.org/10.1002/cpe.1765)
• Diamond-like tiling schemes for efficient explicit Euler on GPUs. In 11th International Symposium on Parallel and Distributed Computing (ISPDC 2012), pages 259–266, 2012. Best paper award
  M. Korch, J. Kulbe, and C. Scholtes
  
• Exploiting limited access distance of ODE systems for parallelism and locality in explicit methods. In ALGORITMY 2012. 19th Conference on Scientific Coputing, Vysoké Tatry – Podbanské, Slovakia, September 9–14, 2012. Proceedings, pages 250– 260. Slovak University of Technology in Bratislava, Faculty of Civil Engineering, Department of Mathematics and Descriptive Geometry, 2012
  M. Korch
  
• Locality improvement of data-parallel Adams–Bashforth methods through blockbased pipelining of time steps. In Euro-Par 2012. Parallel Processing, number 7484 in LNCS, pages 563–574. Springer, 2012
  M. Korch
  
• Online auto-tuning for the time-step-based parallel solution of ODEs on shared-memory systems. J. Parallel Distrib. Computing, 74(8):2722–2744, 2014
  N. Kalinnik, M. Korch, and T. Rauber
  (See online at https://doi.org/10.1016/j.jpdc.2014.03.006)