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

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(M log d N) scalar operations, where O(M) is the time complexity of a parallel multiplication of two dense N times N 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.