Comparison of two activity analyses for automatic differentiation: context-sensitive flow-insensitive vs. context-insensitive flow-sensitive

ABSTRACT

Automatic differentiation (AD) is a family of techniques to generate derivative code from a mathematical model expressed in a programming language. AD computes partial derivatives for each operation in the input code and combines them to produce the desired derivative by applying the chain rule. Activity analysis is a compiler analysis used to find active variables in automatic differentiation. By lifting the burden of computing partial derivatives for passive variables, activity analysis can reduce the memory requirement and run time of the generated derivative code. This paper compares a new context-sensitive flow-insensitive (CSFI) activity analysis with an existing context-insensitive flow-sensitive (CIFS) activity analysis in terms of execution time and the quality of the analysis results. Our experiments with eight benchmarks show that the new CSFI activity analysis runs up to 583 times faster and overestimates up to 18.5 times fewer active variables than does the existing CIFS activity analysis.

REFERENCES

• 1: http://mitgcm.org/.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Brett M. Averick, Richard G. Garter, and Jorge J. More. MINPACK-2 Test Problem Collection. Technical Memorandum ANL/MCS-TM-150, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, May 1991.
• 4: Martin Berz, Christian H. Bischof, George F. Corliss, and Andreas Griewank, editors. Computational Differentiation: Techniques, Applications, and Tools. SIAM, Philadelphia, PA, 1996.
• 5: 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]
• 6: Mike Fagan and Alan Carle. Activity Analysis in ADIFOR: Algorithms and Effectiveness. Technical Report TR04-21, Department of Computational and Applied Mathematics, Rice University, Houston, TX, November 2004.
• 7: Message Passing Interface Forum. MPI: A message-passing interface standard. International Journal of Supercomputer Applications, 8(3/4):165--414, 1994.
• 8: Andreas Griewank and George F. Corliss, editors. Automatic Differentiation of Algorithms: Theory, Implementation, and Application. SIAM, Philadelphia, PA, 1991.
• 9: Laurent Hascoët , Uwe Naumann , Valérie Pascual, "To be recorded" analysis in reverse-mode automatic differentiation, Future Generation Computer Systems, v.21 n.8, p.1401-1417, October 2005 [doi>10.1016/j.future.2004.11.009]
• 10: Uday P. Khedker , Dhananjay M. Dhamdhere, A generalized theory of bit vector data flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1472-1511, Sept. 1994 [doi>10.1145/186025.186043]
• 11: Barbara Kreaseck, Luis Ramos, Scott Easterday, Michelle Strout, and Paul Hovland. Hybrid static/dynamic activity analysis. In Proceedings of the 3rd International Workshop on Automatic Differentiation Tools and Applications (ADTA '04), Reading, England, 2006.
• 12: Arun Lakhotia, Rule-based approach to computing module cohesion, Proceedings of the 15th international conference on Software Engineering, p.35-44, May 17-21, 1993, Baltimore, Maryland, United States
• 13: Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
• 14: Thomas Reps , Genevieve Rosay, Precise interprocedural chopping, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.41-52, October 12-15, 1995, Washington, D.C., United States
• 15: Rice University. Open64 project. http://www.hipersoft.rice.edu/open64/.
• 16: Marc Shapiro, II , Susan Horwitz, The Effects of the Presision of Pointer Analysis, Proceedings of the 4th International Symposium on Static Analysis, p.16-34, September 08-10, 1997
• 17: Michelle Mills Strout , Barbara Kreaseck , Paul D. Hovland, Data-Flow Analysis for MPI Programs, Proceedings of the 2006 International Conference on Parallel Processing, p.175-184, August 14-18, 2006 [doi>10.1109/ICPP.2006.32]
• 18: Michelle Mills Strout , John Mellor-Crummey , Paul Hovland, Representation-independent program analysis, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 19: Jean Utke. OpenAD: Algorithm implementation user guide. Technical Memorandum ANL/MCS-TM-274, Mathematics and Computer Science Division, Argonne National Laboratory, 2004.
• 20: Rob F. van der Wijngaart. NAS parallel benchmarks version 2.4. Technical Report NAS-02-007, NASA Advanced Supercomputing (NAS) Division, October 2002.
• 21: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

Keywords:
activity analysis, automatic differentiation