Towards an optimal trade off between recalculations and taping in reverse mode AD
by
Ralf Giering
Jet-Propulsion-Laboratory
Coauthors: Thomas Kaminski (Max-Planck-Institut fuer Meteorologie, Hamburg)

In the reverse mode of AD required intermediate results must be provided in an order that is opposite to that of their original computation. This can be realized in two ways: Firstly, the intermediate results can be stored on a tape during an initial function evaluation and restored whenever they are required during the derivative computations. Secondly, the required variables can be recomputed during the derivative computations. Any combination of both strategies results in taping some intermediate results and recalculating others from the independent or taped variables. The necessary run-time and memory resources for taping and recalculation can be estimated roughly by a simple architecture/compiler model. After assigning specific costs to these resources the optimal strategy can be derived from a graph representation. No AD-tool is yet able to find automatically a optimal strategy, and only TAMC and Odyssee provide mechanisms for the user to influence the strategy at all. We describe the necessary code analysis which is very similar to that of automatic parallizing compilers.

http://puddle.mit.edu/~ralf/tamc

Date received: December 29, 1999