English Title: The parallelization of the filtering algebraic multigrid method as a solver for partial differential equations

Preview

PDF, German Download (2MB) | Terms of use

Abstract

In dieser Doktorarbeit wird das neue robuste und effiziente parallele algebraische Mehrgitterverfahren pFAMG zum Lösen von partiellen Differentialgleichungen präsentiert. Der aktuelle Stand der Forschung für parallele und robuste Lösungsverfahren für partielle Differentialgleichungen wird zusammengefaßt; dies umfaßt vor allem parallele geometrische und algebraische Mehrgitterverfahren (AMG). Zwei Einsatzgebiete für algebraische Mehrgitterverfahren werden herausgearbeitet: als Löser für die Gleichung auf der von einem Gittergenerator erzeugten Triangulierung des Gebiets oder als Grobgitterlöser innerhalb eines geometrischen Mehrgitterverfahrens. MIMD Parallelrechner mit sehr vielen Prozessoren sind die Zielarchitektur; sie werden im SPMD Modell benutzt. Ein ganzer Satz von Methoden wird entwickelt, mit dem sich AMG Verfahren – speziell Selektionsverfahren – parallelisieren lassen. Das Ziel ist dabei, das serielle Verfahren möglichst wenig zu verändern, um seine Güte zu erhalten. Dafür wird ein knotenbasierter Verteilungsansatz verwendet. Darauf wird eine parallele lineare Algebra definiert. Der zentrale Begriff ist dabei die parallele Darstellungsform. Für alle benötigten linearen Algebra Operationen wird bewiesen, welche parallelen Darstellungsformen für die Operanden zulässig sind. Die wesentlichen Komponenten sind ein ausreichender Überlapp der Matrix-Teilgraphen auf den einzelnen Prozessoren, ein Graphfärbungsalgorithmus, mit dessen Hilfe die Arbeit im Überlappbereich teilsequentialisiert wird, um eine widersprüchliche Markierung der Knoten zu vermeiden, sowie die Gittertransferoperatoren (Restriktion und Prolongation), die Galerkinassemblierung für die Erstellung der Grobgittermatrizen und der Löser auf dem gröbsten Gitter. Dabei wird Wert darauf gelegt, daß alle Komponenten völlig verteilt ablaufen können, um so eine gute Skalierbarkeit auch für sehr viele Prozessoren zu ermöglichen. Für den Löser auf dem gröbsten Gitter stellt sich eine Agglomeration auf nur einen Prozessor als ausreichend performant heraus. Die Korrektheit aller Algorithmusteile wird bewiesen. Dieser Rahmenalgorithmus wird nun konkret auf das filternde algebraische Mehrgitterverfahren (FAMG) angewandt. Als Hilfsmittel für die parallele Programmierung wird das Programmiersystem UG (Unstructured Grids, siehe http://cox.iwr.uni-heidelberg.de/~ug) verwendet. Der Kern des FAMG Verfahrens, nämlich die Bestimmung einer Menge von guten Elternpaaren, aus denen ein Knoten gut interpoliert werden kann, kann gegenüber dem seriellen Verfahren unter den geschaffenen Voraussetzungen vollkommen unverändert gelassen werden. Die Sequenz, in der diese Elternpaare ausgewählt und zur Fein- bzw. Grobknotenmarkierung herangezogen werden, muß allerdings für einen effizienten parallelen Algorithmus entscheidend umgestaltet werden. Dafür stellt das entwickelte Rahmenverfahren die entscheidenden Hilfsmittel bereit. Da hier allerdings vom seriellen Ablauf abgewichen werden muß, ist das die kritische Stelle im gesamten Verfahren. Daß dabei die Robustheit des Lösungsverfahrens nicht verloren geht, zeigen die durchgeführten numerischen Experimente. Das Verfahren ist für alle Steifigkeitsmatrizen, wie sie aus Finiten Differenzen, Finiten Elemente oder Finiten Volumen Diskretisierungen entstehen, geeignet. Es werden Experimente für die Anisotrope Poissongleichung und die Konvektions-Diffusionsgleichung für lineare Strömungen und Kreisströmungen präsentiert. Für diese singulär gestörten Differentialgleichungen werden auch extreme Parameterwerte getestet, die üblicherweise ein paralleles Lösungsverfahren zum Versagen bringen. Die Parallelisierung kann unverändert auch für Systeme von partiellen Differentialgleichungen verwendet werden. In den Experimenten werden bis zu 128 Prozessoren und 16,7 Mio. Unbekannten verwendet. In allen Fällen wird Robustheit bezüglich des Gleichungsparameters (das ist der Anisotropiekoeffizient bzw. die Pecletzahl), der Prozessoranzahl, der Gebietsaufteilung und der Gitterweite (bzw. der Anzahl der Unbekannten im linearen Gleichungssystem) erzielt. Die ermittelten Scale-up Effizienzen von bis zu 80% auf 128 Prozessoren sind sehr gut. Als die zwei wesentlichen Einflußfaktoren auf die parallele Effizienz werden die Lastbalance und die Interfacelänge nachgewiesen. Für beide Faktoren gibt es ausgereifte Techniken, um mit ihnen umzugehen. Das Ziel, ein robustes, effizientes und paralleles algebraisches Mehrgitterverfahren zu erstellen, ist also vollständig erreicht worden.

Translation of abstract (English)

A new robust and efficient parallel algebraic multigrid method pFAMG for the solution of partial differential equations is presented in this thesis. The current state of research on parallel and robust solvers for partial differential equations is summarized, especially parallel geometric and algebraic multigrid methods (AMG). Two use cases for algebraic multigrid methods are emphasized: as a solver for the equation on the triangulation of the domain provided by a grid generator or as a coarse level solver for a geometric multigrid method. MIMD computers with many processors are the target platform; the computers are operated in the SPMD model. A set of approaches is developed to enable the parallelization of AMG methods, especially selection methods. The aim is to alter the sequential method as little as possible in order to maintain the numerical quality. A node-based distribution is used. Thereupon a parallel linear algebra is defined. The main concept is the parallel representation format. It is proved, which combinations of the representation formats are correct for the operands of the used linear algebra operations. The essential ingredients are a sufficient overlap of the matrix sub-graphs on each individual processor, a graph coloring algorithm, to establish a partly sequential ordering of the processors to avoid inconsistent node labels, further on grid transfer operators (restriction and prolongation), a Galerkin assembly for the coarse level matrix, and a base level solver. The crucial aspect is that all components are working completely parallel to ensure the optimal parallel scale-up even for many processors. An agglomeration onto one single processor shows sufficient performance for the base level solver. The correctness of all parts of the algorithm is proved. This general approach is now applied to the filtering algebraic multigrid method (FAMG). The implementation uses the toolbox UG (Unstructured Grids, see http://cox.iwr.uni-heidelberg.de/~ug) for the parallel numerical solution of partial differential equations. The core of the method – the calculation of good parent nodes to interpolate a node well – can be left completely unchanged compared to the sequential program due to the provided prerequisites. The sequence, in which the parents are selected and the fine / coarse labeling is done, must be changed to yield an efficient algorithm. For this task the general approach developed in this thesis provides essential tools. Due to the deviation from the sequential algorithm this part is the most critical in the whole program. Whether the robustness of the solver is preserved must be checked by numerical experiments. The method is well suited for all stiffness matrices produced by finite difference, finite elements or finite volume discretizations. Experiments are presented for the anisotropic Poisson equation and the convection diffusion equation for linear and circular currents. Even extreme parameter values, for which usual parallel solvers fail, are tested for these singular disturbed equations. The parallelization can be applied unchanged for systems of partial differential equations. Up to 128 processors and 16.7 million unknowns are used in the experiments. All cases show robustness with regard to the parameter of the equation (i. e. the coefficient of the anisotropy respectively the Peclet number), the number of processors, the domain decomposition and the mesh width (or the number of unknowns in the linear system of equations). The measured scale-up efficiency of up to 80% for 128 processors is very good. The two main influences on the parallel efficiency prove to be the load balance and the interface length. There exist mature techniques to tackle with these aspects. The goal to build a robust, efficient and parallel algebraic multigrid method is totally achieved.