• search hit 18 of 56
Back to Result List

## Multigrid Optimization Methods for High Performance Computing

### Implementierung von Mehrgitterverfahren zur Lösung von optimalen Steuerungsproblemen auf Höchstleistungsrechnern

• Optimal control problems are optimization problems governed by ordinary or partial differential equations (PDEs). A general formulation is given byrn \min_{(y,u)} J(y,u) with subject to e(y,u)=0, assuming that e_y^{-1} exists and consists of the three main elements: 1. The cost functional J that models the purpose of the control on the system. 2. The definition of a control function u that represents the influence of the environment of the systems. 3. The set of differential equations e(y,u) modeling the controlled system, represented by the state function y:=y(u) which depends on u. These kind of problems are well investigated and arise in many fields of application, for example robot control, control of biological processes, test drive simulation and shape and topology optimization. In this thesis, an academic model problem of the form \min_{(y,u)} J(y,u):=\min_{(y,u)}\frac{1}{2}\|y-y_d\|^2_{L^2(\Omega)}+\frac{\alpha}{2}\|u\|^2_{L^2(\Omega)} subject to -\div(A\grad y)+cy=f+u in \Omega, y=0 on \partial\Omega and u\in U_{ad} is considered. The objective is tracking type with a given target function y_d and a regularization term with parameter \alpha. The control function u takes effect on the whole domain \Omega. The underlying partial differential equation is assumed to be uniformly elliptic. This problem belongs to the class of linear-quadratic elliptic control problems with distributed control. The existence and uniqueness of an optimal solution for problems of this type is well-known and in a first step, following the paradigm 'first optimize, then discretize', the necessary and sufficient optimality conditions are derived by means of the adjoint equation which ends in a characterization of the optimal solution in form of an optimality system. In a second step, the occurring differential operators are approximated by finite differences and the hence resulting discretized optimality system is solved with a collective smoothing multigrid method (CSMG). In general, there are several optimization methods for solving the optimal control problem: an application of the implicit function theorem leads to so-called black-box approaches where the PDE-constrained optimization problem is transformed into an unconstrained optimization problem and the reduced gradient for these reduced functional is computed via the adjoint approach. Another possibilities are Quasi-Newton methods, which approximate the Hessian by a low-rank update based on gradient evaluations, Krylov-Newton methods or (reduced) SQP methods. The use of multigrid methods for optimization purposes is motivated by its optimal computational complexity, i.e. the number of required computer iterations scales linearly with the number of unknowns and the rate of convergence, which is independent of the grid size. Originally multigrid methods are a class of algorithms for solving linear systems arising from the discretization of partial differential equations. The main part of this thesis is devoted to the investigation of the implementability and the efficiency of the CSMG on commodity graphics cards. GPUs (graphic processing units) are designed for highly parallelizable graphics computations and possess many cores of SIMD-architecture, which are able to outperform the CPU regarding to computational power and memory bandwidth. Here they are considered as prototype for prospective multi-core computers with several hundred of cores. When using GPUs as streamprocessors, two major problems arise: data have to be transferred from the CPU main memory to the GPU main memory, which can be quite slow and the limited size of the GPU main memory. Furthermore, only when the streamprocessors are fully used to capacity, a remarkable speed-up comparing to a CPU is achieved. Therefore, new algorithms for the solution of optimal control problems are designed in this thesis. To this end, a nonoverlapping domain decomposition method is introduced which allows the exploitation of the computational power of many GPUs resp. CPUs in parallel. This algorithm is based on preliminary work for elliptic problems and enhanced for the application to optimal control problems. For the domain decomposition into two subdomains the linear system for the unknowns on the interface is solved with a Schur complement method by using a discrete approximation of the Steklov-Poincare operator. For the academic optimal control problem, the arising capacitance matrix can be inverted analytically. On this basis, two different algorithms for the nonoverlapping domain decomposition for the case of many subdomains are proposed in this thesis: on the one hand, a recursive approach and on the other hand a simultaneous approach. Numerical test compare the performance of the CSMG for the one domain case and the two approaches for the multi-domain case on a GPU and CPU for different variants.
• Optimale Steuerungsprobleme treten in einer Vielzahl von praktischen Anwendungen auf, zum Beispiel in der Robotersteuerung, Steuerung biologischer Prozesse, Simulation von Testfahrten und in der Form- und Topologieoptimierung. Charakterisiert werden solche Probleme durch ein Zielfunktional, welches unter bestimmten Nebenbedingungen, die durch gewöhnliche oder partielle Differentialgleichungen sowie eventuell vorhandener weiterer Beschränkungen gegeben sind, minimiert wird. In der vorliegende Dissertation wird ein akademisches Modelproblem mit Tracking Zielfunktional und einem Regularisierungsterm sowie einer linearen, gleichmäßig elliptischen partiellen Differentialgleichung zweiter Ordnung als Nebenbedingung betrachtet. Hierfür kann Existenz und Eindeutigkeit einer optimalen Lösung gezeigt werden. Dem Paradigma 'First optimize, then discretize' folgend werden zuerst die notwendigen und hinreichenden Optimalitätsbedingung mittels Berechnung der Adjungierten hergeleitet und in Form eines Optimalitätssystems beschrieben. In einem zweiten Schritt erfolgt die Approximation der auftretenden Differentialoperatoren durch Finite Differenzen. Für die numerische Lösung des resultierenden linearen Systems wird einerseits die Implementierbarkeit von bekannten und hinreichend untersuchten Optimierungsalgorithmen, im Speziellen eines kollektiven Mehrgitterverfahrens (CSMG), auf neue Rechnerarchitekturen untersucht, andererseits werden neue Algorithmen zur Lösung von optimalen Steuerungsprobleme konstruiert, die die effiziente Nutzung mehrerer paralleler Prozessoren erlauben. Die Implementierung dieser Algorithmen erfolgt auf einer handelsüblichen Grafikkarte (GPU): konzipiert für Grafikberechnungen, welche sich durch ein hohes Maß an Parallelisierung auszeichnen besitzen sie eine Vielzahl von Kernen und erreichen eine höhere Rechenleistung im Vergleich zu einer CPU. Die GPUs werden hier als Prototyp für zukünftige Multicore-Architekturen mit mehreren hundert Kernen betrachtet. Es zeigt sich, dass für moderate Problemgrößen eine Verbesserung in der Rechenzeit im Vergleich zu einer klassischen CPU erreichbar ist. Für größere Probleme ist der beschränkte Speicherplatz des Hauptspeichers der Grafikkarte der limitierende Faktor. Hierfür wird eine nichtüberlappende Gebietszerlegungsstrategie konstruiert, wobei mehrere GPUs bzw. CPUs parallel genutzt werden können. Diese Strategie basiert auf Vorarbeiten für elliptische Probleme und wird für optimale Steuerungsprobleme weiterentwickelt. Für eine Zerlegung in zwei Teilgebiete wird mittels einer Schur Komplement Methode das Gleichungssystem für den inneren Rand durch eine diskrete Approximation des Steklov-Poincare Operators hergeleitet, welches dann direkt gelöst werden kann. Aufbauend auf dieser Zerlegung werden in dieser Dissertation zwei verschiedene Algorithmen für die Gebietszerlegung in mehrere Gebiete betrachtet: auf der einen Seite ein rekursiver Ansatz, auf der anderen Seite ein simultaner Ansatz. Numerische Tests vergleichen die Performance des kollektiven Mehrgitterverfahrens auf der GPU mit der CPU für verschiedene Varianten.

### Additional Services

Author: Christian Wagner urn:nbn:de:hbz:385-8044 https://doi.org/10.25353/ubtr-xxxx-c295-9367/ Volker Schulz Doctoral Thesis English 2013/05/07 Universität Trier Universität Trier, Fachbereich 4 2012/12/07 2013/05/07 GPU; Gebietszerlegung; HPC; Mehrgitterverfahren; OptimierungGPU; domain decomposition; multigrid; optimal control; optimization Optimale Kontrolle Fachbereich 4 / Mathematik 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik

$Rev: 13581$