-
Effiziente Implementierung eingebetteter Runge-Kutta-Verfahren durch Ausnutzung der Speicherzugriffslokalität
(2006)
- Eingebettete Runge-Kutta-Verfahren zählen zu den numerischen Lösungsverfahren für nichtsteife Anfangswertprobleme gewöhnlicher Differentialgleichungssysteme. Sie werden in der Praxis häufig eingesetzt, da sie gute numerische Eigenschaften aufweisen, eine effiziente Steuerung der Schrittweite ermöglichen und aufgrund ihrer Berechnungsstruktur oft schneller die gesuchte Lösung berechnen können als alternative Verfahren. Der erforderliche Berechnungsaufwand ist dennoch sehr hoch, insbesondere für Systeme großer Dimension. Diese Arbeit beschäftigt sich mit der effizienten Implementierung eingebetteter Runge-Kutta-Verfahren. Das Ziel ist es, durch eine möglichst gute Ausnutzung der Leistungsfähigkeit moderner sequentieller und paralleler Rechnersysteme die erforderliche Berechnungszeit weitestgehend zu reduzieren. Der wichtigste Ansatzpunkt dazu ist die Optimierung der Speicherzugriffslokalität, da die Programmlaufzeit auf modernen Rechnersystemen häufig durch Wartezeiten aufgrund ausstehender Speichertransaktionen bestimmt wird. Diesbezüglich werden zunächst verschiedene allgemeine Implementierungsvarianten für sequentielle Rechnersysteme beschrieben und ausführlich hinsichtlich ihres Lokalitätsverhaltens untersucht. Die Untersuchungen zeigen, daß die Schleifenstruktur der Implementierungen aufgrund des daraus hervorgehenden Speicherzugriffsmusters einen signifikanten Einfluß auf die Anzahl der erzeugten Cache-Fehlzugriffe und somit auch auf die Laufzeit ausübt. In Anlehnung an die sequentiellen Implementierungsvarianten werden im Anschluß allgemeine parallele Implementierungsvarianten für verteilten und für gemeinsamen Adreßraum, die das Parallelitätspotential bezüglich der Komponenten des Differentialgleichungssystems ausnutzen, entwickelt und ebenfalls hinsichtlich ihres Lokalitätsverhaltens und ihrer Skalierbarkeit untersucht. Die durchgeführten Untersuchungen machen deutlich, daß das Lokalitätsverhalten einen großen Einfluß auf die Skalierbarkeit der Implementierungen für gemeinsamen Adreßraum besitzt, während die Skalierbarkeit der Implementierungen für verteilten Adreßraum in der Regel durch die Kosten der Kommunikationsoperationen begrenzt wird. Als eine Möglichkeit zur Verbesserung der Skalierbarkeit wird der Einsatz von Techniken zur dynamischen Lastbalancierung untersucht. Der Einsatz solcher Techniken ist immer dann sinnvoll, wenn eine ungleichförmige Verteilung der Funktionsauswertungskosten bezüglich der einzelnen Komponenten des Differentialgleichungssystems vorliegt oder die Berechnung auf einem heterogenen Rechnersystem durchgeführt wird. Die durchgeführten Laufzeitexperimente zeigen, daß unter bestimmten Voraussetzungen aber auch für Differentialgleichungssysteme mit nahezu ausgeglichenen Funktionsauswertungskosten ein Laufzeitgewinn erzielt werden kann. Da allgemeine Implementierungen weder ein optimales Lokalitätsverhalten besitzen noch eine zufriedenstellende Skalierbarkeit erreichen können, werden Möglichkeiten untersucht, Lokalität und Skalierbarkeit durch eine Spezialisierung bezüglich des Differentialgleichungssystems zu verbessern. Es wird ein blockbasierter Pipelining-Algorithmus vorgestellt, der unter der Voraussetzung, daß die rechte Seite eine beschränkte Zugriffsdistanz besitzt, bei der Integration von Differentialgleichungssystemen mit großer Dimension ein besseres Lokalitätsverhalten als die allgemeinen Implementierungen aufweist. Darüber hinaus kann der Pipelining-Algorithmus mit einem geringen Speicherplatzbedarf realisiert werden. Er eignet sich deshalb gut für die Integration mittels Linienmethode semi-diskretisierter partieller Differentialgleichungssysteme, die eine beschränkte Zugriffsdistanz besitzen und häufig einen hohen Speicherplatzbedarf aufweisen. Weiterhin ermöglicht der Pipelining-Algorithmus das frühzeitige Erkennen von Zeitschritten, die verworfen werden müssen. Bei einer parallelen Implementierung für verteilten Adreßraum kann die beschränkte Zugriffsdistanz ausgenutzt werden, um den Kommunikationsaufwand zu reduzieren, indem Einzeltransferoperationen anstelle von globalen Kommunikationsoperationen eingesetzt werden und Datenübertragungszeiten durch Berechnungen überdeckt werden. Von dem verbesserten Lokalitätsverhalten des Pipelining-Algorithmus können sowohl parallele Implementierungen für gemeinsamen Adreßraum als auch parallele Implementierungen für verteilten Adreßraum profitieren. Der zur Realisierung des Pipelining-Algorithmus verfolgte Ansatz läßt sich auf weitere Verfahren, wie z.B. iterierte Runge-Kutta-Verfahren, übertragen.
-
Parallel Low-Storage Runge-Kutta Solvers for ODE Systems with Limited Access Distance
(2010)
- We consider the solution of initial value problems (IVPs) of large systems of ordinary differential equations (ODEs) for which memory space requirements determine the choice of the integration method. In particular, we discuss the space-efficient sequential and parallel implementation of embedded Runge-Kutta (RK) methods. We focus on the exploitation of a special structure of commonly appearing ODE systems, referred to as "limited access distance", to improve scalability and memory usage. Such systems may arise, for example, from the semi-discretization of partial differential equations (PDEs). The storage space required by classical RK methods is directly proportional to the dimension n of the ODE system and the number of stages s of the method. We propose an implementation strategy based on a pipelined processing of the stages of the RK method and show how the memory usage of this computation scheme can be reduced to less than three storage registers by an overlapping of vectors without compromising the choice of method coefficients or the potential for efficient stepsize control. We analyze and compare the scalability of different parallel implementation strategies in detailed runtime experiments on different parallel architectures.
