# Differentiation-Enabled Compiler Technology (COMPAD-III)

Lead Research Organisation:
University of Hertfordshire

Department Name: Science and Technology RI

### Abstract

Given a Fortran program which evaluates numerically a scalar output y = f(x) from a vector x of input values, we are frequently interested in evaluating the gradient vector g = f '(x) whose components are the derivatives (sensitivities) dy/dx.Automatic Differentiation is a set of techniques for automatically transforming the program for evaluating f into a program for evaluating f '. In particular the adjoint, or reverse, mode of Automatic Differentiation can produce numerical values for all components of the gradient g at a computational cost of about three evaluations of f, even if there are millions of components in x and g. This is done by using the chain rule from calculus (but applied to floating point numerical values, rather than to symbolic expressions) so as to evaluate numerically the sensitivity of the output with respect to each floating point calculation performed. However, doing this requires making the program to run backwards, since these sensitivities must be evaluated starting with dy/dy = 1 and ending with dy/dx = g, which is the reverse order to the original calculation. It also requires the intermediate values calculated by f to be either stored on the forward pass, or recomputed on the reverse pass by the adjoint program. Phase II of the CompAD project has already produced the first industrial strength Fortran compiler in the world able to perform this adjoint transformation (and reverse program flow) automatically. Previous Automatic Differentiation tools used either overloading (which was hard to optimize) or source transformation (which could not directly utilize low level compiler facilities).The adjoint Fortran compiler produced by phase II is perfectly adequate for small to medium sized problems (up to a few hundred input variables), and meets the objectives of the second phase of the project. However even moderately large problems (many thousands of input variables) require the systematic use and placement of checkpoints, in order to manage efficiently the tradeoff between storage on the way forward and recomputation on the way back. With the present prototype, the user must place and manage these checkpoints explicitly. This is almost acceptable for experienced users with very large problems which they already understand well, but it is limiting and timeconsuming for users without previous experience of using Automatic Differentiation, and represents a barrier to the uptake of numerical methods based upon Automatic Differentiation. The objective of Phase III of the CompAD project is to automate the process of trading off storage and recomputation in a way which is close to optimal. Finding a tradeoff which is actually optimal is known to be an NP-hard problem, so we are seeking solutions which are almost optimal in a particular sense. Higher order derivatives (eg directional Hessians) can be generated automatically by feeding back into the compiler parts of its own output during the compilation process. We intend to improve the code transformation techniques used in the compiler to the point where almost optimally efficient higher order derivative code can be generated automatically in this way.A primary purpose of this project is to explore alternative algorithms and representations for program analysis and code transformation in order to solve certain hard problems and lay the groundwork for future progress with others. But we will be using some hard leading edge numerical applications from our industrial partners to guide and prove the new technology we develop, and the Fortran Compiler resulting from this phase of the project is designed to be of widespread direct use in Scientific Computing.

## People |
## ORCID iD |

Bruce Christianson (Principal Investigator) |

### Publications

Christianson, B
(2009)

*Global convergence using de-linked Goldstein or Wolfe linesearch conditions*in Advanced Modelling and Optimization
Mosenkis V
(2012)

*On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs*in Optimization Methods and Software
Naumann U
(2012)

*Combinatorial Scientific Computing*
Naumann U
(2015)

*Algorithmic Differentiation of Numerical Methods Tangent and Adjoint Solvers for Parameterized Systems of Nonlinear Equations*in ACM Transactions on Mathematical Software
Naumann U
(2009)

*DAG reversal is NP-complete*in Journal of Discrete Algorithms
Naumann U
(2008)

*Advances in Automatic Differentiation*
R Kopmann (Co-Author)
(2012)

*Using Reliability Analysis in Morphodynamic Simulation with TELEMAC-2D / SISYPHE*
Rauser F
(2010)

*On the use of discrete adjoints in goal error estimation for shallow water equations*in Procedia Computer ScienceDescription | The previous phase (Phase II) of the CompAD project produced the first industrial strength Fortran compiler in the world able to perform the adjoint transformation (and reverse program flow) automatically. Previous Automatic Differentiation tools used either overloading (which was hard to optimize) or source transformation (which could not directly utilize low level compiler facilities). Phase III of the CompAD project has improved the adjoint transformation process by using parallel processing to trade-off storage and re-computation in a way that is close to optimal. (Finding a tradeoff which is actually optimal is known to be an NP-hard problem, so we provide solutions which are "almost optimal" in a particular sense.) For example, on a typical problem (shallow-water flow) we were able during Phase III to reduce the run-time for computing the entire long gradient vector g from 120 times that required just to compute the original function f, to a ratio of less than nine. Phase III has also enabled higher-order derivatives such as directional Hessians to be generated automatically. This was done by developing tools that allow feeding back into the compiler parts of its own output, during the compilation process. In this phase of the research we enhanced the code transformation techniques used in the compiler to the point where "almost optimally" efficient higher order derivative code is generated automatically in this way. The resulting "reduced entry cost" for exploiting benefits of Automatic Differentiation makes it more likely that users without previous experience of Automatic Differentiation will be willing to adopt numerical methods that are based upon it to address their modeling and optimization problems. |

Exploitation Route | A primary purpose of Phase III of the project was to explore alternative algorithms and representations for program analysis and code transformation. But we used some hard leading-edge numerical applications from our industrial partners to guide and prove the new technology we developed, and so the Fortran Compiler resulting from this phase of the project is designed to be of widespread direct use in Scientific Computing. |

Sectors | Digital/Communication/Information Technologies (including Software) |

Description | A compiler developed in the course of a ten-year research programme at the University has been successfully applied to a number of commercial problems by re-purposing the research tool. NAG Ltd has adapted the tool into a commercial product now used operationally by investment banks. Numerous applications of the mathematical methods (such as type-flow graphs used conjointly for correctness and optimization) have been deployed by industry. |

First Year Of Impact | 2009 |

Sector | Aerospace, Defence and Marine,Energy,Financial Services, and Management Consultancy,Manufacturing, including Industrial Biotechology,Transport |

Impact Types | Economic |

Description | Bundesanstalt fur Wasserbau |

Amount | £150,000 (GBP) |

Organisation | Federal Waterways (Bundesanstalt fur Wasserbau) |

Sector | Public |

Country | Germany |

Start |

Description | Bundesanstalt fur Wasserbau |

Amount | £150,000 (GBP) |

Organisation | Federal Waterways (Bundesanstalt fur Wasserbau) |

Sector | Public |

Country | Germany |

Start |

Description | Numerical Algorithms Group Ltd |

Organisation | Numerical Algorithms Group Ltd |

Country | United Kingdom |

Sector | Private |

Start Year | 2006 |

Description | RWTH Aachen University |

Organisation | RWTH Aachen University |

Country | Germany |

Sector | Academic/University |

Start Year | 2006 |