Reduktion des Kommunikationsaufwands iterierter Runge-Kutta-Verfahren für dünnbesetzte gewöhnliche Differentialgleichungssysteme

Iterierte Runge-Kutta (IRK) Verfahren sind eine Klasse von Lösungsverfahren für Anfangswertprobleme gewöhnlicher Differentialgleichungssysteme (DGL), welche ein hohes Parallelisierungspotential besitzen. Während Implementierungen für dichtbesetzte DGL regelmäßig Vektoren der Größe der DGL austauschen müssen, können spezialisierte Löser Kommunikationskosten einsparen, indem nur die wenigen tatsächlich benötigten Vektorelemente ausgetauscht werden. In dieser Arbeit werden parallele ImplementierIterierte Runge-Kutta (IRK) Verfahren sind eine Klasse von Lösungsverfahren für Anfangswertprobleme gewöhnlicher Differentialgleichungssysteme (DGL), welche ein hohes Parallelisierungspotential besitzen. Während Implementierungen für dichtbesetzte DGL regelmäßig Vektoren der Größe der DGL austauschen müssen, können spezialisierte Löser Kommunikationskosten einsparen, indem nur die wenigen tatsächlich benötigten Vektorelemente ausgetauscht werden. In dieser Arbeit werden parallele Implementierungen von IRK-Verfahren für verteilten Adressraum betrachtet. Es werden zunächst allgemeine Implementierungen für dichtbesetzte DGL vorgestellt. Anschließend wird deren Kommunikation für dünnbesetzte DGL und Probleme mit beschränkter Zugriffsdistanz optimiert. Die entstandenen Implementierungen werden in Hinsicht auf Laufzeit und Skalierbarkeit untersucht. Dafür werden Messungen auf verschiedenen Rechnersystemen mit unterschiedlichen dünnbesetzten DGL ausgewertet. Dabei wird festgestellt, dass eine Implementierung der Kommunikation sowohl für dünnbesetzte DGL als auch für Probleme mit beschränkter Zugriffsdistanz besonders gut geeignet ist.show moreshow less
Iterated Runge-Kutta (IRK) methods are a class of solution methods for initial value problems of systems of ordinary differential equations (ODE) which offer a high level of parallelization. While implementations for dense systems of ODE have to exchange vectors of size of the ODE system regularly, specialized solvers can reduce communication costs by exchanging only the few vector elements that are actually required. In this work, parallel implementations of IRK methods for distributed addreIterated Runge-Kutta (IRK) methods are a class of solution methods for initial value problems of systems of ordinary differential equations (ODE) which offer a high level of parallelization. While implementations for dense systems of ODE have to exchange vectors of size of the ODE system regularly, specialized solvers can reduce communication costs by exchanging only the few vector elements that are actually required. In this work, parallel implementations of IRK methods for distributed address space are considered. At first general implementations for dense ODE systems are presented. Afterwards their communication will be optimized for sparse ODE systems and problems with limited access distance. The resulting implementations are examined in terms of runtime and scalability. Therefore measurements made on different computer systems using different sparse ODE systems will be evaluated. It is found that one implementation option is particularly well suited for sparse ODE systems as well for problems with limited access distance.show moreshow less

Export metadata

  • Export Bibtex
  • Export RIS
  • frontdoor_exportcitavi

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Institutes:Informatik
Author: Markus Straubinger
Year of Completion:2012
Pagenumber:27 S.
Series (Volume number)Bayreuth Reports on Parallel and Distributed Systems (4)
SWD-Keyword:Gewöhnliche Differentialgleichung; MPI <Schnittstelle>; Parallelverarbeitung; Prädiktor-Korrektor-Verfahren; Runge-Kutta-Verfahren
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
CCS-Classification:Parallel and vector implementations (NEW)
MSC-Classification:65L05 Initial value problems
65Y05 Parallel computation
65Y20 Complexity and performance of numerical algorithms [See also 68Q25]
URN:urn:nbn:de:bvb:703-opus4-10169
Document Type:Bachelor Thesis
Language:German
Date of Publication (online):13.12.2012
Licence (German):License Logokeine Lizenz (Deutsches Urhebergesetz)