Differentiation-Enabled Compiler Technology (COMPAD-III)

给出一个Fortran程序，它从输入值的向量x对标量输出y=f(X)进行数值计算，我们经常对计算其分量是导数(灵敏度)dy/dx的梯度向量g=f‘(X)感兴趣。自动微分是一组将计算f的程序自动转换为计算f’的程序的技术。具体地说，即使在x和g中存在数百万个分量，伴随或逆自动微分模式也可以以大约三次f的计算成本产生梯度g的所有分量的数值。这是通过使用微积分中的链式规则(但应用于浮点数值，而不是符号表达式)来实现的，以便对输出相对于所执行的每个浮点计算的灵敏度进行数值评估。然而，这样做需要使程序向后运行，因为这些敏感度必须从dy/dy=1开始计算，以dy/dx=g结束，这与原始计算的顺序相反。它还要求由f计算的中间值要么存储在正向传递中，要么由伴随程序在反向传递中重新计算。CompAD项目的第二阶段已经产生了世界上第一个工业强度的Fortran编译器，能够自动执行这种伴随变换(和反向程序流)。以前的自动区分工具要么使用重载(这很难优化)，要么使用源代码转换(不能直接利用低级编译器工具)。第二阶段生成的伴随Fortran编译器完全适合于中小型问题(最多几百个输入变量)，并满足项目第二阶段的目标。然而，即使是中等规模的问题(数千个输入变量)也需要系统地使用和放置检查点，以便有效地管理前进途中的存储和返回途中的重新计算之间的权衡。使用本原型，用户必须显式放置和管理这些检查点。这对于有很大问题的有经验的用户来说几乎是可以接受的，但对于没有使用自动微分的经验的用户来说，这是有限的和耗时的，并且代表了基于自动微分的数值方法的采用的障碍。CompAD项目第三阶段的目标是以接近最佳的方式自动化存储和重新计算的权衡过程。寻找一个实际上是最优的折衷方案是一个已知的NP-Hard问题，因此我们正在寻找在特定意义上几乎是最优的解决方案。在编译过程中，通过将其自身输出的部分反馈到编译器中，可以自动生成更高阶导数(例如方向Hessian)。我们打算改进编译器中使用的代码转换技术，以达到以这种方式自动生成几乎最优效率的高阶派生代码的程度。本项目的主要目的是探索用于程序分析和代码转换的替代算法和表示，以解决某些困难问题，并为未来与其他方面的进展奠定基础。但我们将使用我们工业合作伙伴的一些尖端数值应用程序来指导和证明我们开发的新技术，该项目的这一阶段产生的Fortran编译器被设计为在科学计算中广泛直接使用。

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.