TU Darmstadt / ULB / TUbiblio

Compiler Support for Operator Overloading and Algorithmic Differentiation in C++

Hück, Alexander (2020)
Compiler Support for Operator Overloading and Algorithmic Differentiation in C++.
Technische Universität Darmstadt
doi: 10.25534/tuprints-00011522
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Multiphysics software needs derivatives for, e.g., solving a system of non-linear equations, conducting model verification, or sensitivity studies. In C++, algorithmic differentiation (AD), based on operator overloading (overloading), can be used to calculate derivatives up to machine precision. To that end, the built-in floating-point type is replaced by the user-defined AD type. It overloads all required operators, and calculates the original value and the corresponding derivative based on the chain rule of calculus. While changing the underlying type seems straightforward, several complications arise concerning software and performance engineering. This includes (1) fundamental language restrictions of C++ w.r.t. user-defined types, (2) type correctness of distributed computations with the Message Passing Interface (MPI) library, and (3) identification and mitigation of AD induced overheads. To handle these issues, AD experts may spend a significant amount of time to enhance a code with AD, verify the derivatives and ensure optimal application performance. Hence, in this thesis, we propose a modern compiler-based tooling approach to support and accelerate the AD-enhancement process of C++ target codes. In particular, we make contributions to three aspects of AD.

The initial type change - While the change to the AD type in a target code is conceptually straightforward, the type change often leads to a multitude of compiler error messages. This is due to the different treatment of built-in floating-point types and user-defined types by the C++ language standard. Previously legal code constructs in the target code subsequently violate the language standard when the built-in floating-point type is replaced with a user-defined AD type. We identify and classify these problematic code constructs and their root cause is shown. Solutions by localized source transformation are proposed. To automate this rather mechanical process, we develop a static code analyser and source transformation tool, called OO-Lint, based on the Clang compiler framework. It flags instances of these problematic code constructs and applies source transformations to make the code compliant with the requirements of the language standard. To show the overall relevance of complications with user-defined types, OO-Lint is applied to several well-known scientific codes, some of which have already been AD enhanced by others. In all of these applications, except the ones manually treated for AD overloading, problematic code constructs are detected.

Type correctness of MPI communication - MPI is the de-facto standard for programming high performance, distributed applications. At the same time, MPI has a complex interface whose usage can be error-prone. For instance, MPI derived data types require manual construction by specifying memory locations of the underlying data. Specifying wrong offsets can lead to subtle bugs that are hard to detect. In the context of AD, special libraries exist that handle the required derivative book-keeping by replacing the MPI communication calls with overloaded variants. However, on top of the AD type change, the MPI communication routines have to be changed manually. In addition, the AD type fundamentally changes memory layout assumptions as it has a different extent than the built-in types. Previously legal layout assumptions have, thus, to be reverified. As a remedy, to detect any type-related errors, we developed a memory sanitizer tool, called TypeART, based on the LLVM compiler framework and the MPI correctness checker MUST. It tracks all memory allocations relevant to MPI communication to allow for checking the underlying type and extent of the typeless memory buffer address passed to any MPI routine. The overhead induced by TypeART w.r.t. several target applications is manageable.

AD domain-specific profiling - Applying AD in a black-box manner, without consideration of the target code structure, can have a significant impact on both runtime and memory consumption. An AD expert is usually required to apply further AD-related optimizations for the reduction of these induced overheads. Traditional profiling techniques are, however, insufficient as they do not reveal any AD domain-specific metrics. Of interest for AD code optimization are, e.g., specific code patterns, especially on a function level, that can be treated efficiently with AD. To that end, we developed a static profiling tool, called ProAD, based on the LLVM compiler framework. For each function, it generates the computational graph based on the static data flow of the floating-point variables. The framework supports pattern analysis on the computational graph to identify the optimal application of the chain rule. We show the potential of the optimal application of AD with two case studies. In both cases, significant runtime improvements can be achieved when the knowledge of the code structure, provided by our tool, is exploited. For instance, with a stencil code, a speedup factor of about 13 is achieved compared to a naive application of AD and a factor of 1.2 compared to hand-written derivative code.

