Publication: A Matrix-Matrix Multiplication Approach to the Automatic Differentiation and Parallelization of Straight-Line Codes
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

A Matrix-Matrix Multiplication Approach to the Automatic Differentiation and Parallelization of Straight-Line 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 8--12, 2002

Editor(s)
U. Brinkschulte, K. -E. Großpietsch, C. Hochberger, E. W. Mayr

Year
2002

Publisher
VDE Verlag

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

AD Theory and Techniques
Parallelism

BibTeX
@INPROCEEDINGS{
         Bucker2002AMM,
       author = "H.~M.~B{\"u}cker and K.~R.~Buschelman and P.~D.~Hovland",
       title = "A Matrix-Matrix Multiplication Approach to the Automatic Differentiation and
         Parallelization of Straight-Line Codes",
       booktitle = "Workshop Proceedings of the International Conference on Architecture of Computing
         Systems ARCS~2002, Germany, April~8--12, 2002",
       editor = "U. Brinkschulte and K.-E. Gro\ss{}pietsch and C. Hochberger and E. W. Mayr",
       publisher = "VDE~Verlag",
       pages = "203--210",
       address = "Berlin",
       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_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 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.",
       ad_theotech = "Parallelism",
       year = "2002"
}


back
  

LinkedIn:    Contact:
autodiff.org
Username:
Password:
(lost password)