Universität zu Köln

Kiparski, Ekkehart (2016). Ein Programm für die Parallelisierung dynamisch adaptiver Mehrgitterverfahren. PhD thesis, Universität zu Köln.

Preview	PDF veroeffentlichen.01.04.2016.pdf Download (2MB)
	ZIP Programm.01.04.2016.zip Download (59MB)
	Other Programm.01.04.2016.tgz Download (59MB)

Abstract

In dieser Arbeit werden dynamisch adaptive Mehrgitterverfahren parallelisiert. Bei dynamisch adaptiven Mehrgitterverfahren wird ein Gebiet mit einem Gitter überdeckt, und auf diesem Gitter wird gerechnet, indem Gitterpunkte in der Umgebung herangezogen werden, um den Wert des nächsten Zeitpunktes zu bestimmen. Dann werden gröbere und feinere Gitter erzeugt und verwendet, wobei die feineren Gitter sich auf Teilgebiete konzentrieren. Diese Teilgebiete ändern sich im Verlauf der Zeit. Durch die Verwendung der zusätzlichen Gitter werden die numerischen Eigenschaften verbessert. Die Parallelisierung solcher Verfahren geschieht in der Regel durch Bisektion. In der vorliegenden Arbeit wird die Umverteilung der Gebiete realisiert, indem Mengen von einzelnen Gitterpunkten verschickt werden. Das ist ein Scheduling-Verfahren. Die Mehrgitterstrukturen sind so aufgebaut, dass fast beliebige Gitterpunktverteilungen auf den Gitterebenen vorliegen können. Die Strukturen werden einmal erzeugt, und nur bei Bedarf geändert, sodass keine Speicherallokationen während der Iterationen nötig sind. Neben dem Gitter sind zusätzliche Strukturen, wie zum Beispiel die Randstrukturen, erforderlich. Eine Struktur Farbenfeld verzeichnet, auf welchem Kern sich ein Außenrandpunkt befindet. In der parallelen adaptiven Verfeinerung werden für einzelne durch ein Entscheidungskriterium ausgewählte Gitterpunkte 5 x 5 Punktüberdeckungen vorgenommen. Dazu werden die verfügbaren Entscheidungsinformationen zur Bestimmung von komplexeren Strukturen herangezogen. Damit muss das Verfeinerungsgitter nicht komplett abgebaut und dann wieder aufgebaut werden, sondern nur die Änderungen am Gitter sind vorzunehmen. Das spart viel Berechnungszeit. Der letzte Schritt besteht darin, den Lastausgleich durchzuführen. Zunächst werden die Lasttransferwerte bestimmt, die angeben, wie viele Gitterpunkte von wo nach wo zu verschicken sind. Das geschieht mit Hilfe einer PLB genannten Methode bzw. einer Variante. PLB wurde bisher vor allem für kombinatorische Probleme eingesetzt. Dann erfolgt eine Auswahl der zu verschickenden Gitterpunkte mit einer Strategie, welche Punkte eines Kerns zu welchen Nachbarkernen transferiert werden sollen. Im letzten Schritt werden schließlich die ausgewählten Punkte migriert, wobei alle Gitterpunktstrukturen umgebaut werden und solche Informationen gepackt werden müssen, sodass ein Umbau seiner Gitterpunktstrukturen bei dem Empfänger möglich wird. Neben den Gitterpunktstrukturen müssen auch Strukturen für die parallele adaptive Verfeinerung verändert werden. Es muss ein Weiterverschicken von Gitterpunkten möglich sein, wenn über die Lastkanten in mehreren Runden Last verschickt wird. Während des Lastausgleichs wird noch Arbeit durch eine Struktur Zwischenkorrektur durchgeführt, die es ermöglicht, das Farbenfeld intakt zu halten, wenn benachbarte Gitterpunkte gleichzeitig verschickt werden.

Item Type:	Thesis (PhD thesis)
Translated abstract:	Abstract Language In this thesis dynamic adaptive multi-grid methods are parallelized. In dynamic adaptive multi-grid methods a domain is covered by a grid, and this grid is utilized to calculate objective function values. The objective function at a specific grid point at time t is calculated according to the values of this point and its neighbors at time t-1. The accuracy of this method can be improved by applying coarser and finer grids, where the latter concentrate on subdomains which may change over time. The parallelization of such methods usually is conducted by bisection of the grid and distributed calculation of the partial objective function values. In this thesis a scheduling approach for the redistribution of partial domains by transferring sets of grid points is presented. The design of the applied multi-grid structures supports almost any distribution of grid points. The grids' data structures are generated once and changed only when required. Thus, no dynamic memory allocation is necessary during iterations. In addition to the multi-grid further structures are necessary, e.g. a structure called Farbenfeld (color field) records on which CPU core certain boundary points of the grid are located. During the parallel adaptive refinement phase a decision criterion is applied in order to create 5x5 fine grid points for one coarse grid point fullfilling the criterion. This is performed using complex data structures only necessitating local modifications to the grid, significantly reducing computation time. Lastly, load balancing is performed by calculating Lasttransferwerte (load transfer values), which specify the number of grid points to be send from one core to another. For this purpose the PLB method and a variant of it are utilized, which usually are applied to complex combinatorial optimization problems. Subsequently, the specific grid points to be transferred from one core to its neighboring cores are chosen and the necessary information for restructuring is send to the affected CPU cores. In addition to the multi-grid structures the structures used by parallel adaptive refinement phase need to be modified. If load is transferred in multiple consecutive load balancing phases, grid points need to be passed on to other neighboring cores. If neighboring grid points are migrated simultaneously during load balancing, a data structure Zwischenkorrektur (intermediate correction) is utilized to keep intact the Farbenfeld. English
Creators:	Creators Email ORCID ORCID Put Code Kiparski, Ekkehart rbekiparski@online.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-66783
Date:	2016
Language:	German
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Parallelisierung German adaptive Mehrgitterverfahren German parallele adaptive Mehrgitterverfahren German verteiltes Programmieren German Mehrgitterverfahren German adaptive multigrid English multigrid English parallelization English adaptiv German parallel German load balancing English Lastverteilung German adaptive English parallel English
Date of oral exam:	13 January 2016
Referee:	Name Academic Title Speckenmeyer, Ewald Prof. Dr. Randerath, Hubert Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/6678