A Matrix-Matrix Multiplication Approach to the Automatic Differentiation and Parallelization of Straight-Line Codes

TitleA Matrix-Matrix Multiplication Approach to the Automatic Differentiation and Parallelization of Straight-Line Codes
Publication TypeReport
Year of Publication2000
AuthorsBecker, HM, Buschelman, KR, Hovland, PD
Series TitleWorkshop Proceedings of the Int'l Conf. on Architecture of Computing Systems ARCS-2002, Germany, April 8-12, 2002
Pagination203-210
Date Published10/2000
InstitutionVDE Verlag
Other NumbersANL/MCS-P854-1000
Abstract

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.

PDFhttp://www.mcs.anl.gov/papers/P854.ps.Z