Efficient reversal of the intraprocedural flow of control in adjoint computations

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.02.038 Byline: Jean Utke (a), Andrew Lyons (a), Uwe Naumann (b) Keywords: Control flow reversal; Adjoint computation; Efficient loop reversal Abstract: Numerical simulations of physical, chemical, and economical processes play an increasingly important role in modern science and engineering. The implementation of mathematical models of real-world applications on a computer facilitates both the speed and the depth of our understanding of the behavior of the respective systems. Derivative models of the computer programs are required to make the transition from pure simulation to the highly desirable optimization of the numerical models with respect to a potentially very large number of input parameters. Such models can be generated automatically from the given numerical program by a source transformation technique known as automatic differentiation. Reversal of the control flow is especially important for the generation of adjoint derivative models. We describe an approach to the control flow reversal of structured programs motivated by the significant weakness of approaches that do not exploit the result of control-flow analysis. Our approach is used to automatically generate adjoint code for numerical programs by semantic source transformation. After a short introduction to applications and the implementation tool set, we motivate the proposed approach with a simple example. We present a novel preaccumulation algorithm for local Jacobian matrices at the level of basic blocks. The main part of the paper covers the reversal of structured control flow graphs. First we show the algorithmic steps for simple branches and loops. We give a detailed algorithm for the reversal of arbitrary combinations of loops and branches based only on the structural information in a general control flow graph. Dependencies between computations and their enclosing control flow constructs can lead to inefficient adjoint code. We formulate a set of conditions that allows for considerable efficiency gains in the adjoint code while permitting a reasonably simple modification of the reversal algorithms for specially designated control flow subgraphs. We present a sensitivity computation of an oceanographic application that illustrates the benefits of this modified approach. Author Affiliation: (a) Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue, Argonne, IL 60438, USA (b) Software and Tools for Computational Engineering, RWTH Aachen University, D-52056 Aachen, Germany Article History: Received 17 February 2006; Accepted 19 February 2006 Article Note: (footnote) [star] The submitted manuscript has been created by the University of Chicago as Operator of Argonne National Laboratory ("Argonne") under Contract No. W-31-109-ENG-38 with the US Department of Energy. The US Government retains for itself, and others acting on its behalf, a paid-up, nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government.