Typ des Eintrags: Dissertation
Erschienen: 2020
Autor(en): Hück, Alexander
Art des Eintrags: Erstveröffentlichung
Titel: Compiler Support for Operator Overloading and Algorithmic Differentiation in C++
Sprache: Englisch
Referenten: Bischof, Prof. Dr. Christian ; Bücker, Prof. Dr. Martin
Publikationsjahr: 2020
Ort: Darmstadt
Datum der mündlichen Prüfung: 28 Februar 2020
DOI: 10.25534/tuprints-00011522
URL / URN: https://tuprints.ulb.tu-darmstadt.de/11522
Kurzbeschreibung (Abstract):

Multiphysics software needs derivatives for, e.g., solving a system of non-linear equations, conducting model verification, or sensitivity studies. In C++, algorithmic differentiation (AD), based on operator overloading (overloading), can be used to calculate derivatives up to machine precision. To that end, the built-in floating-point type is replaced by the user-defined AD type. It overloads all required operators, and calculates the original value and the corresponding derivative based on the chain rule of calculus. While changing the underlying type seems straightforward, several complications arise concerning software and performance engineering. This includes (1) fundamental language restrictions of C++ w.r.t. user-defined types, (2) type correctness of distributed computations with the Message Passing Interface (MPI) library, and (3) identification and mitigation of AD induced overheads. To handle these issues, AD experts may spend a significant amount of time to enhance a code with AD, verify the derivatives and ensure optimal application performance. Hence, in this thesis, we propose a modern compiler-based tooling approach to support and accelerate the AD-enhancement process of C++ target codes. In particular, we make contributions to three aspects of AD.

The initial type change - While the change to the AD type in a target code is conceptually straightforward, the type change often leads to a multitude of compiler error messages. This is due to the different treatment of built-in floating-point types and user-defined types by the C++ language standard. Previously legal code constructs in the target code subsequently violate the language standard when the built-in floating-point type is replaced with a user-defined AD type. We identify and classify these problematic code constructs and their root cause is shown. Solutions by localized source transformation are proposed. To automate this rather mechanical process, we develop a static code analyser and source transformation tool, called OO-Lint, based on the Clang compiler framework. It flags instances of these problematic code constructs and applies source transformations to make the code compliant with the requirements of the language standard. To show the overall relevance of complications with user-defined types, OO-Lint is applied to several well-known scientific codes, some of which have already been AD enhanced by others. In all of these applications, except the ones manually treated for AD overloading, problematic code constructs are detected.

Type correctness of MPI communication - MPI is the de-facto standard for programming high performance, distributed applications. At the same time, MPI has a complex interface whose usage can be error-prone. For instance, MPI derived data types require manual construction by specifying memory locations of the underlying data. Specifying wrong offsets can lead to subtle bugs that are hard to detect. In the context of AD, special libraries exist that handle the required derivative book-keeping by replacing the MPI communication calls with overloaded variants. However, on top of the AD type change, the MPI communication routines have to be changed manually. In addition, the AD type fundamentally changes memory layout assumptions as it has a different extent than the built-in types. Previously legal layout assumptions have, thus, to be reverified. As a remedy, to detect any type-related errors, we developed a memory sanitizer tool, called TypeART, based on the LLVM compiler framework and the MPI correctness checker MUST. It tracks all memory allocations relevant to MPI communication to allow for checking the underlying type and extent of the typeless memory buffer address passed to any MPI routine. The overhead induced by TypeART w.r.t. several target applications is manageable.

