TU Darmstadt / ULB / TUbiblio

Numerical Investigation of Parallel-in-Time Methods for Dominantly Hyperbolic Equations

Schmitt, Andreas (2018):
Numerical Investigation of Parallel-in-Time Methods for Dominantly Hyperbolic Equations.
Darmstadt, Technische Universität, [Online-Edition: https://tuprints.ulb.tu-darmstadt.de/8328],
[Ph.D. Thesis]

Abstract

Simulations aid in many scientific and industrial applications. A general ambition for these simulations is to keep the time-to-solution as small as possible while maintaining a desired accuracy. Besides with high computational power, this can be achieved by employing multiple processing units with parallelization. Today’s state of the art is the spatial parallelization which provides a very good parallel efficiency.

However, such a parallelization introduces communication and synchronization overheads leading to a maximal number of processing units which can be used efficiently. Applying a parallelization in time on top of the parallelization in space makes using more processing units possible. An issue of the parallel-in-time methods is their problem dependent efficiency. It tends to be generally bad for dominantly hyperbolic problems. The viscous Burgers equation, which for small viscosities falls into that category, is used to investigate two methods of parallelization in time.

First, a look is taken at the Adomian decomposition method (ADM) and possibilities of exploiting additional degrees of parallelism within this method. Its viability is questioned by comparing its discrete version (DADM) to the explicit Runge-Kutta method (ERK). The comparison shows similar restric- tions regarding their maximal time step size for both methods. Furthermore, the DADM leads to larger errors with increasing order of accuracy compared to the ERK. However, discussing the parallelization within the DADM shows a reduction of the runtime complexity from quadratic to linear is possible. With this reduction in the runtime DADM seems to be a viable competitor to the ERK. This is especially true for high-order schemes, as fewer function evaluations have to be run serial. Increasing the order of accuracy is also embarrassingly easy with the DADM compared to the ERK.

The second method investigated in this thesis is the Parareal algorithm. Here, the focus lies on the potential of the implicit Runge-Kutta method with semi-Lagrangian advection (SLIRK) as the coarse solver for the Parareal algorithm. Its potential compared to using the explicit Runge-Kutta method (ERK) and the implicit-explicit Runge-Kutta method (IMEX) is tested with three different benchmarks. The comparison shows the ERK is in contrast to the other two methods not able to provide speedup potential with the chosen benchmarks. For advection dominated problems SLIRK performs better than IMEX due to its stability. The stability of SLIRK leads to speedup potential for a larger range of viscosities with the Parareal algorithm. Still, the instability of Parareal itself causes a decreasing potential with a decreasing viscosity. With an inviscid case the number of iterations to convergence for Parareal is too large to yield a reasonable speedup. An additional result worth mentioning is it was possible to show the importance of predicting the phase of the solution correctly for the convergence of Parareal.

Item Type: Ph.D. Thesis
Erschienen: 2018
Creators: Schmitt, Andreas
Title: Numerical Investigation of Parallel-in-Time Methods for Dominantly Hyperbolic Equations
Language: English
Abstract:

Simulations aid in many scientific and industrial applications. A general ambition for these simulations is to keep the time-to-solution as small as possible while maintaining a desired accuracy. Besides with high computational power, this can be achieved by employing multiple processing units with parallelization. Today’s state of the art is the spatial parallelization which provides a very good parallel efficiency.

However, such a parallelization introduces communication and synchronization overheads leading to a maximal number of processing units which can be used efficiently. Applying a parallelization in time on top of the parallelization in space makes using more processing units possible. An issue of the parallel-in-time methods is their problem dependent efficiency. It tends to be generally bad for dominantly hyperbolic problems. The viscous Burgers equation, which for small viscosities falls into that category, is used to investigate two methods of parallelization in time.

First, a look is taken at the Adomian decomposition method (ADM) and possibilities of exploiting additional degrees of parallelism within this method. Its viability is questioned by comparing its discrete version (DADM) to the explicit Runge-Kutta method (ERK). The comparison shows similar restric- tions regarding their maximal time step size for both methods. Furthermore, the DADM leads to larger errors with increasing order of accuracy compared to the ERK. However, discussing the parallelization within the DADM shows a reduction of the runtime complexity from quadratic to linear is possible. With this reduction in the runtime DADM seems to be a viable competitor to the ERK. This is especially true for high-order schemes, as fewer function evaluations have to be run serial. Increasing the order of accuracy is also embarrassingly easy with the DADM compared to the ERK.

The second method investigated in this thesis is the Parareal algorithm. Here, the focus lies on the potential of the implicit Runge-Kutta method with semi-Lagrangian advection (SLIRK) as the coarse solver for the Parareal algorithm. Its potential compared to using the explicit Runge-Kutta method (ERK) and the implicit-explicit Runge-Kutta method (IMEX) is tested with three different benchmarks. The comparison shows the ERK is in contrast to the other two methods not able to provide speedup potential with the chosen benchmarks. For advection dominated problems SLIRK performs better than IMEX due to its stability. The stability of SLIRK leads to speedup potential for a larger range of viscosities with the Parareal algorithm. Still, the instability of Parareal itself causes a decreasing potential with a decreasing viscosity. With an inviscid case the number of iterations to convergence for Parareal is too large to yield a reasonable speedup. An additional result worth mentioning is it was possible to show the importance of predicting the phase of the solution correctly for the convergence of Parareal.

Place of Publication: Darmstadt
Divisions: 16 Department of Mechanical Engineering
16 Department of Mechanical Engineering > Institute of Numerical Methods in Mechanical Engineering (FNB)
Exzellenzinitiative
Exzellenzinitiative > Graduate Schools
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
Date Deposited: 10 Feb 2019 20:55
Official URL: https://tuprints.ulb.tu-darmstadt.de/8328
URN: urn:nbn:de:tuda-tuprints-83286
Referees: Schäfer, Prof. Dr. Michael and Schöps, Prof. Dr. Sebastian
Refereed / Verteidigung / mdl. Prüfung: 10 October 2018
Alternative Abstract:
Alternative abstract Language
Viele wissenschaftliche und industrielle Anwendungen werden von Simulationen unterstützt. Bei diesen Simulationen ist eine so gering wie mögliche Laufzeit bei einer vorgegebenen Genauigkeit gewünscht. Außer durch hohe Rechenleistung kann dies durch die Nutzung mehrerer Recheneinheiten mit Hilfe von Parallelisierung verringert werden. Derzeitiger Stand der Technik ist eine Parallelisierung im Raum, welche eine gute Effizienz aufweist. Eine Parallelisierung erfordert jedoch unweigerlich Kommunikations- und Synchronisierungs-Overheads, welche zu einer maximalen Anzahl an Recheneinheiten führen, die effizient genutzt werden können. Ein Anwenden der Zeitparallelisierung zusätzlich zur räumlichen Parallelisierung kann die Effizienzgrenze allerdings weiter nach oben verschieben. Die Effizienz der Zeitparallelisierung ist jedoch abhängig von der Anwendung. Insbesondere Probleme, die vorwiegend hyperbolischer Natur sind, führen zu schlechter Effizienz. Anhand der viskosen Burgersgleichung, welche für kleine Viskositäten solch ein Problem ist, werden zwei Methoden der Zeitparallelisierung untersucht. Zunächst wird die Möglichkeit einer Parallelisierung der Adomian decomposition method (ADM) untersucht. Da es sich bei der diskreten Version (DADM) der ADM um ein explizites Zeitschrittverfahren handelt, wird die Brauchbarkeit der DADM in einem Vergleich zur etablierten expliziten Runge-Kutta Methode (ERK) untersucht. Der Vergleich zeigt, dass beide Methoden einen sehr ähnlichen maximalen Zeitschritt zulassen. Bei ansteigender Verfahrensordnung führt die DADM zu einem größeren Fehler verglichen mit der ERK. Mit der gezeigten Parallelisierung der DADM ist es möglich die quadratische Laufzeitkomplexität auf eine lineare zu verringern. Dies führt dazu, dass die DADM mit der ERK konkurrieren kann. Insbesondere in Fällen mit hoher Verfahrensordnung ist die geringere Anzahl von Funktionsauswertungen die seriell ablaufen ein Vorteil der DADM. Verglichen mit der ERK ist es sehr einfach die Verfahrensordnung der DADM zu erhöhen. Die zweite untersuchte Methode ist der Parareal Algorithmus. Hierbei wird ein besonderes Augenmerk darauf gelegt, welches Potential die implizite Runge-Kutta Methode mit einer semi-Lagrangian Advektion (SLIRK) als Groblöser des Parareal Algorithmus besitzt. Hierfür wird ein Vergleich mit der expliziten Runge-Kutta Methode (ERK) und der impliziten-expliziten Runge-Kutta Methode (IMEX) auf Basis von drei Benchmarks durchgeführt. Dieser Vergleich zeigt, dass die ERK in den getesteten Fällen kein Speedup Potential besitzt. Bei kleinen Viskositäten, welche der Gleichung einen vorwiegend hyperbolischen Charakter geben, ist die SLIRK klar im Vorteil gegenüber der IMEX, da die SLIRK stabiler ist. Auf Grund dieser Stabilität führen mehr Viskositäten zu Speedup Potential mit dem Parareal Algorithmus. Ein Verringern der Viskosität resultiert jedoch in einem Anstieg der Zahl der Iterationen zur Konvergenz von Parareal durch die Instabilität von Parareal. Im Fall der Burgersgleichung ohne Viskosität kann kein Potential für Speedup gefunden werden. Zusätzlich ist zu Erwähnen, dass die korrekte Vorhersage der Phase der Lösung wichtig ist für eine schnelle Konvergenz von Parareal.German
Export:

Optionen (nur für Redakteure)

View Item View Item