Increasing the granularity of parallelism and reducing contention in automatic differentiation.

摘要

The automatic differentiation package ADOL-C of Griewank and Juedes, traces the computation of a function whose derivative is to be computed, and then subsequently propagates adjoint values long these traces paths according to the chain rule. While a sequential implementation of the reverse mode can utilize this trace by traversing it in reverse order, a parallel implementation must build the entire computational graph, as different processors will each simultaneously be working on different sections of the trace. In a sequential implementation, the linearized trace inherently obeys the dependencies of the function evaluation. In a parallel implementation, however, there must be a mechanism to determine whether a node's dependencies have been resolved yet, meaning that the node's adjoint value is computable. A node in the graph must represent a quantity of arithmetic operations large enough for a processor to do enough computation before it must communicate the result to another processor, but small enough for there to be enough nodes in the graph to allow many processors to work simultaneously. Sinks are bottlenecks for efficient parallel computation, as their many dependencies mean that many processors will contend for them simultaneously. These two factors are both familiar problems in parallel computation; the first is an issue of granularity, while the second is an issue of contention. As a first step toward achieving an efficient parallel implementation, we present a system for construction of a computational graph from ADOL-C's computational trace, as well as two transformations for this graph, hoisting and splitting, which improve its computational granularity and reduce contention, respectively. 2 refs., 6 figs.