The Data-Dependence Graph of Adjoint Programs

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

INRIA Research Report #4167, april 2001 (17 pages)

Abstract: Automatic Differentiation is a technique that permits generation of adjoint programs, which compute gradients. In scientific computation, these gradients are a fundamental tool for optimization or data assimilation. Computation of a gradient is relatively expensive, and should therefore be optimized whenever possible. The study of these program optimizations is most often based on the data-dependence graph. Under precise assumptions, we prove that the adjoint program's data-dependence graph is isomorphic to a sub-graph of the original data-dependence graph. The proof relies on a refined definition of the notion of data-dependence, and on a formal definition of adjoint programs in terms of products of local Jacobian matrices. This theorem can be used to transpose optimizations of the original program, to the adjoint program. It can also justify specific transformations on the adjoint. We give some examples of such applications

Keywords: Automatic Differentiation, reverse mode, adjoints, gradients, data-dependences, parallelization, Memory optimization

Full text (pdf)


@techreport{Hascoet2001TDG,
  author = {Hasco\"et, L.},
  title = {The Data-Dependence Graph of Adjoint Programs},
  institution = {INRIA},
  type = {Research Report},
  number=4167,
  url = "http://www.inria.fr/rrrt/rr-4167.html",
  year=2001
}