Differentiation-Enabled Compiler Technology (COMPAD-III)

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