Reversal Schedules for Adjoining Structured Programs

Parameter Identification and Design Optimization require the differentiation of residual functionals with respect to very large numbers of variables. These objective functions are often evaluated by extensive simulation codes involving numerical iterations or integrations over many (pseudo-) time steps. The main difficulty in computing the objective gradient by the otherwise highly efficient adjoint method is the reversal of the forward simulation within a reasonable amount of internal and external memory.

The execution of a general programs generates a tree of run-time subroutine calls. Each subroutine may be reversed in one of two modes, split or joint. The spatial and temporal complexity of the resulting reversal schedules are determined by the height, width and other topological properties of the calling tree. We present reversal strategies that are provably optimal on single and multiple processor machines. This result applies only to certain calling trees structures but all other trees can be rewritten into a suitable form. The size of reversable problems grows exponential in the available resources: memory, run-time and number of processors.