12. Reversal Schedules and Checkpointing
Society for Industrial and Applied Mathematics eBooks · 2008
The key difficulty in adjoining large evaluation programs is their reversal within a reasonable amount of memory. Performing the actual adjoint operations is a simple task compared to (re) producing all intermediate results in reverse order. In fact, as one can see in Table 4.8, just a couple of additions and multiplications need to be performed for each value that was computed and "taped" on the way forward. As we saw in section 4.3, some of these memory moves can be avoided by inverting certain incremental operations as listed in Table 4.10. However, for general nonlinear problems, we cannot expect that even the most selective storage strategy reduces the required memory traffic by more than a small constant. The problem of reversing a program execution has received some perfunctory attention in the computer science literature (see, e.g., [Ben73] and [vdS93]). The first authors to consider the problem from an AD point of view were apparently Volin and Ostrovskii [VO85] and later Horwedel [Hor92].Checking the MemoryA good-size function evaluation might easily run for 10 minutes on a superscalar chip sustaining a rate of several hundred million arithmetic operations per second. If all intermediate results were saved, this would amount to a total memory requirement of roughly a terabyte (= 1012 bytes). If we were a lot more selective about savings and the processor was not performing quite as many flops, we might get by with several gigabytes, which could be available as external memory.However, that would barely make the whole process computationally attractive since storing and retrieving some gigabytes may take a while, even under favorable circumstances. Here we have already taken into account the strictly sequential nature of "tape" accesses in the basic reverse mode specified in Table 4.4. Hence nothing can be gained by sophisticated "external memory algorithms" that have been developed for computational geometry and other applications with very large and nonsequential data access requirements.