Systolic Automatic Differentiation of Straight-Line Code on Meshes of Trees
by
H. Martin Bücker
Institute for Scientific Cmputing, Aachen University of Technology
Coauthors: Kristopher R. Buschelman (Mathematics and Computer Science Division, Argonne National Laboratory), Paul D. Hovland (Mathematics and Computer Science Division, Argonne National Laboratory)

Given a serial computer program to compute a function, it is shown how to derive, in a completely automatic fashion, a parallel program evaluating not only the function but also the first order derivatives of that function. To this end, it is assumed that a serial straight-line code is given consisting solely of statements assigning a real constant to a variable as well as of binary real additions and multiplications. Given such a code with N statements, the parallel algorithm to evaluate and carry forward a gradient of each intermediate program variable with respect to n input variables simultaneously with the evaluation of the program variable itself requires O(n logN logd N) scalar operations on a parallel computer whose network architecture is an N×N×N mesh of trees. Here, the parameter d represents, in a sense to be defined, a measure of the complexity of the straight-line code. In the worst case, the degree can be exponential in N. However, for many problems d is polynomial in N leading to a running time of O(n  log² N).

http://www.sc.rwth-aachen.de/buecker/ad2000.html

Date received: February 11, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cads-72.