Exploiting parallelism in automatic differentiation

Abstract:

The numerical methods employed in the solution of many scientific computing problems require the computation of first- or second-order derivatives of a function f: Rn → Rm. We present an approach that, given a serial C program for the computation of f(x), derives a parallel execution schedule for the computation of f and its derivatives in a completely automatic fashion. This is achieved by overloading the computation of f(x) in C++ to obtain a trace of the computations to be performed and then transforming this trace into a data flow graph for the computation of f(x). In addition to the computation of f(x), this graph also allows us to exactly and inexpensively compute derivates of f by the repeated use of the chain rule. Parallelism is exploited in two ways: rows or columns of derivative matrices can be computed by independent passes through the computational graph, and parallelism within the processing of this computational graph can be exploited by processing independent subgraphs concurrently. We present experimental results that show that good performance on sharedmemory machines can be obtained by using a graph interpreter approach. We then present some ideas that are currently under development for improving computational granularity and for implementing parallel automatic differentiation schemes in a portable and more efficient fashion.

Año de publicación:

1991

Keywords:

Fuente:

scopus