Algorithmic differentiation of Java programs

Slusanschi, Emil-Ioan; Bischof, Christian

doi:2339

Algorithmic differentiation of Java programs = Algorithmische Differentiation von Java Programmen

Slusanschi, Emil-Ioan (Author)

2008

Verantwortlichkeitsangabevorgelegt von Emil-Ioan Slusanschi

ImpressumAachen : Publikationsserver der RWTH Aachen University 2008

UmfangXIII, 175 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2008

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Bischof, Christian (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2008-04-11

Online
URN: urn:nbn:de:hbz:82-opus-23395
URL: https://publications.rwth-aachen.de/record/50080/files/Slusanschi_Emil-Ioan.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Automatische Differentiation (Genormte SW) ; Java (Genormte SW) ; Framework <Informatik> (Genormte SW) ; Optimierender Compiler (Genormte SW) ; Byte-Code (Genormte SW) ; Informatik (frei) ; Automatic Differentiation (frei) ; Framework (frei) ; Optimizing Compilers (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: I.2.2 Auto * I.1.2 Algo * D.2.2 Desi * D.3.4 Proc * D.2.3 Codi

Kurzfassung
Ableitungen sind eine wichtige Komponente in vielen Gebieten der Natur- und Ingenieurwissenschaften, deren akkurate Berechnung häufig bei verschiedenen wissenschaftlichen Anwendungen benötigt wird. Ein Ansatz zur Berechnung von Ableitung ist die Technik des automatischen Differenzierens (AD). Die Tatsache, dass momentan keine verfügbare AD-Implementierung für Java existiert, war Motivation für die Entwicklung eines AD-Werkzeugs für die Programmiersprache Java. Aufgrund der Portabilität und Erleichterung in Bezug auf Standardisierungen durch den Java-Bytecode, wurde ADiJaC (Automatisches Differenzieren für Java-Klassendateien) als Werkzeug für AD Transformationen in Java Klassendateien implementiert. Um AD allerdings effektiv zu implementieren, ist anstelle des unstrukturierten Bytecodes eine deutlich abstraktere interne Repräsentation für die Durchführung von AD-Transformationen nötig. Eines der Hauptziele dieser Arbeit war das Herausarbeiten einer Ebene für die Zwischenrepräsentationen passend für AD-Transformationen und ihrer nacheinander folgenden Implementierung für Java-Bytecode Programme. Die Notwendigkeit für eine vereinheitlichte Zwischenrepräsentation als Basis für alle Arten von Programmtransformation führte zur Entwicklung von IR’s, wie Jimple oder Grimp aus dem SOOT-Framework. Auf dieser Ebene sind genug Informationen über den Programmcode verfügbar, während ein brauchbarer Abstraktionslevel erhalten bleibt. Wie wir konstruktiv in dieser Arbeit zeigen können, erlaubt diese Ebene der Abstraktion eine effiziente Implementierung von AD-spezifischen Transformationen. Das ADiJaC Werkzeug implementiert diese AD-Transformationen für das Vorwärtsverfahren, gleichermaßen für den Skalar- als auch für den Vektormodus, mit Unterstützung der vollständigen Java-2 Mathematik Bibliothek. Die Berechnung im Rückwärtsverfahren besteht aus zwei Hauptdurchläufen: einem Vorwärts- und einem Rückwärtslauf. Ersterer wird angewandt, um die erforderlichen Zwischenvariablen zu speichern, während Letzterer die benötigten Adjungierten berechnet. ADiJac implementiert die sogenannte Joint-Reversal-Strategie und speichert die Kontextvariablen auf einem lokalen Stack, was günstiger ist, als diese neu zu berechnen. Die Tatsache, dass die Stack-Objekte lokal in jeder neuen Adjoint-Methode sind, führt, gekoppelt mit der Möglichkeit einer on-demmand garbage collection, zu einer besonders effizienten Umsetzung dieses Ansatzes. Unter Beachtung, dass Schleifen Strukturen durch eine Kombination von if und goto Statements repräsentiert werden, und dies zu Missverständnissen mit herkömmlichen bedingten Sprüngen in den SOOT IR’s führen kann, ist eine genaue Identifizierung dieser Strukturen von entscheidender Bedeutung. Es wurden so genannte loopPass und ifPass Transformationen implementiert, welche diese Strukturen genau erfassen und eine effiziente Implementierung von AD Transformationen für das Vorwärts- und Rückwärtsverfahren zulassen. Mit Hilfe von Markern, und unter Ausnutzung der internen Daten-Struktur und spezieller Algorithmen, kann ADiJaC die Schleifen-Informationen aus dem unstrukturierten Java-Bytecode entnehmen. Dies ermöglicht die Implementation von effizienten AD-Transformationen. Auch werden Ausnahme-Behandlung und Warnmeldungen für beide AD-Modi unterstützt. Da die MINPACK-2 Programmsammlung oft als standard AD-Testumgebung genutzt wird, wurde die Genauigkeit und Korrektheit der AdiJaC Transformationen für das Vorwärts- und Rückwärtsverfahren an diesen Programmbeispielen mit Erfolg überprüft. Die Laufzeit und Speicheranforderungen für diese Probleme zeigten, dass ein korrekter und effizienter Code von ADiJaC generiert wurde. Der von ADiJaC generierte Ableitungscode wurde auch mit dem äquivalenten von Tapenade generierten Fortran-Programmcode vergleichen. Dabei steht AdiJaC recht gut im Vergleich zum robusten, gut etablierten und verlässlichen Tapenade in Bezug auf Performance dar. Außerdem wurde der Speedup und die Effizienz für eine Thread-basierte Parallelisierung mit Hilfe der so genannten Derivative Strip-Mining-Technik gezeigt. Die Ergebnisse demonstrieren, dass die meisten AD-erweiterten Programme sehr gut auf Shared-Memory-Plattformen skalieren. Die Entwicklung von ADiJaC wird weiter fortgeführt. Zukünftige Optimierungen beinhalten Schleifen-Zusammenführungen der Ableitungs-Berechnungen für das Vektor-Vorwärtsverfahren. Damit werden Iterationen über Ableitungs-Vektoren zusammengeführt, welche ursprünglich von verschiedenen Statements herrühren. Für das Rückwärtsverfahren gilt, dass bei den automatischen Ableitungen realer Anwendungen ein Hauptanteil der Laufzeit für die Stack-Operationen aufgebracht wird, die das Speichern und Zurücklesen der Zwischenwerte organisiert. Dementsprechend sollen diese Operationen mit Hilfe von Analysen minimiert werden, um die absolute Anzahl von zu speichernden Zwischenwerten zu reduzieren, ähnlich wie in Tapenade’s TBR.

Derivatives are a crucial component in many areas of science and engineering, and their accurate evaluation is often required in various scientific applications. One technique widely used to obtain computer derivatives is Automatic Differentiation (AD). The fact that to date no usable AD tool implementation exists for Java motivated the development of an AD tool for the Java language. Because of the portability and simplicity in terms of standardization provided by the Java bytecode, our ADiJaC (Automatic Differentiation for Java Class files) tool implements AD transformations on Java classfiles. However, to effectively implement AD, a more abstract internal representation than the unstructured bytecode for performing AD transformations is required. One of the main goals of this work has been the identification of a level of intermediate representations suitable for automatic differentiation transformations and their subsequent implementation for Java bytecode programs. The need for a unified intermediate representation to be used as the basis for all kinds of program transformations, has lead to the development of IRs such as Jimple or Grimp in the Soot framework. At this level, enough information about the program code is available, while maintaining a useful level of abstraction. As we constructively show in our work, this level of abstraction also enables efficient implementation of AD specific transformations. The ADiJaC tool implements these AD transformations in the forward mode, for the scalar and vector modes alike, with support for the entire Java 2 Math library. Moreover, ADiJaC deals with the new issues appearing in the semantics of automatic differentiation transformations due to problems such as the need to “deep-clone” certain objects in order to obtain local copies of these objects, instead of simple references to them. The reverse mode implementation consists of two main sweeps: the forward and reverse. The former is used to save the necessary intermediate variables while the latter computes the required adjoints. ADiJaC saves context variables on a local stack, rather than recompute them, implementing a so-called “joint” reversal strategy. The fact that the stack objects are local to each new adjoint method, coupled with the ability to use on-demand garbage collection, leads to a particularly efficient implementation of this approach. Considering that loop structures are represented by a combination of if and goto statements, and that they can be confused with the traditional conditional statements in the Soot IRs, it becomes a necessity to properly identify these structures. We implement transformations called loopPass and ifPass that capture this structure and effectively deal with it in implementing forward and reverse mode AD transformations. Using tags, internal data-structures and specific algorithms, ADiJaC extracts loop information from the unstructured Java bytecode, thus enabling the implementation of efficient AD transformations. Exception handling and warnings reporting is also supported for both AD modes. The accuracy and correctness of both forward and reverse mode ADiJaC transformations were successfully tested on codes from the MINPACK-2 test problem collection – often used as standard AD test-cases. The runtime and memory requirements for these problems showed that a correct and efficient code is being generated by ADiJaC. ADiJaC-generated derivative code was also compared to Tapenade-generated code for equivalent Fortran codes, and ADiJaC fared quite well against the robust, well-established and reliable Tapenade ADtool in performance comparisons. The speedup and efficiency obtained for a “derivative strip-mining” technique through thread-based parallelization of the forward implementation was also shown. The results demonstrate that most AD-enhanced codes scale quite well on shared-memory platforms. The development of the ADiJaC tool is a continuing process. Future optimizations include loop fusion for the derivative computation in the vector forward mode to join together iterations over the derivative vectors coming from different statements, whenever the dependencies in the original code allow for it. In the reverse mode approach to automatic differentiation of real applications, a substantial amount of the total execution time is spent with the stack operations – for saving and retrieving the intermediate values. Accordingly, these operations should be minimized by using analyses similar to Tapenade’s TBR, meant to reduce the number of values being stored.

Fulltext:
PDF