Efficient reversal of the intraprocedural flow of control in adjoint computations

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. (C) 2006 Elsevier Inc. All rights reserved.