Publication: Improving the Performance of the Vertex Elimination Algorithm for Derivative Calculation
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Improving the Performance of the Vertex Elimination Algorithm for Derivative Calculation

- incollection -
 

Author(s)
Mohamed Tadjouddine , Frances Bodman , John D. Pryce , Shaun A. Forth

Published in
Automatic Differentiation: Applications, Theory, and Implementations

Editor(s)
H. M. Bücker, G. Corliss, P. Hovland, U. Naumann, B. Norris

Year
2005

Publisher
Springer

Abstract
In previous work [TOMS, 2004, 30(3), 266--299], we used Markowitz-like heuristics to find elimination sequences that minimise the number of floating-point operations (flops) for vertex elimination Jacobian code. We also used the depth-first traversal algorithm to reorder the statements of the Jacobian code with the aim of reducing the number of memory accesses. In this work, we study the effects of reducing flops or memory accesses within the vertex elimination algorithm for Jacobian calculation. On RISC processors, we observed that for data residing in registers, the number of flops gives a good estimate of the execution time, while for out-of-register data, the execution time is dominated by the time for memory access operations. We also present a statement reordering scheme based on a greedy list scheduling algorithm using ranking functions. This statement reordering will enable us to trade off the exploitation of the instruction level parallelism of such processors with the reduction in memory accesses.

Cross-References
Bucker2005ADA

AD Tools
EliAD

AD Theory and Techniques
X-Country

BibTeX
@INCOLLECTION{
         Tadjouddine2005ItP,
       author = "Mohamed Tadjouddine and Frances Bodman and John D. Pryce and Shaun A. Forth",
       title = "Improving the Performance of the Vertex Elimination Algorithm for Derivative
         Calculation",
       editor = "H. M. B{\"u}cker and G. Corliss and P. Hovland and U. Naumann and B.
         Norris",
       booktitle = "Automatic Differentiation: {A}pplications, Theory, and Implementations",
       series = "Lecture Notes in Computational Science and Engineering",
       publisher = "Springer",
       year = "2005",
       abstract = "In previous work [TOMS, 2004, 30(3), 266--299], we used Markowitz-like heuristics
         to find elimination sequences that minimise the number of floating-point operations (flops) for
         vertex elimination Jacobian code. We also used the depth-first traversal algorithm to reorder the
         statements of the Jacobian code with the aim of reducing the number of memory accesses. In this
         work, we study the effects of reducing flops or memory accesses within the vertex elimination
         algorithm for Jacobian calculation. On RISC processors, we observed that for data residing in
         registers, the number of flops gives a good estimate of the execution time, while for
         out-of-register data, the execution time is dominated by the time for memory access operations. We
         also present a statement reordering scheme based on a greedy list scheduling algorithm using ranking
         functions. This statement reordering will enable us to trade off the exploitation of the instruction
         level parallelism of such processors with the reduction in memory accesses.",
       crossref = "Bucker2005ADA",
       ad_tools = "EliAD",
       ad_theotech = "X-Country",
       pages = "111--120",
       doi = "10.1007/3-540-28438-9_10"
}


back
  

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