Static Analysis for Automatic Differentiation
Scientific computing is an important branch of computer science with applications in many different industries including aerospace, defense, automotive, financial, environmental and energy. Scientific computing algorithms such as optimization, nonlinear equation solving, and modeling require the use of derivative functions. There are many options for computing these derivatives. They can be created manually, but this is highly tedious and error prone. They can be created symbolically using a mathematics package such as Maple or Matlab, but this is not directly applicable to computer programs written in a language such as C, and either fails or becomes computationally infeasible for large programs. They can be approximated using finite differencing, but this can be inaccurate and slow.
Automatic differentiation (AD) (also known as computational differentiation or algorithmic differentiation) has emerged as an alternative technique for computing derivatives. Given a program that computes a numerical function F(x), an automatic differentiation tool creates a related program that computes F'(x) (the derivative of F). Automatic differentiation works by systematically applying the chain rule of differential calculus at the level of the built-in operators and libraries of the language. Because of this, it is not subject to the same numerical errors as finite differencing.
Recently, automatic differentiation has seen a surge of interest, corresponding to the appearance of automated techniques for applying it. Its advantages are clear and proven. However, it is still used in only a handful of research laboratories. The low level of uptake can be attributed to the fact that the tools are still in their infancy, and still suffer from scalability, usability, and performance problems.
Automatic differentiation can be implemented either as a source-to-source translation, or by means of overloaded operators and reinterpreted operands. The advantage of using overloaded operators is that it is easy to implement and the source code does not need to change much. However, it has the disadvantage that it is inefficient. There are two main sources of inefficiency in the overloaded-operator approach. First, the approach is context-insensitive —it cannot exploit local context-sensitive information to improve efficiency. Second, the technique must be applied globally to all statements, regardless of whether they contribute to the computation of the derivative or not.
The great advantage of source-to-source translation is that analysis of the source code can be used to greatly improve the efficiency of the derivative. The chief disadvantage is that static source-code analysis tools and source-to-source transformation tools are generally large, complicated, and difficult to implement.
GrammaTech is a leading provider of static analysis tools for computer programs. Our technology computes the dependence-graph representation of a program, in which program points such as statements, functions, parameters, etc., are joined by an edge if there is a data or a control dependence between them. Queries are provided for inspecting the graph—for example, a slice takes as input a set of program points and returns all program points that contribute to the values computed at those input points. The query algorithms are not simple straightforward graph reachability—they must only return results that correspond to feasible executions of the program.
Many of the questions that must be answered in order to do efficient AD can be cast in terms of queries on the dependence graph. For example, identifying the set of variables that contribute to the derivative can be done by doing point-to-point graph reachability between the independent variables and the dependent variables.
We propose to develop a system for automatic differentiation using source-to-source transformation methods. The system will make use of our advanced static analysis capabilities to generate efficient derivatives.