Iteration-wise adjoining
by
Laurent Hascoet
INRIA Sophia-Antipolis
Coauthors: Stefka Fidanova, Christophe Held

The reverse mode of Automatic Differentiation is a software engineering technique that allows analytic computation of gradients in relatively few operations. However, this technique has the drawback that it uses a lot of temporary memory storage. In the case of a parallelizable loop, we propose a specific refinement to this technique, that potentially reduces the memory requirements for such a loop, by a factor equal to the number of parallel iterations.

Analysis of the data-dependence graph of a parallelizable loop, and of its differentiated loops, allows us to perform the differentiation transformation on an iteration-wise basis. This reduces the need for temporary storage, since only one iteration at a time needs to be recorded.

To prove the correctness of this transformation, we first show an isomorphism between the data-dependence graph of a program and the data-dependence graph of the reverse differentiation of this program. Then we show that this isomorphism applied to the parallelizable loop permits iteration-wise differentiation.

This refinement is particularly suitable for assembly loops, that dominate in mesh-based computations. Application is done on the kernel of a real-size Navier-Stokes solver. Correctness of the computed gradient is shown, and improvements in memory usage are measured. We also compare this method with other similar ways to perform automatic differentiation in an iteration-wise manner.

http://homepages.feis.herts.ac.uk/~comqun/AD2000/Ext_Abstracts/hascoet.ps

Date received: February 8, 2000