AD domain-specific profiling - Applying AD in a black-box manner, without consideration of the target code structure, can have a significant impact on both runtime and memory consumption. An AD expert is usually required to apply further AD-related optimizations for the reduction of these induced overheads. Traditional profiling techniques are, however, insufficient as they do not reveal any AD domain-specific metrics. Of interest for AD code optimization are, e.g., specific code patterns, especially on a function level, that can be treated efficiently with AD. To that end, we developed a static profiling tool, called ProAD, based on the LLVM compiler framework. For each function, it generates the computational graph based on the static data flow of the floating-point variables. The framework supports pattern analysis on the computational graph to identify the optimal application of the chain rule. We show the potential of the optimal application of AD with two case studies. In both cases, significant runtime improvements can be achieved when the knowledge of the code structure, provided by our tool, is exploited. For instance, with a stencil code, a speedup factor of about 13 is achieved compared to a naive application of AD and a factor of 1.2 compared to hand-written derivative code.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Multiphysik-Software benötigt Ableitungen, um beispielsweise ein System nichtlinearer Gleichungen zu lösen, oder Modellverifizierungen und Sensitivitätsstudien durchzuführen. In C++ kann die Algorithmische Differenzierung (AD) basierend auf Operator Overloading (Überladung) verwendet werden, um Ableitungen bis zur Maschinengenauigkeit zu berechnen. Zu diesem Zweck wird der integrierte Gleitkommatyp durch den benutzerdefinierten AD-Typ ersetzt. Er überlädt alle erforderlichen Operatoren, und berechnet den ursprünglichen Wert und die entsprechende Ableitung basierend auf der Kettenregel der Differentialrechnung. Während das Ändern des zugrunde liegenden Typs unkompliziert erscheint, treten als Konsequenz einige Komplikationen in Bezug auf Software und Performance Engineering auf. Dies beinhaltet (1) grundlegende Sprachein- schränkungen von C++ bezüglich benutzerdefinierter Typen, (2) Typkorrektheit verteilter Berechnungen mit dem Message Passing Interface (MPI) und (3) Identifikation und Behandlung von AD-induziertem Overhead. Um diese Komplikationen zu bewältigen, können AD-Experten viel Zeit darauf verwenden, einen Code mit AD zu versehen, die Ableitungen zu überprüfen und eine optimale Anwendungsleistung sicherzustellen. Daher schlagen wir in dieser Arbeit einen modernen compilerbasierten Tooling-Ansatz vor, um den AD-Verbesserungsprozess von C++-Zielcodes zu unterstützen und zu beschleunigen. Insbesondere leisten wir Beiträge zu drei Aspekten des Differenzierens mit AD.

Die initiale Typänderung - Während die Änderung des AD-Typs in einem Zielcode konzeptionell unkompliziert ist, führt die Typänderung häufig zu einer Vielzahl von Compilerfehlermeldungen. Dies ist auf die unterschiedliche Behandlung der integrierten Gleitkommatypen und der benutzerdefinierten Typen durch den C++-Sprachstandard zurückzuführen. Zuvor gültige Codekonstruktionen im Zielcode verletzen anschließend den Sprachstandard, wenn der integrierte Gleitkommatyp durch einen benutzerdefinierten AD-Typ ersetzt wird. Wir identifizieren und klassifizieren diese problematischen Codekonstrukte und zeigen ihre Ursache auf. Zu jedem identifizierten Codekonstrukt werden Lösungen durch lokalisierte Quelltexttransformation vorgeschlagen. Um diesen eher mechanischen Prozess zu automatisieren, entwickeln wir auf der Grundlage des Clang- Compiler-Frameworks ein statisches Code-Analyse und Quelltexttransformationswerkzeug namens OO-Lint. Es kennzeichnet Instanzen dieser problematischen Codekonstrukte und wendet Quelltexttransformationen an, um sicherzustellen, dass der Code nach der AD-Typänderung den Anforderungen des Sprachstandards entspricht. Um die allgemeine Relevanz von Komplikationen mit benutzerdefinierten Typen aufzuzeigen, wird OO-Lint auf mehrere bekannte wissenschaftliche Codes angewendet, von denen einige bereits durch andere AD-erweitert wurden. In all diesen Anwendungen, mit Ausnahme derer, die manuell für die AD-Überladung behandelt wurden, werden problematische Codekonstrukte erkannt.

