Modeling the performance of interface contraction

ABSTRACT

Automatic differentiation is a technique used to transform a computer code implementing some mathematical function into another program capable of evaluating the function and its derivatives. Compared to numerical differentiation, the derivatives obtained from applying automatic differentiation are free from truncation error, and their computation often requires less time. To increase the efficiency of a black box approach of automatic differentiation, a technique called interface contraction may be used. Interface contraction exploits the local structure of a code to temporarily reduce the global number of derivatives propagated through the code. Two performance models are introduced to predict the potential improvement in the execution time of a program making use of interface contraction compared to a program generated by a black box approach of automatic differentiation. The performance models are validated by numerical experiments carried out on different computing platforms. The computer codes used in the experiments stem from the application areas of neutron scattering and biostatistics.

REFERENCES

• 1: Amdahl, G. M. 1967. Validity of a single processor approach to achieving large scale computer capabilities. In Proceedings of AFIPS Spring Joint Computer Conference Vol. 30. Atlantic City, NJ, 438--485.
• 2: Berz, M., Bischof, C., Corliss, G., and Griewank, A. 1996. Computational Differentiation: Techniques, Applications, and Tools. SIAM, Philadelphia.
• 3: Christian Bischof , Peyvand Khademi , Andrew Mauer , Alan Carle, Adifor 2.0: Automatic Differentiation of Fortran 77 Programs, IEEE Computational Science & Engineering, v.3 n.3, p.18-32, September 1996 [doi>10.1109/99.537089]
• 4: Bischof, C., Khademi, P., Bouaricha, A., and Carle, A. 1996b. Efficient computation of gradients and Jacobians by dynamic exploitation of sparsity in automatic differentiation. Optimization Methods and Software 7, 1 (July), 1--39.
• 5: Bischof, C. H. and Haghighat, M. R. 1996. Hierarchical approaches to automatic differentiation. In M. Berz, C. Bischof, G. Corliss, and A. Griewank, Computational Differentiation: Techniques, Applications, and Tools. SIAM, Philadelphia, (1996).
• 6: H. Martin Bücker , Arno Rasch, Efficient derivative computations in neutron scattering via interface contraction, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508830]
• 7: George Corliss , Christèle Faure , Andreas Griewank , Lauren Hascoët , Uwe Naumann, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 8: Andreas Griewank, Evaluating derivatives: principles and techniques of algorithmic differentiation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 9: Griewank, A. and Corliss, G. 1991. Automatic Differentiation of Algorithms. SIAM, Philadelphia.
• 10: P. Hovland , C. Bischof , D. Spiegelman , M. Casella, Efficient Derivative Codes through Automatic Differentiation and Interface Contraction: An Application in Biostatistics, SIAM Journal on Scientific Computing, v.18 n.4, p.1056-1066, July 1997 [doi>10.1137/S1064827595281800]
• 11: Pele, H. W., Hempelmann, R., Prager, M., and Zeidler, M. D. 1991. Dynamics of 18-crown-6 ether in aqueous solution studied by quasielastic neutron scattering. Berichte der Bunsen-Gesellschaft für physikalische Chemie 95, 5, 592--598.
• 12: Rall, L. B. 1981. Automatic Differentiation: Techniques and Applications. Lecture Notes in Computer Science, vol. 120. Springer Verlag, Berlin.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Automatic differentiation

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.m Miscellaneous

General Terms:
Measurement, Performance

Keywords:
Automatic differentiation, forward mode, interface contraction, local preaccumulation, performance modeling