

A MatrixMatrix Multiplication Approach to the Automatic Differentiation and Parallelization of StraightLine Codes
Part of a collection
  

Author(s)
H. M. Bücker
, K. R. Buschelman
, P. D. Hovland

Published in Workshop Proceedings of the International Conference on Architecture of Computing Systems ARCS 2002, Germany, April 812, 2002

Editor(s) U. Brinkschulte, K. E. Großpietsch, C. Hochberger, E. W. Mayr 
Year 2002 
Publisher VDE Verlag 
Abstract A Straightline 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 straightline code with N statements, we derive an algorithm that automatically evaluates not only the function but also its firstorder 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_{N} log d N) scalar operations, where O(M_{N}) is the time complexity of a parallel multiplication of two dense N×N matrices and d represents a measure of the complexity of the straightline code. Although d can be exponential in N in the worst case, it tends to be only polynomial in N for many important problems. 
AD Theory and Techniques Parallelism 
BibTeX
@INPROCEEDINGS{
Bucker2002AMM,
author = "H.~M.~B{\"u}cker and K.~R.~Buschelman and P.~D.~Hovland",
title = "A MatrixMatrix Multiplication Approach to the Automatic Differentiation and
Parallelization of StraightLine Codes",
booktitle = "Workshop Proceedings of the International Conference on Architecture of Computing
Systems ARCS~2002, Germany, April~812, 2002",
editor = "U. Brinkschulte and K.E. Gro\ss{}pietsch and C. Hochberger and E. W. Mayr",
publisher = "VDE~Verlag",
pages = "203210",
address = "Berlin",
abstract = "A Straightline 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 straightline code with~$N$ statements, we derive an algorithm that automatically
evaluates not only the function but also its firstorder 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_N
\log d N)$ scalar operations, where~$O(M_N)$ 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 straightline code. Although $d$ can be exponential in~$N$ in the worst case, it
tends to be only polynomial in~$N$ for many important problems.",
ad_theotech = "Parallelism",
year = "2002"
}
 
back

