Exploitation of structural sparsity in algorithmic differentiation

Varnik, Ebadollah; Naumann, Uwe

doi:urn:nbn:de:hbz:82-opus-38476

Exploitation of structural sparsity in algorithmic differentiation = Ausnutzung der strukturellen Dünnbesetztheit im algorithmischen Differenzieren

Varnik, Ebadollah (Author)

2011

Verantwortlichkeitsangabevorgelegt von Ebadollah Varnik

ImpressumAachen : Publikationsserver der RWTH Aachen University 2011

Umfang145 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2011

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Naumann, Uwe (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2011-11-09

Online
URN: urn:nbn:de:hbz:82-opus-38476
URL: https://publications.rwth-aachen.de/record/82673/files/82673.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Feasible Algorithm (Genormte SW) ; Informatik (frei) ; Algorithmisches Differenzieren (frei) ; Dünnbesetztheitsmuster (frei) ; algorithmic differentiation (frei) ; structural sparsity (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: D.1

Kurzfassung
Der Hintergrund dieser Arbeit ist, algorithmisches Differenzierung (AD) der in der Praxis sehr rechenintensiven Vektor-Funktionen, angewendet als Computerprogramme. Traditionell implementieren die meisten AD-Werkzeuge den Vorwärts- bzw. Rückwärtsmodus AD zur Berechnung der Jacobi-Matrix an einer bestimmten Stelle der Eingabe, auf eine Art interner Darstellung wie beispielsweise Hauptspeicher oder Festplatte. In der Tat stellt der Speicher den Flaschenhals von AD vor allem im Rückwärtsmodus dar. Der Vorwärtsmodus AD kann sehr billig in Bezug auf Speicher implementiert werden. Man propagiert dafür zur Laufzeit die Richtungsableitungen vorwärts. Im Gegensatz dazu muss der Rückwärtsmodus gewisse Daten speichern, um den Datenfluss umzukehren und somit Rückwärts-Berechnung der Adjongierten zu ermöglichen. Letzteres ist der Gegenstand der Forschung im AD-Umfeld für skalare Funktionen, da eine einzelne Anwendung des Rückwärtsmodus genügt, um den gesamten Gradienten der Zielfunktion zu akkumulieren. Um den Speicherverbrauch zu reduzieren, wurden Checkpointing-Strategien entworfen, z.B. für zeitabhängige Probleme. Allerdings erfordern sie das Wissen des Anwenders sowohl über die Funktion selbst als auch über den Rückwärtsmodus AD. In diesem Zusammenhang wollen wir ein Werkzeug präsentieren, das den Nicht-AD-Experten die Anwendung des Rückwärtsmodus AD bei seinem Problem wesentlich vereinfacht. Darüber hinaus untersuchen wir Methoden, um die Ausnutzung der strukturellen Eigenschaften der Ableitungstensoren wie Jacobi- und Hesse-Matrizen zu verbessern. Bestehende Methoden basieren auf der Kenntnis der Nichtnull-Muster der Ableitungsstrukturen, in denen eine Kompression in der Regel durch die Anwendung entsprechener Färbungsalgorithmen auf einer grafischen Darstellung erreicht wird. Wir betrachten Distanz-2-Färbung des bipartiten Graphen bzw. Star/Acyclic Färbung der Adjazenzgraphen der Jacobi- bzw. Hesse-Matrix. Wir nutzen die ColPack-Implementierungen dieser Algorithmen. Um eine bessere Kompression zu erzielen, unterscheiden wir zwischen variablen und konstanten Nichnullen, wobei letztere an allen Stellen unverändert bleiben, an denen der Kontrollfluss des darunter liegenden Programms unverändert bleibt. Daher muss nur der variable Teil des jeweiligen Musters zur Laufzeit berechnet werden. Wir stellen allgemeine Laufzeit-Algorithmen zur Verfügung, um die Variablen und Konstanten zu berechnen; wir testen ihre Leistung im Sinne der Laufzeit und erzielter Farben im Prozess der dünnbesetzten Jacobi- und Hesse-Akkumulation. Darüberhinaus präsentieren wir einen Algorithmus, welches das Dünnbesetztheitsmuster der Hesse-Matrix, das wir als das konservative Muster bezeichnen, überschätzt. Das ist das Resultat der Ausnutzung der parziellen Separabellität der zugrunde liegenden Funktion. Wir präsentieren numerische Resultate im Sinne der Laufzeit und der erzielten Farben und vergleichen diese mit denen des genauen Nichtnull-Musters. Die Laufzeitkomplexität der letzteren ist quadratisch. Schließlich erweitern wir den konservativen Algorithmus zu einer rekursiven Version, die wir als das rekursive Muster der Hesse bezeichnen. Der rekursive Algorithmus soll die Richtung des Genauen konvergieren für ausreichend große Rekursionstiefe. Dabei ergibt sich für die Rekursionstiefe eins genau das gleiche Muster wie das konservative.

The background of this thesis is algorithmic differentiation (AD) of in practice very computationally expensive vector functions given as computer programs. Traditionally, most AD software provide forward and reverse modes of AD to calculating the Jacobian matrix accurately at a given point on some kind of internal representation kept on memory or hard disk. In fact, the storage is known to be the bottleneck of AD to handle larger problems efficiently, especially, in reverse mode. The forward mode AD can be implemented very cheaply in terms of memory by single forward propagation of directional derivatives at runtime. However, the reverse mode needs to store some data in the so-called forward sweep to allow the data flow reversal needed for backward propagation of adjoints. The latter is recently the focus of ongoing research activities of the AD community for scalar functions as a single application of reverse mode is enough to accumulate the entire gradient of the target function. To handle the memory bottleneck, checkpointing schedules e.g. revolve have been developed for time-dependent problems. However, they require user's knowledge in both the function as well as the reverse mode AD. In this context, we aim to provide a tool, which minimizes non-AD user's effort in application of the reverse mode AD on their problems for large dimensions. Moreover, we investigate methods to improve the exploitation of structural sparsity of in general derivative tensors such as Jacobians and Hessians. Existing methods are based on the knowledge of the nonzero pattern of target derivative structures, where a compression is usually achieved by the application of some coloring algorithms to a graphical representation. We consider partial distance-2 coloring and star/acyclic coloring of the bipartite and adjacency graph of Jacobians and Hessians, respectively, provided by the coloring package ColPack. To achieve better compression, we distinguish between variable and constant nonzeros, where the latter is supposed to be unchanged at all those points of interest with fix flow of control. Hence, only the former is needed to be computed at runtime. Therefore, general runtime algorithms are provided to compute the variable pattern and the constant entries. We test also their performance in both runtime and achieved colors in the process of sparse Jacobian and Hessian computation. Furthermore, we present an algorithm to overestimate the Hessian sparsity pattern that is referred to as the conservative Hessian pattern estimation. It is gained by exploiting the partial separability of the underlying function. We present numerical results on the computational cost as well as the coloring performance in terms of runtime and achieved colors of the conservative pattern and compare them with those of the exact (nonzero) Hessian pattern. The computational complexity of the latter is known to be quadratic. Finally, the conservative algorithm is refined to a recursive version that is referred to as the recursive Hessian pattern estimation. The recursive algorithm is supposed to converge to the exact one in both runtime and the resulting pattern for sufficiently large recursion level. Thereby, the recursion level one yields exactly the same pattern as the conservative one.

Fulltext:
PDF
(additional files)