Hybrid approaches to adjoint code generation with dco/c++

Lotz, Johannes; Gauger, Nicolas Ralph; Naumann, Uwe

doi:34835

Hybrid approaches to adjoint code generation with dco/c++ = Hybride Verfahren zur Generierung adjungierter Programme mithilfe von dco/c++

Lotz, Johannes^RWTH*

2016

VerantwortlichkeitsangabeDiplom-Ingenieur Johannes Lotz

ImpressumAachen 2016

Umfang1 Online-Ressource (III, 127 Seiten) : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2016

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Naumann, Uwe (Thesis advisor) ; Gauger, Nicolas Ralph (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2016-03-03

Online
URN: urn:nbn:de:hbz:82-rwth-2016-061974
URL: https://publications.rwth-aachen.de/record/667318/files/667318.pdf
URL: https://publications.rwth-aachen.de/record/667318/files/667318.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
algorithmic differentiation (frei) ; adjoints (frei) ; optimization (frei) ; C++ (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die vorliegende Dissertationsschrift beschäftigt sich mit der Berechnung von Tangenten- und Adjungierten-Projektionen von Ableitungstensoren beliebiger Ordnung numerischer Simulationsprogramme, welche in der Programmiersprache C++ verfasst sind. Aufgrund der ständig steigenden Rechenleistung, spielen numerische Simulationen in vielen unterschiedlichen Bereichen eine fundamentale Rolle. Daher haben sich über die letzten Jahrzehnte Simulationsprogramme zur Grundlage von Optimierungsproblemen entwickelt, wie z.B. bei der Design-Optimierung in der numerischen Strömungsmechanik. Falls zu diesem Zweck ableitungsbasierte Verfahren verwendet werden, benötigt man Sensitivitäten des Simulationsprogrammes. Da dabei in den meisten Fällen Gradienten eines skalaren Zielfunktionals berechnet werden müssen, sollte dies mithilfe adjungierter Verfahren geschehen. Adjungierte Programme können entweder manuell geschrieben, oder durch "algorithmische" (auch "automatische") "Differentiation" (AD) generiert werden. AD ist eine semantische Programmtransformation, welche auf Basis der Kettenregel in der Differentialrechnung aus dem originalen Programm eines generiert, welches zusätzlich zu den Funktionswerten auch entsprechende Sensitivitäten berechnet. Demgegenüber steht das manuelle Schreiben adjungierter Programme. Letzteres ist auf der einen Seite meist ein aufwändiger und fehleranfälliger Prozess, wobei der Programmierer andereseits, sollte er fundierte mathematische Kenntnisse besitzen, möglicherweise ein hoch optimiertes, sehr effizientes Programm entwickelt. Dies ist insbesondere durch die Ausnutzung mathematischer Eigenschaften, wie dem Satz von impliziten Funktionen, möglich. Neben diesem Punkt verliert der Programmierer jedoch dabei die Möglichkeit eines inkrementellen Softwareentwicklungsprozesses. Um solch einen effektiven Entwicklungsprozess zu erhalten und zusätzlich ein effizientes adjungiertes Programm zu entwickeln wird in dieser Arbeit ein hybrider Ansatz vorgeschlagen. Dabei wird die Verwendung eines AD tools mit manuell geschriebenem adjungiertem Code verbunden. Damit erreicht man einen top-down Softwareentwicklungsprozess, welcher inkrementell von einer korrekten reinen AD Lösung, Schritt für Schritt zu einer sehr effizienten Implementierung verfeinert werden kann.Die Arbeit besteht aus drei eng verknüpften Themen-Bereichen. Den Anfang macht die Beschreibung und Einführung von dco/c++, eine Software welche im Zuge dieser Arbeit entwickelt wurde. dco/c++ ist eine Überladungsbibliothek welche AD für die Programmiersprache C++ implementiert und oben angesprochene Hybridisierung sehr flexibel und effizient unterstützt. Dabei wird der Flexibilitätsbegriff hier so verstanden, dass die Bibiliothek in einer modernen C++ Umgebung eingesetzt werden kann (d.h. generische Konzepte, exception-safety, thread-safety oder Portabilität unter verschiedenen Betriebssystemen) und dass eine gute Benutzbarkeit gewährleistet ist (verständliche Interfaces, Unterstützung von Ableitungen beliebiger Ordnung). Für dco/c++ wird die Effizienz durch Laufzeitmessungen mithilfe eine neu entwickelten AD test suite sichergestellt. Diese schafft eine gute Datenlage und macht einen fundierten Vergleich mit anderen AD tools möglich. Ergebnisse dazu sind in dieser Arbeit zusammengefasst.Als zweiten Bereich beschäftigt sich die Arbeit mit der symbolischen Herleitung von Adjungierten beliebiger Ordnung für einige weit verbreitete numerische Algorithmen. Darunter fallen z.B. lineare und nichtlinear Löser. Die Relevanz der dabei gewonnenen Formulierungen wird durch eine Verknüpfung mit dco/c++ und einer großen Effizienzsteigerung deutlich. Dies wird anhand einer umfassenden Beispielanwendung demonstriert. Zusätzlich wurde dco/c++ erfolgreich in vielen Projekten eingesetzt; die Anwendbarkeit der Software wird daher durch eine Beschreibung von Referenzprojekten dargelegt.Der dritte Bereich beschäftigt sich mit einem anderen Aspekt und gleichzeitig großem Problem bei adjungierten Programmen: dem Speicherverbrauch. Neben anderen Herangehensweisen, ist der Ansatz des "Checkpointing" verbreitet, um den Speicherverbrauch auf Kosten zusätzlicher Laufzeit zu verringern. In dieser Arbeit wurde zum ersten mal für das sogenannte "Call Tree Reversal Problem" die Formulierung als ganzzahliges Optimierungsproblem hergeleitet. Entsprechende Ergebnisse im Vergleich zu herkömmlichen Ansätzen finden sich ebenfalls in dieser Arbeit.

This dissertation is concerned with the computation of arbitrary-order derivative projections (tangents and adjoints) of numerical simulation programs written in C++. Thanks to the increasing computational power, simulation nowadays plays a fundamental role within a wide range of applications. On this basis, in the last decades simulation programs became the foundation for optimization problems in a wide variety of domains, e.g. design optimization in computational fluid dynamics. When using derivative-based algorithms to carry out the optimization, first- and higher-order sensitivities of the underlying simulation program are required. Since in many cases gradients of scalar objective functions need to be computed, the adjoint method should be used. Adjoint programs can either be written by hand or generated by Algorithmic (or Automatic) Differentiation (AD) tools. AD is a semantic program transformation exploiting the chain rule of differential calculus to automatically generate programs such that sensitivities are computed in addition to the original function values. Writing adjoint programs by hand can be a tedious, time-consuming, and error-prone task, but on the other hand, the well-versed programmer can possibly write much more efficient code, especially when exploiting mathematical properties by symbolic transformations. When hand-coding an adjoint simulation program, an incremental software development process is difficult. To achieve an effective development process and get an efficient program, hybridization techniques can be used to couple an AD tool with hand-written code. This makes a top-down adjoint code development possible -- beginning with a pure AD solution, going step by step to a more efficient implementation.This thesis consists of three main points. First, the software dco/c++ is presented. dco/c++ implements AD by overloading in C++ and features hybridization techniques in a flexible and efficient way. Flexibility is meant in terms of compliance with a modern C++ environment (e.g. generic concepts, exception-safety, thread-safety, or portability), and in terms of a convenient interface with emphasis on the support for arbitrary-order derivatives. Efficiency on the other hand is ensured by the newly developed AD test suite, which carries out performance tests also in comparison to other AD tools.As the second main point, arbitrary-order derivative projections of common numerical algorithms like linear and nonlinear solvers are derived symbolically, exploiting mathematical properties. Those results are shown to be of practical relevance by connecting them to the hybridization capabilities of dco/c++. This combination is presented with the help of an extensive case study demonstrating the effectiveness of the approach. In addition, dco/c++ was successfully used in many projects and its applicability is therefore shown in terms of "reference projects".When using AD to generate an adjoint program, the resulting executable typically requires a huge amount of memory. The third point of this thesis therefore covers the Call Tree Reversal (CTR) problem. CTR is a checkpointing technique, which allows for a tradeoff between additional runtime and memory requirements. The problem itself is an NP-complete optimization problem, which in this thesis is approached by a mixed integer programming formulation for the first time.

OpenAccess:
PDF PDF (PDFA)
(additional files)