# Presentation: 448913

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

***The 22nd Annual ACM Symposium on Applied Computing******Seoul, Korea, March 12, 2007***

## Outline

- Automatic Differentiation
- Activity Analysis
- Existing Algorithm: ICFGAA
- Our Algorithm: VDGAA
- Experimental Results
- Conclusion

## Automatic Differentiation (AD)

- y = f(x)

- dy/dx = f’(x)

- y = sin(x)

- y.v = sin(x.v)
- y.d = x.d*cos(x.v)

- AD

## Automatic Differentiation (AD)

- Analytic differentiation of elementary functions

**t****1**** = sin(x)**
**t****2**** = exp(t****1****)**
**y = 2*t****2**

**dy/dx = (dt****1****/dx)(dt****2****/dt****1****)(dy/dt****2****)**

**dt****1****/dx = cos(x)**
**dt****2****/dt****1**** = exp(t****1****)**
**dy/dt****2**** = 2**

- Combine the partial derivatives according to the **chain rule**

## AD in a Nutshell

- Automatically generates the derivatives of mathematical functions written in programming languages
- No round-off errors unlike numerical differentiation
- Used in optimization, nonlinear PDEs, sensitivity analysis, inverse problems, ...

- Source-to-source translation
- Semantic transformation

***Compiler’s perspective ...***

## Activity Analysis: Given f, compute dy1/dx1

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1)**
**  ****y1 = t1*2**
**  ****t2 = cos(x2)**
**  ****y2 = t2*3**
**  ****y3 = x3*t1**
**}**

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1)**
**  ****dt1/dx1 = cos(x1)**
**  ****y1 = t1*2**
**  ****dy1/dt1 = 2**
**  ****t2 = cos(x2)**
**  ****y2 = t2*3**
**  ****y3 = x3*t1**
**  ****dy1/dx1 = (dy1/dt1)*(dt1/dx1)**
**}**

## Activity Analysis: Given f, compute dy1/dx1

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1)**
**  ****y1 = t1*2**
**  ****t2 = cos(x2)**
**  ****y2 = t2*3**
**  ****y3 = x3*t1**
**}**

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1)**
**  ****dt1/dx1 = cos(x1)**
**  ****y1 = t1*2**
**  ****dy1/dt1 = 2**
**  ****t2 = cos(x2)**
**  ****dt2/dx2 = -sin(x2)**
**  ****y2 = t2*3**
**  ****dy2/dt2 = 3**
**  ****y3 = x3*t1**
**  ****dy3/dx3 = t1**
**  ****dy3/dt1 = x3**
**  ****dy1/dx1 = (dy1/dt1)*(dt1/dx1)**
**  ****dy2/dx2 = (dt2/dx2)*(dy2/dt2)**
**  ****dy3/dx1 = (dt1/dx1)*(dy3/dt1)**
**}**

## Activity Analysis: varied + useful = active

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1);**
**  ****y1 = t1*2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3 = x3*t1;**
**}**

**f(****x1****, x2, x3, y1, y2, y3){**
**  ****t1 ****= sin(****x1****);**
**  ****y1 ****= ****t1*****2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3 ****= x3*****t1****;**
**}**

**f(x1, x2, x3, ****y1****, y2, y3){**
**  ****t1 ****= sin(****x1****);**
**  ****y1 ****= ****t1*****2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3 = x3*t1;**
**}**

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 ****=**** ****sin(****x1****);**
**  ****y1 ****= ****t1*****2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3 = x3*t1;**
**}**

*varied*

*varied*

*useful*

*useful*

*active*

## Context-Insensitive, Flow-Sensitive Activity Analysis (ICFGAA)

- Interprocedural Control Flow Graph (ICFG)
- Iterative data-flow analysis (DFA)
- Two separate DFAs:
- Forward for “varied” variables
- Backward for “useful” variables
- Long run time
- Large number of iterations
- Nonseparability of activity analysis: data-flow analysis values depend on other data-flow values
- Large overestimation
- Due to context-insensitivity
- Value propagation through unrealizable control paths

## Context-Sensitive, Flow-Insensitive Activity Analysis (VDGAA)

