Compiler-based Automatic Differentiation (CompAD)

---

GOTO: Motivation - Overview - CompAD-I - CompAD-II - CompAD-III

---

Motivation

Automatic differentiation has been proven extremely useful in the context of numerous applications of computational science and engineering requiring numerical methods that are based on derivative information. Refer to [M1-M4] for details. Integration of AD into an industrial-strength compiler has the potential of making this technology more robust and efficient as well as user-friendly. The automatic generation of adjoint code is of particular interest to scientists and engineers aiming at a transition from the pure numerical simulation to optimization of the underlying models and/or their parameters. ClickHere for an illustration of the power of adjoint codes.

[M1] Corliss, Griewank: Automatic Differentiation: Theory, Implementation, and Application. Proceedings Series, SIAM, 1991.

[M2] Berz, Bischof, Corliss, Griewank: Computational Differentiation: Techniques, Applications, and Tools. Proceedings Series, SIAM, 1996.

[M3] Corliss, Faure, Griewank, Hascoet, Naumann: Automatic Differentiation of Algorithms - From Simulation to Optimization. Springer, 2002.

[M4] Bücker, Corliss, Hovland, Naumann, Norris: Automatic Differentiation: Applications, Theory, and Tools. Numer 50 in Lecture Notes in Computational Science and Engineering, Springer, 2005.

[GOTO top]

Overview

The CompAD project aims to put Automatic Differentiation into the NAGWare Fortran compiler (in the following simply referred to as "the compiler"). We are currently in the third phase of the project (see CompAD-III). The ongoing work is presented in the context of the results of the past tow parts of the project (see CompAD-I and CompAD-II).

[GOTO top]

CompAD-III (Oct 2008 - Sep 2010)

Aims

• Optimization of Data-Flow Reversal
  • automatic call graph reversal; heuristics for near optimal call graph reversal (combinations of split and joint with argument and with result checkpointing reversal modes) based on static and/or dynamic (profiling) complexity estimates
  • automatic loop-level checkpointing
• Support for Second Derivatives
  • reapplication of compiler to unparsed tangent-linear and adjoint Fortran codes
  • increased efficiency of tangent-linear code generated by ADAC; coupling with compiler to generate second-order tangent-linear and adjoint codes
  • application of ADOL-C and/or ADIC to unparsed tangent-linear and adjoint C-codes
• Applications from Science and Engineering
  • shape optimization in collaboration with QinetiQ
  • sensitivity analysis with the Met Office's Ported Unified Model
  • adjoint of a structural dynamics solver provided by Prof. Keane from the University of Southampton
  • coupling the compiler with the NAG Fortran 90 Library
  • further commerzialisation of the project's results through NAG

[GOTO top]

Ongoing Activities

• Adjoint Code Generation [more]
• Parallel Taping [more]
• Toward a C++ Back-End [more]
• Tangent-Linear MPI Code [more]
• Checkpointing [more]
• Differentiation of Complex Arithmetic [more]
• External Adjoint Functions In Reverse Tape Interpretation (STCE Own Tape) [more]
• External Adjoint Functions In ADOL-C [more]
• Examples of Implementation of External Adjoint Functions (Own Tape and ADOL-C) In Jurassic [more]

[GOTO top]

CompAD-II (Oct 2006 - Sep 2008)

Aims

• automatic generation of adjoint code within the compiler
• static program analysis for optimized derivative code
• support for user-driven checkpointing
• automatic transformation of assembler code in tangent-linear mode (ADAC)
• second-order adjoints by coupling the compiler with ADAC
• sensitivity analysis in shape optimization code provided by QinetiQ
• commercialization of project's results through NAG

Intermediate Results (September 2007)

Theory

• optimal Jacobian accumulation is NP-complete [C2.3]
• optimal data-flow reversal is NP-complete [C2.4]
• an L-attributed grammar for the syntax-directed compilation of tangent-linear code [C2.5]
• an L-attributed grammar for the syntax-directed compilation of adjoint code [C2.6]
• an algorithm for optimal vertex elimination for single-expression-use graphs [C2.9]

Automatic Tangent-Linear Code ...

• ... by automatic type changes and overloading of intrinsic operators and functions (see MoreOnTLbyOverloading)
• ... by automatic type changes and automatic inlining of overloaded of intrinsic operators and functions (corresponds to source transformation; see MoreOnTLCbyInlining)

Automatic Adjoint Code ...

• ... by automatic type changes, overloading of intrinsic operators and functions, and reverse interpretation of program execution mapped into a virtual memory space [C2.2] (see MoreOnAdjointbyOverloading) first version based on preaccumulated statement-level gradients previously used in global forward modeas described in [C1.2]
• ... by transformation of the compilers internal representation of the program (corresponds to source transformation) [C2.1] (see MoreOnAdjointCode)

Tangent-Linear Assembler Code ...

... by transformation of the assembler source [C2.8] (see MoreOnADAC)

Second-Order Adjoint Code ...

