Scalability analysis of parallel algorithms for solving ordinary differential equations
Final Report Abstract
Das Projekt hatte zum Ziel, existierende parallele Algorithmen zur Lösung gewöhnlicher Differentialgleichungssysteme hinsichtlich ihrer Skalierbarkeits- und Lokalitätseigenschafton zu analysieren und, aufbauend auf den gewonnenen Erkenntnissen, verbesserte Algorithmen zu entwickeln und diese portabel und effizient zu implementieren. Ein großer Teil der durchgeführten Untersuchungen konzentrierte sich auf eingebettete Runge-Kutta- Verfahren, da diese eine große praktische Bedeutung besitzen und sie sich aufgrund ihrer im Vergleich zu ianderen Verfahren einfacheren Berechnungsstruktur sehr gut als Ausgangspunkt für das Projekt eigneten. Neben eingebetteten Runge-Kutta-Verfahren wurden auch iterierte Runge-Kutta-Verfahren, Extrapolationsverfahren und Adams-Verfahren betrachtet. Um die Laufzeit von parallelen Lösungsverfahren für gewöhnliche Differentialgleichungssysteme zu reduzieren, wurden folgende Vorgehensweisen erfolgreich angewandt: 1. Verbesserung der Lokalitätseigenschaften: Durch die Verbesserung der Lokalitätseigenschaften kann eine Reduzierung der Anzahl der Cache-Fehlzugriffe und, daraus folgend, in der Regel eine Verbesserung der Laufzeit und auf parallelen Rechnersystemen eine Verbesserung der Skalierbarkeit erreicht werden. Als Beispiele hierfür wurden hauptsächlich eingebettete Runge-Kutta-Verfahren betrachtet. Aber auch sequentielle Implementierungen iterierter Runge-Kutta-Verfahren wurden untersucht. Um eine Verbesserung der Lokalitätseigenschaften zu erreichen, wurden verschiedene Transformaitionen auf Programmebene untersucht, die insbesondere eine Modifikation der Schleifenstruktur sowie eine Veränderung der Datenstrukturen beinhalteten. 2. Optimierung der Interprozessorkommunikation: Die Kommunikationskosten üben häufig einen entscheidenden Einfluß auf die Skalierbarkeit eines Programmes aus. Es wurde deshalb ein Vergleich verschiedener Programmierumgebungen durchgeführt, in welchem die Eignung von MPI, Pthreads und JavaThreads für die Implementierung von iterierten und eingebetteten Runge-Kutta-Verfahren •untersucht wurden. Weiterhin wurden spezialisierte Implementierungen eingebetteter Runge-Kutta- Verfahren entwickelt, die durch Verwendung eines gemischten Programmiermodells auf die Ausnutzung der spezifischen Eigenschaften von SMP-Clustern zielen. 3. Ausnutzung spezifischer Eigenschaften des gewöhnlichen Differentialgleichungssystems: Weiterführende Programmtransformationen sind möglich, wenn das Lösungsverfahren spezifische Eigenschaften des gewöhnlichen Differentialgleichungssystems ausnutzen kann. Am Beispiel eingebetteter Runge-Kutta-Verfahren wurde gezeigt, wie durch die Ausnutzung einer beschränkten Zugriffsdistanz eine erhebliche Reduzierung des Arbeitsraumes und somit eine Verbesserung des Lokalitätsverihaltens erreicht werden kann. Darüber hinaus wurde gezeigt, wie eine beschränkte Zugriffsdistanz zur Reduzierung des Kommunikationsaufwandes ausgenutzt werden kann. Die vorgeschlagenen Techniken können in modifizierter Form z. B. auch auf iterierte Runge-Kutta-Verfahren angewendet werden. 4. Vermeidung von Wartezeiten durch dynamische Verteilung der Berechnungen: Synchronisationsibedingte Wartezeiten können in bestimmten Fällen durch die Anwendung von Techniken, die eine dynamische Verteilung der auszuführenden Berechnungen durchführen, verringert werden. Dies wurde am Beispiel eingebetteter Runge-Kutta-Verfahren demonstriert. 5. Ausnutzung mehrstufiger Parallelität: Viele Lösungsverfahren besitzen ein mehrstufiges Parallelitätspotential, z.B. für Instruktionsparallelität, Datenparallelität und gegebenenfalls mehrere Ebenen der Taskparallelität. Die Ausnutzung dieses Potentials kann eine Reduzierung der Laufzeit und eine Verbesserung der Skalierbarkeit ermöglichen, z.B. durch Verwendung einer geeigneten Aufteilung der Prozessoren in mehrere Gruppen und den Austausch globaler Kommunikationsoperationen durch effizientere gruppenbasierte Kommunikationsoperationen. Durch die Beschleunigung von Lösungsverfahren für gewöhnliche Differentialgleichungssysteme kann 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
-
KORCH, Matthias; RAUBER, Thomas: Applicability of Load Balancing Strategies to Data-Parallel Embedded Runge-Kutta Integrators. In: Euro-Par 2006. Parallel Processing (LNCS 4128), Springer- Verlag, August 2006, S. 720-729
-
KORCH, Matthias; RAUBER, Thomas: Comparison of Parallel Implementations of Runge-Kutta Solvers: Message Passing vs. Threads. In: Parallel Computing: Software Technology, Algorithms, Architectures & Applications - Proceedings of the International Conference ParCo2003, Dresden, Germany Bd. 13. Elsevier, September 2004, S. 209-216
-
KORCH, Matthias; RAUBER, Thomas: Optimizing Locality and Scalability of Embedded Runge- Kutta Solvers Using Block-Based Pipelining. In: Journal of Parallel and Distributed Computing 6 (2006), März, Nr. 3, S. 444-468
-
KORCH, Matthias; RAUBER, Thomas: Scalable Parallel RK Solvers for DDEs Derived by the Method of Lines. In: Euro-Par 2003. Parallel Processing (LNCS 2790), Springer-Verlag, August 2003, S. 830-839
-
KORCH, Matthias; RAUBER, Thomas: Simulation-based analysis of parallel Runge-Kutta solvers. In: Applied Parallel Computing: State of the Art in Scientific Computing. 7th International Workshop, PARA 2004, Lyngby, Denmark, June 2004. Revised Selected Papers, Springer-Verlag, 2006 (LNCS 3732), S. 1105-1114
-
KORCH, Matthias; RAUBER, Thomas; RÜNGER, Gudula: Performance Optimization of RK Methods Using Block-based Pipelining. In: GETOV, V. (Hrsg.); GERNDT, M. (Hrsg.); HOISIE, A. (Hrsg.); MALONY, A. (Hrsg.); MILLER, B. (Hrsg.): Performance Analysis and Grid Computing. Kluwer Academic Publishers, Oktober 2003, S. 41-56
-
KORCH, Matthias; RAUBER, Thomas; RÜNGER, Gudula: Pipelining for Locality Improvement in RK ! Methods. In: Euro-Par 2002. Parallel Processing (LNCS 2400), Springer-Verlag, 2002, S. 724-733
-
RAUBER, T.; RÜNGER, G.: Improving Locality for ODE Solvers by Program Transformations. In: Scientific Programming 12 (2004), Nr. 3, S. 133-154
-
RAUBER, Thomas; RÜNGER, Gudula: Execution Schemes for Parallel Adams Methods. In: Euro-Par 2004. Parallel Processing (LNCS 3149). Pisa, Italy: Springer-Verlag, September 2004, S. 708-717
-
RAUBER, Thomas; RÜNGER, Gudula: Exploiting Multiple Levels of Parallelism in Scientific Computing. In: DONCESCU, A. (Hrsg.); LENG, T. (Hrsg.); Nc, M. K. (Hrsg.); YANG, L. T. (Hrsg.): High Performance Computational Science and Engineering: IFIP TC5 Workshop on High Performance Computational Science and Engineering (HPCSE), World Computer Congress. Toulouse, France: Springer, 2005 (IFIP International Federation for Information Processing 172), S. 3-19
-
RAUBER, Thomas; RÜNGER, Gudula: Optimizing Locality for ODE Solvers. In: Proceedings of the 15th ACM International Conference on Supercomputing, ACM Press, 2001, S. 123-132
