LANS Publications

"Comparison of Two Activity Analyses for Automatic Differentiation: Context-Sensitive Flow-Insensitive vs. Context-Insensitive Flow-Sensitive"

J. Shin and P. D. Hovland

Preprint ANL/MCS-P1369-0906

Preprint Version: [pdf]

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.