TBR analysis in reverse-mode Automatic Differentiation
Laurent Hascoët
Valérie Pascual
(INRIA, BP93, 06902 Sophia-Antipolis, France)
Uwe Naumann
(Math and Comp. Sci. Division, Argonne Nat. Lab., Argonne, IL 60439, USA)
Preprint, Argonne National Laboratory ANL-MCS/P936-0202 and INRIA RR-4856, 2002 (21 pages)
Abstract:The automatic generation of adjoints of mathematical models
that are implemented as computer programs is receiving a increased
attention in the scientific and engineering communities.
Reverse-mode Automatic Differentiation (AD) is of particular interest for
large-scale optimization problems. It allows for the computation of gradients
at a small constant multiple of the cost for evaluating the objective
function itself, that is independent of the number of input parameters.
Source-to-source transformation tools for AD
are available to generate adjoint codes based on the adjoint
version of every statement, built by applying simple
differentiation rules. A reversal of the control flow
of the original program becomes necessary. To guarantee correctness, certain
values that are computed and overwritten in the original program must be made
available in the adjoint program. They can be determined by performing a static
data flow analysis, the so-called TBR analysis. Overestimation of this set
must be kept minimal to get efficient adjoint codes.For many real-world
applications, this efficiency is compulsory to apply a source-to-source
transformation such as AD.
Keywords:
Automatic Differentiation, Adjoint, Gradient, Static analysis,
Data-Flow analysis, Compilation
Full text (pdf)
@techreport{HNP02,
author = {Hasco\"et, L. and Naumann, U. and Pascual, V.},
title = {TBR analysis in reverse-mode Automatic Differentiation},
type = {Preprint},
institution = {Argonne National Laboratory},
number = {ANL-MCS/P936-0202},
note = {also Rapport de recherche \#4856, INRIA},
url = "http://www.inria.fr/rrrt/rr-4856.html",
year = 2002
}