A Matrix-Matrix Multiplication Approach to the Automatic Differentiation and Parallelization of Straight-Line Codes
|Title||A Matrix-Matrix Multiplication Approach to the Automatic Differentiation and Parallelization of Straight-Line Codes|
|Year of Publication||2000|
|Authors||Becker, HM, Buschelman, KR, Hovland, PD|
|Series Title||Workshop Proceedings of the Int'l Conf. on Architecture of Computing Systems ARCS-2002, Germany, April 8-12, 2002|
A Straight-line code, which consists of assignment, addition, and multiplication statements, is an abstraction of a serial computer program to compute a function with n inputs. Given a serial straight-line code with N statements, we derive an algorithm that automatically evaluates not only the function but also its first-order derivatives with respect to the n inputs on a parallel computer. The basic idea of the algorithm is to marry automatic computation of derivatives with automatic parallelization of serial programs. The algorithm requires O(MN log dN) scalar operations, where O(MN) is the time complexity of a parallel multiplication of two dense NxN matrices and d represents a measure of the complexity of the straight-line code. Although d can be exponential in N in the worst case, it tends to be only polynomial in N for many important problems.