Algorithmic differentiation of Java programs

  • Algorithmische Differentiation von Java Programmen

Slusanschi, Emil-Ioan; Bischof, Christian (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2008)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2008

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.

Identifikationsnummern