Datentyp-Korrektheit von MPI-Kommunikation - MPI ist der faktische Standard für die Programmierung von verteilten Hochleistungsanwendungen. Gleichzeitig verfügt es über eine komplexe Programmierschnittstelle, deren Verwendung fehleranfällig sein kann. Beispielsweise erfordern von MPI abgeleitete Datentypen eine manuelle Erstellung, indem Speicherorte der zugrunde liegenden Daten angegeben werden. Die Angabe falscher Speicheradressen kann zu subtilen Fehlern führen, die nur schwer zu erkennen sind. Im Kontext von AD existieren spezielle Bibliotheken, die die erforderliche Buchhaltung für Ableitungen verwalten, indem sie die MPI-Kommunikationsaufrufe durch überladene Varianten ersetzen. Zusätzlich zur Änderung des AD-Typs müssen die MPI- Kommunikationsroutinen jedoch manuell geändert werden. Darüber hinaus werden durch den AD-Typ die Annahmen zur Speicherauslegung grundlegend geändert, da er ein anderes Ausmaß aufweist als die integrierten Typen. Bisherige Annahmen zur Speicher- auslegung müssen daher erneut überprüft werden. Um subtile typbezogene Fehler zu erkennen, haben wir das auf dem LLVM-Compiler-Framework basierende Tool TypeART entwickelt. Es verfolgt alle für die MPI-Kommunikation relevanten Speicherallokationen, um den zugrunde liegenden Typ und den Umfang der typlosen Speicherpufferadresse zu überprüfen, die an eine MPI-Routine übergeben wird. Das Anwenden von TypeART auf mehrere Zielanwendungen zeigt, dass der verursachte Overhead akzeptabel ist.

AD-domänenspezifische Profilerstellung- Das Black-Box-Anwenden von AD ohne Berücksichtigung der Zielcodestruktur kann sich erheblich auf die Laufzeit und den Speicherverbrauch auswirken. Ein AD-Experte muss in der Regel weitere AD-bezogene Optimierungen vornehmen, um diese induzierten Berechnungskosten zu reduzieren. Herkömmliche Profiling-Techniken sind jedoch unzureichend, da sie keine domänen-spezifischen AD-Metriken anzeigen. Von Interesse für die AD-Code-Optimierung sind beispielsweise bestimmte Codemuster, insbesondere auf Funktionsebene, die mit AD effizient behandelt werden können. Zu diesem Zweck haben wir ein statisches Profiling-Tool namens ProAD entwickelt, das auf dem LLVM-Compiler-Framework basiert. Für jede Funktion wird der Berechnungsgraph basierend auf dem statischen Datenfluss der Gleitkommavariablen generiert. Das Framework unterstützt die Musteranalyse im Berechnungsgraph, um die optimale Anwendung der Kettenregel zu ermitteln. Das Potenzial der optimalen Anwendung von AD zeigen wir anhand von zwei Fallstudien. In beiden Fällen können erhebliche Laufzeitverbesserungen erzielt werden, wenn die von unserem Tool bereitgestellten Kenntnisse über die Codestruktur genutzt werden. Beispielsweise wird bei einem Stencil-Code ein Beschleunigungsfaktor von ungefähr 13 im Vergleich zu einer naiven Anwendung von AD und ein Faktor von 1,2 im Vergleich zu einem handgeschriebenen abgeleiteten Code erreicht.

Deutsch
URN: urn:nbn:de:tuda-tuprints-115226
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Scientific Computing
Zentrale Einrichtungen
Zentrale Einrichtungen > Hochschulrechenzentrum (HRZ)
Zentrale Einrichtungen > Hochschulrechenzentrum (HRZ) > Hochleistungsrechner
Hinterlegungsdatum: 10 Jun 2020 10:28
Letzte Änderung: 16 Jun 2020 05:22
PPN:
Referenten: Bischof, Prof. Dr. Christian ; Bücker, Prof. Dr. Martin
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 28 Februar 2020
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen