Optimal Program Execution Reversal Schedules
by
Andreas Griewank
Technical University Dresden
Coauthors: Andrea Walther

Optimal Program Execution Reversal Schedules
For adjoint calculations, debugging, interactive control and similar purposes one may need to reverse the execution of a computer program. The simplest option of recording a complete execution log and then reading it backwards requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the 'forward' calculation repeatedly from suitably placed checkpoints. Our goal is to minimize the temporal and spatial complexity as measured by the number of evaluation repeats and the number of checkpoints, respectively.

We present optimal checkpointing schedules for one-step and multi-step evolutions. These might arise for example as discretizations of ODEs by Euler's methods or multi-step schemes, respectively. Furthermore, we present parallel extensions, where auxcilliary processors perform the repeated forward evaluations such that one processor can run backward without any interruption. For either case the length of the evolution that can be reversed is shown to grow exponentially with the number of checkpoints and the number of repetitions or the number of processors.

Date received: August 13, 1999