Universität zu Köln

Ein Programm für die Parallelisierung dynamisch adaptiver Mehrgitterverfahren

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

[img]
Preview
PDF
Download (2517Kb) | Preview
    [img] ZIP
    Download (56Mb)
      [img] Archive (TGZ)
      Download (56Mb)

        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:
        AbstractLanguage
        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:
        CreatorsEmail
        Kiparski, Ekkehartrbekiparski@online.de
        URN: urn:nbn:de:hbz:38-66783
        Subjects: Data processing Computer science
        Uncontrolled Keywords:
        KeywordsLanguage
        ParallelisierungGerman
        adaptive MehrgitterverfahrenGerman
        parallele adaptive MehrgitterverfahrenGerman
        verteiltes ProgrammierenGerman
        MehrgitterverfahrenGerman
        adaptive multigridEnglish
        multigridEnglish
        parallelizationEnglish
        adaptivGerman
        parallelGerman
        load balancingEnglish
        LastverteilungGerman
        adaptiveEnglish
        parallelEnglish
        Faculty: Mathematisch-Naturwissenschaftliche Fakultät
        Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
        Language: German
        Date: 2016
        Date Type: Publication
        Date of oral exam: 13 January 2016
        Full Text Status: Public
        Date Deposited: 27 May 2016 11:43:50
        Referee
        NameAcademic Title
        Speckenmeyer, EwaldProf. Dr.
        Randerath, HubertProf. Dr.
        URI: http://kups.ub.uni-koeln.de/id/eprint/6678

        Actions (login required)

        View Item