• ... by overloading of the interpreter (see first item in section "Automatic Adjoint Code") for a user-defined data-type in tangent-linear mode (see MoreOnSOAbyPureOverloading)
• ... by overloading of the adjoint code (see second item in section "Automatic Adjoint Code") for a user-defined data-type in tangent-linear mode [C2.7] (see MoreOnSOAbyOverloadingAdjoint)
• ... by generation of tangent-linear code for the adjoint assembly code resulting from second item in section "Automatic Adjoint Code" (see MoreOnADAConAdjoint)

Application to Sensitiviy Analysis

Euler Code from QinetiQ

Application to Nonlinear Optimization

Time-dependent optimal control based on compressible Navier-Stokes solver

Commercialization

A Fortran module for tangent-linear mode is considered by NAG in the context of a potential commercialization. Case studies for coupling the compiler with the NAG Fortran 90 Library are being evaluated too.

Bibliography

[C2.1] Maier, Naumann: Intraprocedural adjoint code generated by the differentiation-enabled NAGWare Fortran compiler. Proceedings of 5th International Conference on Engineering Computational Technology, paper 112, pages 1--19. Civil-Comp Press, 2006.

[C2.2] Naumann, Riehme: Computing adjoints with the NAGWare Fortran~95 compiler. In M. Bücker et. al., editors, Automatic Differentiation: Applications, Theory, and Tools, number 50 in LNCSE, pages 159--170. Springer, 2006.

[C2.3] Naumann: Optimal Jacobian accumulation is NP-complete. Math. Prog., Springer. In press. Appeared in Springer's "Online First" section [link].

[C2.4] Naumann: DAG Reversal is NP-Complete. To appear in J. of Discrete Algorithms, Elsevier. Appeared as RWTH Aachen Computer Science Report AIB-2007-05.

[C2.5] Naumann, Gendler, Varnik: On Syntax-Directed Tangent-Linear Code. Proceedings of the IADIS International Conference on Applied Computing, Salamanca, Spain, pages 425-430, IADIS, 2007.

[C2.6] Naumann, Riehme: An L-Attributed Grammar for Adjoint Code. Proceedings of the 1st Workshop on Advances in Programming Languages (WAPL'07), Wisla, Poland, 2007. Appeared as RWTH Aachen Computer Science Report AIB-2007-12.

[C2.7] Naumann, Maier, Riehme, Christianson: Automatic First- and Second-Order Adjoints for Truncated Newton. Proceedings of the Workshop on Computer Aspects of Numerical Algorithms (CANA'07), Wisla, Poland, 2007. Appeared as RWTH Aachen Computer Science Report AIB-2007-13.

[C2.8] Gendler, Naumann, Christianson: Automatic Differentiation of Assembler Code. Proceedings of the IADIS International Conference on Applied Computing, Salamanca, Spain, pages 431-436, IADIS, 2007.

[C2.9] Naumann, Hu: Optimal Vertex Elimination in Single-Expression-Use Graphs. To appear in ACM Transactions on Mathematical Software. Appeared as RWTH Aachen Computer Science Report AIB-2006-08.

[C2.12] Naumann: Call Graph Reversal is NP-Complete. To appear in proceedings of 5th International Conference on Automatic Differentiation, LNCSE, Springer.

[C2.11] Riehme, Stiller, Walther, Naumann: Adjoints for Time-Dependent Optimal Control.To appear in proceedings of 5th International Conference on Automatic Differentiation, LNCSE, Springer.

[C2.15] Stumm, Riehme, Walther, Naumann: Structure-Exploiting Automatic Differentiation of Finite Element Discretizations.To appear in proceedings of 5th International Conference on Automatic Differentiation, LNCSE, Springer.

Currently Being Written...

[C2.10] Christianson, Naumann, Riehme: Unconstrained Nonlinear Optimization with Matrix-Free Truncated Newton. To be submitted to Optimization Methods and Software.

[C2.13] Gendler, Naumann, Riehme, Christianson: On Automatically Generated Tangent-Linear Assembler Code. Technical report.

[C2.14] Maier, Naumann, Riehme, Christianson: Tangent-Linear Fortran Code by Automatic Inlining. Technical report.

[C2.16] Riehme, Naumann, Kopmann: A Tangent-Linear Version of Sisyphe. Technical report.

[GOTO top]

CompAD-I (Jul 2001 - Dec 2002)

Aims

• automatic generation of tangent-linear code within the compiler
• follow-up proposal based on investigation of potential use of compiler for automatic generation of adjoint code

Results

All aims were met. In particular

• tangent-linear mode by overloading [C1.1]
• tangent-linear code based on preaccumulation of local gradients of all assignments [C1.2]
• follow-up proposal leading to ongoing CompAD-II project

Bibliography

[C1.1] Cohen, Naumann, Riehme: Towards Differentiation-Enabled Fortran~95 Compiler Technology. SAC '03: Proceedings of the 2003 ACM symposium on Applied computing, pages 143-147, ACM Press, 2003.

[C1.2] Naumann, Riehme: A Differentiation-Enabled Fortran 95 Compiler. ACM Transactions on Mathematical Software, 31(4), 458--474, 2005.

[GOTO top]