Optimal program execution reversal

Abstract

For adjoint calculations, debugging, 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 auxiliary 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 either the number of repetitions or the number of processors.