权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Differentiation-Enabled Compiler Technology (COMPAD-III)

支持微分的编译器技术 (COMPAD-III)

基本信息

批准号：
EP/F069383/1
负责人：
Bruce Christianson
金额：
$ 30.17万
依托单位：
University of Hertfordshire
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2008
资助国家：
英国
起止时间：
2008 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FF069383%2F1
关键词：
Differentiation Enabled Compiler Technology COMPAD

项目摘要

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.

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