Effiziente Implementierung eingebetteter Runge-Kutta-Verfahren durch Ausnutzung der Speicherzugriffslokalität

Titelangaben

Korch, Matthias:
Effiziente Implementierung eingebetteter Runge-Kutta-Verfahren durch Ausnutzung der Speicherzugriffslokalität.
Bayreuth , 2006
( Dissertation, 2006 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

	Format: PDF Name: korch2006effiziente.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Creative Commons BY 3.0: Namensnennung
	Download (5MB)

Abstract

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.

Abstract in weiterer Sprache

Embedded Runge-Kutta methods are among the most popular numerical solution methods for non-stiff initial value problems of ordinary differential equations. While possessing a simple computational structure, they provide desirable numerical properties and can adapt the step size efficiently. Therefore, embedded Runge-Kutta methods can often compute the solution function faster than other solution methods. However, the computation time required can be very large, particularly for systems with a high dimension. This work considers the efficient implementation of embedded Runge-Kutta methods. It aims at a reduction of the execution time by exploiting the capabilities of modern sequential and parallel computer systems. The most important approach followed is the optimization of the locality of memory references, because on modern computer systems the execution time is often determined by waiting times due to outstanding memory transactions. In this context, several general implementation variants for sequential computer systems are described and investigated with particular regard to the locality behavior. The investigations show that the loop structure of the implementations, which is responsible for the memory reference pattern, has a significant influence on the number of generated cache misses and, hence, on the execution time. Then, using the sequential implementations as a starting point, general parallel implementations for distributed and shared address space are developed, which exploit the potential for parallelism across the system, and their locality and scalability behavior is investigated. The investigations indicate that the locality behavior has a large influence on the scalability of the implementations for shared address space, while the scalability of the implementations for distributed address space is usually limited by the costs of the communication operations. As one possibility to improve the scalability, the applicability of dynamic load balancing techniques is investigated. Such techniques are suitable if the function evaluation costs of the individual components of the ordinary differential equation system are characterized by an unequal distribution or if the integration is performed on a heterogeneous computer system. The runtime experiments performed show that under certain conditions the run time can be reduced even for systems with a nearly equal distribution of the function evaluation costs. Since the general implementations neither possess an optimal locality behavior nor obtain a satisfying scalability, methods are investigated that improve locality and scalability by exploiting special properties of the ordinary differential equation system. A block-based pipelining algorithm is presented, which---under the precondition of a limited access distance of the right hand side function---shows a better locality behavior and a higher scalability when systems of high dimension are integrated. Moreover, the pipelining algorithm can be realized with low storage requirements. Therefore, it is particularly suitable for the integration of semi-discretized partial differential equations that have been derived by the method of lines, which possess a limited access distance and often demand for high storage space. Further, the pipelining algorithm enables the early detection of time steps that will have to be rejected. A parallel implementation for distributed address space can exploit a limited access distance to reduce the communication costs by using single transfer operations instead of global communication operations and by overlapping data transfer times by computations. The better locality behavior of the pipelining algorithm can speed up implementations for shared address space as well as implementations for distributed address space. The approach followed to realize the pipelining algorithm can also be applied to other solution methods, e.g., iterated Runge-Kutta methods.