Michael Hofmann

Effiziente parallele Sortier- und Datenumverteilungsverfahren für Partikelsimulationen auf Parallelrechnern mit verteiltem Speicher

Dokumente und Dateien

Hinweis

Bitte nutzen Sie beim Zitieren immer folgende Url:

http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-86229

Kurzfassung in Deutsch

Partikelsimulationen repräsentieren eine Klasse von daten- und rechenintensiven Simulationsanwendungen, die in unterschiedlichen Bereichen der Wissenschaft und der industriellen Forschung zum Einsatz kommen. Der hohe Berechnungsaufwand der eingesetzten Lösungsmethoden und die großen Datenmengen, die zur Modellierung realistischer Probleme benötigt werden, machen die Nutzung paralleler Rechentechnik hierfür unverzichtbar. Parallelrechner mit verteiltem Speicher stellen dabei eine weit verbreitete Architektur dar, bei der eine Vielzahl an parallel arbeitenden Rechenknoten über ein Verbindungsnetzwerk miteinander Daten austauschen können. Die Berechnung von Wechselwirkungen zwischen Partikeln stellt oft den Hauptaufwand einer Partikelsimulation dar und wird mit Hilfe schneller Lösungsmethoden, wie dem Barnes-Hut-Algorithmus oder der Schnellen Multipolmethode, durchgeführt. Effiziente parallele Implementierungen dieser Algorithmen benötigen dabei eine Sortierung der Partikel nach ihren räumlichen Positionen. Die Sortierung ist sowohl notwendig, um einen effizienten Zugriff auf die Partikeldaten zu erhalten, als auch Teil von Optimierungen zur Erhöhung der Lokalität von Speicherzugriffen, zur Minimierung der Kommunikation und zur Verbesserung der Lastbalancierung paralleler Berechnungen.

Die vorliegende Dissertation beschäftigt sich mit der Entwicklung eines effizienten parallelen Sortierverfahrens und der dafür benötigten Kommunikationsoperationen zur Datenumverteilung in Partikelsimulationen. Hierzu werden eine Vielzahl existierender paralleler Sortierverfahren für verteilten Speicher analysiert und mit den Anforderungen von Seiten der Partikelsimulationsanwendungen verglichen. Besondere Herausforderungen ergeben sich dabei hinsichtlich der Aufteilung der Partikeldaten auf verteilten Speicher, der Gewichtung zu sortierender Daten zur verbesserten Lastbalancierung, dem Umgang mit doppelten Schlüsselwerten sowie der Verfügbarkeit und Nutzung speichereffizienter Kommunikationsoperationen. Um diese Anforderungen zu erfüllen, wird ein neues paralleles Sortierverfahren entwickelt und in die betrachteten Anwendungsprogramme integriert. Darüber hinaus wird ein neuer In-place-Algorithmus für der MPI_Alltoallv-Kommunikationsoperation vorgestellt, mit dem der Speicherverbrauch für die notwendige Datenumverteilung innerhalb der parallelen Sortierung deutlich reduziert werden kann. Das Verhalten aller entwickelten Verfahren wird jeweils isoliert und im praxisrelevanten Einsatz innerhalb verschiedener Anwendungsprogramme und unter Verwendung unterschiedlicher, insbesondere auch hochskalierbarer Parallelrechner untersucht.

weitere Metadaten

übersetzter Titel
(Englisch)
Efficient Parallel Sorting and Data Redistribution Methods for Particle Codes on Distributed Memory Systems
Schlagwörter
(Deutsch)
Paralleles Sortieren, Datenumverteilung, Partikelsimulation, Performance-Optimierung, Verteilter Speicher, Message-Passing-Programmierung
Schlagwörter
(Englisch)
parallel sorting, data redistribution, particle simulation, performance optimization, distributed memory, message passing programming
SWD SchlagworteSortierverfahren, Parallelverarbeitung, Computersimulation, Verteilter Speicher, Wissenschaftliches Rechnen
DDC Klassifikation005
Institution(en) 
HochschuleTechnische Universität Chemnitz
FakultätFakultät für Informatik
BetreuerProf. Dr. Gudula Rünger
GutachterProf. Dr. Gudula Rünger
Prof. Dr. Felix Wolf
DokumententypDissertation
SpracheDeutsch
Tag d. Einreichung (bei der Fakultät)20.09.2011
Tag d. Verteidigung / Kolloquiums / Prüfung09.03.2012
Veröffentlichungsdatum (online)16.04.2012
persistente URNurn:nbn:de:bsz:ch1-qucosa-86229

Hinweis zum Urheberrecht

Diese Website ist eine Installation von Qucosa - Quality Content of Saxony!
Sächsische Landesbibliothek Staats- und Universitätsbibliothek Dresden