TU Darmstadt / ULB / TUprints

Entwicklung und Evaluierung von Parallelisierungsstrategien für Particle-In-Cell Simulationen auf Multicomputern

Wolfheimer, Felix (2008)
Entwicklung und Evaluierung von Parallelisierungsstrategien für Particle-In-Cell Simulationen auf Multicomputern.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
dissertation.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Entwicklung und Evaluierung von Parallelisierungsstrategien für Particle-In-Cell Simulationen auf Multicomputern
Language: German
Referees: Weiland, Prof. Dr.- Thomas ; Schäfer, Prof. Dr.- Michael
Date: 20 August 2008
Place of Publication: Darmstadt
Date of oral examination: 10 July 2008
Abstract:

Der Particle-In-Cell Algorithmus kann zur numerischen Berechnung der Dynamik von Vielteilchensystemen herangezogen werden, wie sie beispielsweise in der Plasma- und der Beschleunigerphysik auftreten. Für viele praxisrelevante Problemstellungen erfordert eine 3D Simulation jedoch so viele Rechnerressourcen, dass sie auf einem gewöhnlichen Arbeitsplatzrechner nicht durchführbar ist. Unter Rechnerressourcen sind hier der Bedarf an Arbeitsspeicher sowie die Anzahl der Rechenoperationen zu verstehen, welche zur Lösung des Simulationsproblems benötigt werden. Ein Parallelrechner, welcher sich aus mehreren miteinander vernetzten Einzelrechnern zusammensetzt, ein sogenannter Multicomputer, bietet die Möglichkeit diesem Problem zu begegnen und ausreichende Ressourcen zur Lösung derartiger Simulationsprobleme bereitzustellen. Die Nutzung eines Multicomputers erfordert die Parallelisierung der verwendeten Algorithmen, das heißt, dass sämtliche von dem Algorithmus durchzuführende Rechenoperationen den verfügbaren Verarbeitungseinheiten (Prozessoren) des Parallelrechners zugeordnet werden müssen. Ebenso müssen alle während der Simulation erzeugten Daten auf die Speichermodule der Einzelrechner des Multicomputers verteilt werden. Sowohl die Zuordnung der Rechenoperationen als auch diejenige der Simulationsdaten ist entscheidend für eine optimale Nutzung der durch den Parallelrechner zur Verfügung stehenden Ressourcen und entscheidet auch oftmals darüber, ob eine Berechnung überhaupt durchführbar ist. Diese Zuordnung muss vom Programmentwickler unter Berücksichtigung der Architekturmerkmale des Parallelrechners vorgenommen werden. In der vorliegenden Arbeit werden, nach Erläuterung der algorithmischen Grundlagen für Particle-In-Cell Simulationen sowie den Grundlagen des parallelen Rechnens, verschiedene Parallelisierungsstrategien entwickelt, mit deren Hilfe die oben beschriebene Zuordnung für Multicomputer, bestehend aus einer beliebigen Anzahl an Einzelrechnern verschiedener Leistungsfähigkeit, erfolgen kann. Bei einer Parallelisierungsstrategie handelt es sich um einen Algorithmus, welcher für jedes in der Simulation auftretende Datenobjekt eine Prozessorzugehörigkeit liefert, so dass die Rechnerressourcen möglichst gut genutzt werden und somit die benötigte Laufzeit minimiert wird. Das Ziel der Laufzeitminimierung lässt sich, basierend auf einem mathematischen Modell des Parallelrechners sowie des durch die Simulation erzeugten Speicherzugriffsmusters, als diskretes Optimierungsproblem formulieren. Eine exakte Lösung dieses Optimierungsproblems ist für praxisrelevante Problemstellungen jedoch im Allgemeinen nicht praktikabel, da dies zum einen zu einem unvertretbar großen Rechenaufwand führen würde, und zum anderen die mathematischen Modelle für Parallelrechner, auf denen das Optimierungsproblem basiert, keine exakte Vorhersage der zu erwartenden Laufzeiten, sondern nur eine mehr oder weniger grobe Abschätzung derselben liefern können. Bei den entwickelten Parallelisierungsstrategien handelt es sich daher um Heuristiken, die mit geringem Aufwand an Laufzeit eine für praktische Zwecke zufriedenstellende Approximation an die optimale Zuordnung der Daten und Berechnungsoperationen liefern. Die Parallelisierungsstrategien werden so weit wie möglich theoretisch untersucht. Das Verhalten von Implementierungen der Strategien wird anhand von Benchmarkproblemen, welche basierend auf realen Simulationsproblemen aus dem Feld der Beschleunigerphysik entwickelt wurden, auf dem Parallelrechner des Instituts für Theorie Elektromagnetischer Felder der Technischen Universität Darmstadt evaluiert. Die Simulation einer realen Anordnung aus dem Anwendungsfeld der Beschleunigerphysik, welche mit Hilfe der im Rahmen der Arbeit entstandenen Software durchgeführt wurde, schließt die Arbeit ab. Bei diesem Anwendungsbeispiel handelt es sich um die in der Entwicklung befindliche Elektronenquelle für das europäische XFEL~Projekt bei DESY, Hamburg.

Alternative Abstract:
Alternative AbstractLanguage

The simulation of the dynamic of charged particles requires the coupled solution of the Maxwell's equations and the Newton-Lorentz equations. This can be accomplished numerically by the Particle-In-Cell (PIC) algorithm. For many problems occuring in the field of physics and engineering a 3D PIC simulation requires a large amount of computational resources. Thus, a single workstation is often not well suited or even not able to solve such problems because of insufficient memory or an excessively long runtime. Due to its scalability, the computational environment of a Multicomputer is well suited for the solution of such simulation problems. A Multicomputer is a parallel computer consisting of multiple processors where each processor works on an exclusive part of the memory. The utilization of a Multicomputer requires the parallelization of the PIC algorithm which includes the assignment of all computational operations to the available processors as well as the distribution of the simulation data to the memory modules of the processors. This assignment is critical for obtaining a satisfactory parallel performance and, thus, has to be done with great care considering the architectural properties of a Multicomputer. In the thesis, different parallelization-strategies are introduced which provide an assignment of the computational operations and the simulation data to the processors and memory modules, respectively. The parallelization-strategies are derived theoretically and the performance of implementations of the strategies is evaluated.

English
Uncontrolled Keywords: Parallelisierung Particle-In-Cell Cluster Simulation
Alternative keywords:
Alternative keywordsLanguage
Parallelisierung Particle-In-Cell Cluster SimulationGerman
URN: urn:nbn:de:tuda-tuprints-10850
Classification DDC: 600 Technology, medicine, applied sciences > 620 Engineering and machine engineering
000 Generalities, computers, information > 004 Computer science
Divisions: 18 Department of Electrical Engineering and Information Technology
Date Deposited: 17 Oct 2008 09:23
Last Modified: 07 Dec 2012 11:54
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/1085
PPN: 203138716
Export:
Actions (login required)
View Item View Item