- Variable Dependence Graph (VDG)
- Graph reachability problem
- Two separate propagations:
- Forward for “varied” variables
- Backward for “useful” variables
- Context sensitivity is supported by a stack of contexts.
- Run time
- Nearly-linear to the program size
- Small overestimations
- Due to the way programs are usually written
- Due to the property of activity analysis

## VDGAA on the run: 1. build VDGAA

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1);**
**  ****y1 = t1*2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3 = x3*t1;**
**}**

- x1

- x2

- x3

- t2

- y1

- y2

- y3

- t1

*Variable Dependence Graph (VDG)*

## VDGAA on the run: 2. Find ‘varied’ variables

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1**** = sin(****x1****);**
**  ****y1**** = ****t1*****2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3**** = x3*****t1****;**
**}**

- x1

- x2

- x3

- t2

- y1

- y2

- y3

- t1

*Forward propagation*

## VDGAA on the run: 3. Find ‘useful’ variables

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1**** = sin(****x1****);**
**  ****y1**** = ****t1*****2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3**** = x3*****t1****;**
**}**

- x1

- x2

- x3

- t2

- y1

- y2

- y3

- t1

*Backward propagation*

## Speedups in analysis run time: VDGAA over ICFGAA

## Reduction in active variables

## Where are the improvements coming from ?

- Speedup of analysis comes from the different problem formulation.
- Graph reachability vs. iterative data flow analysis
- Better output quality comes from
- CSFI over CIFS
- Properties of activity analysis
*As long as there exists at least one control path where a variable is active, the variable should be active.*
- The way programs are usually written.
*Variables are defined before being used.*
*Variables are rarely reused.*

## Conclusion

- New CSFI activity analysis algorithm
- Comparison of two activity analyses: CSFI vs. CIFS
- Speedup of the analysis: 2 to 583X over CIFS activity analysis
- Reduction in overestimations: 0.83 to 18.5X
- See the paper for supporting context sensitivity and the issues with global variables.
- Future work
- Improving ICFGAA
- Comparison with CSFS analysis
- Similar improvements to other analyses ?

## Activity Analysis

- Derivatives wrt a small subset of input variables
- Derivatives for a subset of output variables
- Need to compute derivatives only for the intermediate variables
- that are (transitively) dependent on any input variable of interest (called “varied”) AND
- on which any output variable of interest is (transitively) dependent (called “useful”).
- Such intermediate variables are said to be “active”.
- Nonseparable

## OpenAD: With activity information

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1);**
**  ****y1 = t1*2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3 = x3*t1;**
**}**

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****T1.v = SIN(X1.v) **
**  ****dT1/dX1 = COS(X1.v)**** **
**  ****Y1.v = T1.v*2 **
**  ****dY1/dT1 = 2 **
**  ****T2 = COS(X2) **
**  ****Y2 = T2*3 **
**  ****Y3 = X3*T1.v **
**  ****dY1/dX1 = (dT1/dX1)*(dY1/dT1) **
**  ****Y1.d = X1.d*(dY1/dX1)**
**}**

## OpenAD: Without activity information

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****t1 = sin(x1);**
**  ****y1 = t1*2;**
**  ****t2 = cos(x2);**
**  ****y2 = t2*3;**
**  ****y3 = x3*t1;**
**}**

**f(****x1****, x2, x3, ****y1****, y2, y3){**
**  ****T1.v = SIN(X1.v)**
**  ****dT1/dX1 = COS(X1.v)**
**  ****Y1.v = T1.v*2**
**  ****dY1/dT1 = 2**
**  ****T2.v = COS(X2.v)**
**  ****dT2/dX2 = -SIN(X2.v)**
**  ****Y2.v = T2.v*3**
**  ****dY2/dT2 = 3**
**  ****Y3.v = X3.v*T1.v**
**  ****dY3/dX3 = T1.v**
**  ****dY3/dT1 = X3.v**
**  ****dY1/dX1 = (dT1/dX1)*(dY1/dT1)**
**  ****dY3/dX1 = (dT1/dX1)*(dY3/dT1)**
**  ****dY2/dX2 = (dT2/dX2)*(dY2/dT2)**
**  ****Y1.d = X1.d*(dY1/dX1)**
**  ****Y3.d = X1.d*(dY3/dX1)**
**  ****Y2.d = X2.d*(dY2/dX2)**
**  ****Y3.d = Y3.d + X3.d*(dY3/dX3)**
**}**