The Adjoint Data-Flow Analyses: Formalization, Properties, and Applications

Laurent Hascoët
Mauricio Araya-Polo
(INRIA, BP93, 06902 Sophia-Antipolis, France)

Proceedings of the AD2004 Conference, Chicago, Illinois, july 2005 (13 pages)

Abstract: Automatic Differentiation (AD) is a program transformation that yields derivatives. Building efficient derivative programs requires complex and specific static analysis algorithms to reduce run time and memory usage. Focusing on the reverse mode of AD, which computes adjoint programs, we specify jointly the central static analyses that are required to generate an efficient adjoint code. We use a set-based formalization from classical data-flow analysis to specify Adjoint Liveness, Adjoint Write, and To Be Recorded analyses, and their mutual influences, taking into account the specific structure of adjoint programs. We give illustrations on examples taken from real numerical programs, that we differentiate with our AD tool TAPENADE, which implements these analyses.

Keywords: Automatic Differentiation, Adjoint code, Adjoint algorithm, Data-Flow analysis, Reverse Mode

Full text (pdf)

  author = {Hasco\"et, L. and Araya-Polo, M.},
  title = {The Adjoint Data-Flow Analyses:
           {F}ormalization, Properties, and Applications},
  booktitle = {Automatic Differentiation: {A}pplications, Theory, and Tools},
  series = "Lecture Notes in Computational Science and Engineering",
  note = "Selected papers from AD2004 Chicago, July 2005",
  publisher = "Springer",
  year = 2005