Charoenwanit, Ekkapot; Naumann, Uwe (Thesis advisor); Slusanschi, Emil-Ioan (Thesis advisor)
Aachen (2019)
Doktorarbeit
Dissertation, RWTH Aachen University, 2019
Kurzfassung
Diese Doktorarbeit beschäftigt sich mit dem automatischen Differenzieren (AD), das eine Methode zur algorithmischen Ableitungsberechnung von mathematischen Funktionen implementiert als ein Computerprogramm ist. Für die Berechnung von Ableitungen gibt es herkömmlicherweise eine Anzahl von numerischen Methoden, die Wissenschaftler und Ingenieure verwenden. Eine der am weit verbreitetsten Methoden ist die Methode der finiten Differenzen. Diese Methode ist unkompliziert und kann sehr einfach in einem Computerprogramm implementiert werden, weil es sich um eine nicht-intrusive Methode handelt. Das bedeutet, dass sie keine Veränderungen an der interessierenden Funktion erfordert. Da sie nur eine Näherungsmethode ist, ist es dennoch erforderlich, die Schrittweite ausreichend klein zu wählen, so dass eine angemessen gute Näherung für die exakten Ableitungen erhalt werden kann. Eine solche numerische Ungenauigkeit kann aufgrund der falschen Wahl der Schrittweite das Konvergenzverhalten von numerischen Simulationen potenziell und nachteilig beeinflussen. Deshalb benötigen wir eine Methode zur Ableitungsberechnung, die sowohl effizient als auch exakt ist, was in diesem Sinne bedeutet, dass sie unter solcher numerischen Ungenauigkeit nicht leidet. Das automatische Differenzieren kann diese Probleme angehen, weil wir mittels AD die Ableitungen bis zur Maschinengenauigkeit exakt berechnen können. Einer der Vorteile ist, dass AD für die Ableitungsberechnung von bestimmten Arten mathematischer Funktionen rechnerisch viel effizienter ist als die Methode der finiten Differenzen. Beim AD gibt es mehrere Ansätze, die Ableitungen von verschiedenen Arten mathematischer Funktionen zu bestimmen. Für die Funktionen, in denen die Anzahl der Funktionswerte m weit grösser ist als die Anzahl der Veränderlichen n, wird der Vorwärtsmodus (Englisch: tangent mode) häufig verwendet. Andererseits wird der Rückwärtsmodus (Englisch: adjoint mode) für die Funktionen, in denen die Anzahl der Veränderlichen n weit grösser ist als die Anzahl der Funktionswerte m, oft bevorzugt benutzt. Obwohl der Vorwärtsmodus bezogen auf den Speicherplatz relative "billig" ist, ist er rechnerisch aufwendig für die Funktionen mit m << n. In ähnlicher Weise ist der Rückwärtsmodus in Bezug auf die Laufzeit relative "billig", erfordert jedoch relativ viel Speicherplatz, insbesondere bei großen Problemen. Im Rückwärtsmodus speichern die Adjoint-Programme während des sogenannten Vorwärtsdurchlaufs die Ableitungsinformationen über eine Datenstruktur mit wahlfreiem Zugriff (im Englischen "tape" genannt), das im Wesentlichen den linearisierten gerichteten azyklischen Graphen (Englische Abkürzung: linearised DAG) darstellt. Das "tape" wird nach den Ableitungsinformationen interpretiert, die im "tape" während des Vorwärtsdurchlaufs gespeichert wurden, um den Gradienten während des sogenannten Rückwärtsdurchlaufs zu akkumulieren. Während des Rückwärtsdurchlaufs werden die Adjungierten in umgekehrter Reihenfolge des Kontrollflusses des Originalprogrammes verbreitet. Auf diese Weise werden die Adjungierten von den Ausgängen zu den Eingängen des Adjoint-Programmes verbreitet. Falls die Anzahl der Eingabewerte und die Anzahl der Ausgabewerte annähernd gleich sind und sehr viel grösser als 1 ist der Vorwärtsmodus vorzuziehen, da er einen geringeren Rechenaufwand, im Vergleich zum Rückwärtsmodus beim berechnen der Zeilen der Jacobi-Matrix hat. Außerdem hat der Vorwärtsmodus einen geringeren Speicherplatzbedarf als der Rückwärtsmodus. Diese Doktorarbeit zielt darauf ab, Algorithmen zur automatischen Akkumulation der Jacobi-Matrix von beliebig großen linearisierten gerichteten azyklischen Graphen zu entwickeln, um das Problem des Speichermangels zu lösen, wenn diese Graphen zu groß sind um in den Hauptspeicher der verwendeten Maschine zu passen. In dieser Doktorarbeit konzentrieren wir uns auf Adjoint-Probleme mit m << n. Bei unzureichendem Speicherplatz werden die Adjoint-Programme irgendwann, zu dem Zeitpunkt an dem sie nicht mehr genügend Arbeitsspeicher haben, abstürzen. Die Adjoint-Programme für die Problemgröße benötigt Ableitungsinformationen, die zu groß geworden sind, als dass sie in den Hauptspeicher der verwendeten Maschine passen. Zu diesem Zweck können Checkpointing-Schemata angewendet werden, um das Problem des Speichermangels zu verhindern. Durch Speichern der Ergebnisse von Zwischenberechnungen an einem bestimmten Punkt der Adjoint-Programme, Wiederherstellen dieser Werte von den Checkpoints, und Fortsetzen der Ausführung von diesen Checkpoints vorwärts wird der Speicherplatzbedarf reduziert. Somit können wir vermeiden, alle redundanten Werten von Anfang an neu zu berechnen. Eine gewisse Menge an Speicherplatz wird allerdings für die Speicherung von vorherigen Checkpointwerten aus den Zwischenberechnungen verlangt. Nichtsdestoweniger erfordert die Anwendung der Checkpointing-Schemata ziemlich gute Kenntnisse über den Rückwärtsmodus des ADs, was für Anfänger und manchmal sogar für Fortgeschrittene ziemlich kompliziert sein kann. Daher wäre es sehr wünschenswert, wenn wir ein Softwaretool für AD hätten, das in automatischer Weise das Speicherproblem offensichtlich beheben kann, ohne dass Benutzer den originalen AD-Code manuell zwischenspeichern (‚checkpoint") und parallelisieren müssen. Um die oben erwähnten Probleme anzugehen, haben wir ein komplettes Black-Box-Softwaretool für AD entwickelt, das auf der Operatorüberladung basiert. Dieses Softwaretool benötigt keinen Benutzereingriff und kann bei beliebigen numerischen Problemen, die in der Programmiersprache C++ geschrieben sind, mit beliebig grossen Problemgrößen automatisch ausgeführt werden. Es bietet Benutzern sowohl einen neuen überladenen aktiven Datentyp als auch eine Reihe von benutzerfreundlichen APIs (Englisch: Application Programming Interfaces). Der resultierende Derivative-Code bleibt nahezu identisch mit dem originalen Quellcode, außer wenn einige triviale Änderungen am originalen Quellcode erforderlich sind. In Kapitel 3 werden einige Serien-Implementationen, nämlich Serial Global Vertex Elimination (SGVE), Iterative Vertex Elimination (IVE) und Serial Vertex Elimination using Graph Partitioning (SVEGP), vorgeschlagen und diskutiert. SGVE ist grundsätzlich der herkömmliche Rückwärtsmodus des ADs, wobei der gesamte linearisierte Berechnungsgraph einer interessierenden Funktion im Hauptspeicher erstellt wird und Knoten des Graphen in umgekehrter Reihenfolge auf einmal eliminiert werden. Daher verlangt SGVE bei großen Problemen sehr große Mengen an Speicher. IVE wurde entwickelt, um zu versuchen, den Speicherverbrauch zu reduzieren. Es stellt sich heraus, dass IVE den Speicherverbrauch bis zu einem gewissen Grad verringern kann. Jedoch leidet IVE unter schlechtem Laufzeitverhalten aufgrund der Tatsache, dass Knoten in den Untergraphen entweder vorwärts oder rückwärts eliminiert werden, wenn die Speicherobergrenze erreicht wird. Damit erfolgt die resultierende Sequenz der Eliminierung von Knoten auf die Crosscountry-Sortierung und dies bewirkt ein Laufzeitverhalten, dass im Vergleich zu SGVE erheblich schlechter ist. Folglich wurde SVEGP so entwickelt, dass die Untergraphen eines linearisierten Berechnungsgraphen in umgekehrter Reihenfolge erzeugt. Zunächst unterteilt SVEGP den gesamten linearisierten Graphen in mehrere Untergraphen. Jeder dieser Untergraphen passen in den Hauptspeicher. Die Untergraphen werden in umgekehrter Reihenfolge erstellt. Nach der Erstellung jedes Untergraphen entfernt SVEGP die toten, zwischenliegenden Knoten aus dem jeweiligen Untergraphen mittels umgekehrter Vertex Elimination. Daher entspricht dies effektiv der globalen Eliminierung der gesamten Menge von zwischenliegenden Knoten aus dem gesamten linearisierten Graphen mittels umgekehrter Vertex Elimination. Dieser Ansatz ermöglicht SVEGP, die gleiche Anzahl der Multiplikation von Gleitkommazahlen wie die beim SGVE und Rückwärtsmodus beizubehalten. Jedoch hängt die rechnerische Komplexität auch von der Anzahl der Untergraphen ab, weil die Funktion eines einzelnen Untergraphen durch Wiederherstellen des gespeicherten Inputs jedes Mal von Anfang an neu berechnet werden muss, bevor er erstellt werden kann. Deswegen hat das resultierende Adjoint-Programm die quadratische Komplexität bezüglich der Anzahl von Untergraphen. Aufgrund des zusätzlichen quadratischen Rechenaufwandes bezüglich der Anzahl von Untergraphen beim SVEGP haben wir in Kapitel 4 eine parallele Implementierung namens Parallelised Adjoint Accumulation (PAA) entwickelt, wobei linearisierte DAGs in mehrere Untergraphen unterteilt werden, von denen jeder in den Hauptspeicher des jeweiligen Rechenknotens passt. PAA verwendet MPI (English: Message Passing Interface), um Untergraphen auf die verfügbaren Prozessoren zu verteilen. Diese Prozessoren können ferner eine Pre-Akkumulation auf ihren eigenen Untergraphen parallel ausführen, was beim Verbessern der Laufzeitleistung des Akkumulationsprozesses weiterhelfen kann. Die Ergebnisse der Anwendung von PAA in mehreren Fallstudien zeigen, dass PAA erfolgreich ausgeführt werden kann, ohne dass die gegebenen Speicherobergrenzen überschritten werden. Außerdem kann PAA das Laufzeitproblem beheben, mit dem SVGE konfrontiert ist. Ferner zeigen unsere experimentellen Ergebnisse, dass PAA erhebliche Speedups erreichen kann, im Vergleich zur originalen Serial-Version von SVEGP, das die quadratische Komplexität bezüglich der Anzahl von Untergraphen hat. Weiterhin zeigen die Ergebnisse auch, dass PAA in Bezug auf die Laufzeit den Vorwärtsmodus des AD übertrifft, der unter seiner rechnerischen Komplexität ernsthaft leidet, wenn die Anzahl des Inputs n im Vergleich zur Anzahl des Outputs m ausreichend groß ist.
Einrichtungen
- Fachgruppe Informatik [120000]
- Lehr- und Forschungsgebiet Software und Werkzeuge für Computational Engineering [123120]