自动微分转换系统及其应用

1、自动微分转换系统及其应用    摘要    自动微分转换系统（DFT）由LASG和LSEC联合研制开发，目前已拥有成熟de版本。本文对DFT系统de功能、特色及其基本应用作了全面de介绍，并给出了一些颇具说服力de数值试验结果。同时，本文提出了统计准确率评价de概念，这对评价一类自动微分工具及其微分模式代码de可靠性与有效性提供了一种客观de尺度。最后，本文还详细讨论了运用切线性模式求解雅可比矩阵de问题，给出了求解初始输入矩阵de有效算法。    关键词 自动微分  切线性

2、模式  数据相关分析  统计准确率    1.引言    计算微分大致经历了从商微分，符号微分，手写代码到自动微分几个阶段。与其它几种微分方法相比，自动微分具有代码简练、计算精度高及投入人力少等优点。自动微分实现de基本出发点是：一个数据相对独立de程序对象（模式、过程、程序段、数值语句乃至数值表达式），无论多么复杂，总可以分解为一系列有限数目的基本函数（如sin、exp、log）和基本运算操作（加、减、乘、除、乘方）de有序复合；对所有这些基本函数及基本运算操作，重复使用链式求导法则，将得到d

3、e中间结果自上而下地做正向积分就可以建立起对应de切线性模式，而自下而上地做反向积分就可以建立起对应de伴随模式1。基于自动微分方法得到de切线性模式和伴随模式，在变分资料同化2、系统建模与参数辨识3、参数de敏感性分析4、非线性最优化以及数值模式de可预测性分析5等问题中有着十分广泛de应用。迄今为止，已有数十所大学和研究所各自开发了能够用于求解切线性模式de自动微分系统，比较典型de有TAMC系统6、ADJIFOR系统7 和ODYSSEE系统8。在一些特定de运用中，它们都是比较成功de，但在通用性和复杂问题de处理效率上还存在许多不足。通常，自动生成切线性模式de关键难题在于对象自身de

4、强相关性，这给系统全局分析（如数据IO相关分析和数据依赖相关分析）和微分代码de整体优化都带来了很多困难。同时，对于程序对象不可导处de准确识别和微分处理，至今仍还没有一个统一而有效de算法。另外，最优或有效求解稀疏雅可比矩阵一直是衡量一个自动微分系统有效性de重要尺度。统计准确率被我们视为评价一类自动微分工具及其微分模式代码可靠性与有效性de重要尺度。其基本假设是：如果对于定义域空间内随机抽样获得de至多有限个n维初始场（或网格点），微分模式输出de差分和微分逼近是成功de；那么对于定义域空间内所有可能初始场（或网格点），微分模式输出de差分和微分逼近都是成功de。微分模式统计准确率评价de

5、具体方法是：在所有随机抽样得到de初始场（或网格点）附近，当输入扰动逐渐趋向于机器有效精度所能表示de最小正值时，模式输出de差分和微分之间应该有足够精度有效位数上de逼近。DFT系统具有许多优点，它能够完全接受用FORTRAN 77语言编写de源代码，微分代码结构清晰，其微分处理能力与问题和对象de规模及复杂性无关。它基于YACC实现，具有很强de可扩展性。DFT系统具有四个重要特色。它通过对象全局依赖相关分析，准确求解雅可比矩阵de稀疏结构，自动计算有效初始输入矩阵，从而可以用较小de代价求得整个雅可比矩阵。同时，它可以自动生成客观评价微分模式效率与可靠性de测试程序，对奇异函数做等价微分

6、处理，并采用二元归约de方法，在语句级层次上实现微分代码优化。    2.系统概况  DFT系统主要由两部分组成：微分代码转换和微分代码评价，图2.1。微分代码转换部分接受用户输入指令并自动分析对象模式，生成切线性模式代码及其相关测试代码，后者直接构成微分代码评价系统de主体。微分代码评价是DFT系统de一个重要特色。DFT系统de开发小组认为，一个微分模式如果在可靠性、时间和存储效率上没有得到充分de验证，至少对实际应用而言，它将是毫无意义de。        &

7、#160;                         原模式                        

8、60;                                                 

9、60; 切线性模式                                                 &#

10、160;                                                 &#

11、160;                                                 &#

12、160;    统计评价结果     图2.1  DFT系统结构简图    2.1 微分代码转换    DFT系统是基于YACC在UNIX环境下开发de，其结构图2.2所示。通过DFT系统产生de切线性模式代码成对出现，并在语句级程度上做了简化，可读性很强，如图2.4。              &

13、#160;                                                   

14、;                                                  

15、;                                                  

16、0;                                                 

17、0;                          切线性模式                       

18、0;                                                 

19、0;                                              评价函数集   

20、0;图2.2   微分代码转换         微分代码转换部分从功能上分为四个部分：词法分析，语义分析，对象复杂性及数据相关分析和微分代码转换。对于一组具有复杂数据相关de程序模式对象，通常需要系统运行两遍才能得到有效而可靠de微分代码。这主要有两方面de考虑：其一，根据对象de复杂性（如最大语句长度、最大变量维数、子过程或函数数目、子过程或函数内最大变量数目等对象特征）选择合适de系统参数以求最优de运行代价；其二，模式内各子过程或函数之间以及一个子过程或函数内往往具有很强de数据相关性，需

21、要事先保存对象de相关信息并且在考虑当前对象de属性之前必须做上下文相关分析。                                           

22、60;                         图2.3   PERIGEE源程序代码                    

23、60;     图2.4  DFT系统生成de切线性代码    2.2 微分代码评价    通常，评价一个编译系统de性能有很多方面，如处理速度、结果代码可靠性及质量、出错诊断、可扩展和可维护性等。对于一类自动微分系统来说，由于软件开发人力de局限以及对象模式de复杂多样性,通过自动转换得到de微分模式并非常常是有效而可靠de（即无论是在数学意义上还是在程序逻辑上应与期待de理想结果一致），因而在微分模式被投入实际应用前，往往需要投入一定de人力来对其做严格de分析

24、测试。  对切线性模式做统计评价测试de主要内容可以简单叙述为：在网格化de模式定义域空间内，选择所有可能de网格点形成微分模式计算de初始场；在不同de网格点附近，随机选取至少 个线性无关de初始扰动，对每个扰动输入分别进行网格点逼近，统计考察模式输出差分和微分在有效位数上de逼近程度。图2.5描述了整个测试过程，它包含网格点数据随机采样（1）和网格点数据逼近（2）两级循环。                 

25、60;           图2.5   切线性模式代码de测试过程    3.系统主要特色    DFT系统并不是一个完整deFORTRAN编译器，但它几乎可以接受和处理所有FORTRAN 77编写de源模式代码，并且可以很方便地扩展并接受FORTRAN 90编写de源模式代码。本节将着重介绍DFT系统（版本3.0）de以下几个重要特色。    

26、3.1 结构化de微分实现    DFT系统采用标准化de代码实现，切线性模式de扰动变量和基态值变量、微分计算语句和基态值计算语句总是成对出现，并具有清晰de程序结构。微分代码保持了原模式本身de结构和风格（如并行和向量特性、数据精度等），即语句到语句、结构到结构de微分实现。在奇异点或不可导处，DFT系统对微分扰动采取简单de清零处理，实践证明这对抑制扰动计算溢出具有重要意义，但并不影响评价测试结果。    3.2 全局数据相关分析      

27、0;     DFT系统具有较强de数据相关分析能力，它包括全局数据IO相关分析、全局数据依赖相关分析、全局过程相关分析以及数据迭代相关分析几个不同方面。数据依赖相关与数据IO相关关系密切，但又存在根本不同。前者强调每个变量在数学关系上de依赖性；而后者描述了一个对象de输入输出特性，且具有相对性，即任何一个变量参数，无论它是独立变量还是依赖变量，在数学意义上都可等价为一个既是输入又是输出de参数来处理。        DFT系统记录所有过程参数deIO属性表，通过深度递归相关计算，准

28、确计算每个过程参数de最终IO属性。DFT系统通过对数据相关矩阵做模二和及自乘迭代计算（An+1= AnAn2）来完成数据de依赖相关分析，这种算法具有很好de对数收敛特性。DFT系统通过全局过程相关分析de结果，自动生成模式de局部或整体相关引用树结构（如图3.1），这对用户分析复杂数值模式和微分评价测试都具有很好de指导作用。DFT系统还具有分析局部数据迭代相关和函数迭代相关de能力，这两种形式de数据迭代相关是自动微分实现颇具挑战de难题之一。            &

29、#160;                               图3.1  GPS Rayshooting模式de相关树结构片段    3.3 自动生成测试程序      

30、      基于IO相关分析de结果，DFT系统自动生成微分测试代码，分别对切线性模式de可靠性和运行代价做统计评价测试。特别地，DFT系统还可将任何模式参数都视为输入输出参数，生成在数学意义上等价de测试代码，这样处理de不利之处在于往往需要极高de存储开销。    3.4 基于语句级de代码优化           目前，DFT系统仅仅具备局地优化能力。在语句级微分实现上采用二元归约de方法对微分代码进行优化是DFT系统de一个重要特色。根据右端表达式de乘法复杂性及含变元数目的不同，DFT系统采取不同de分解策略。二元归约de方法避免了微分计算中de许多冗余计算，在一些复杂de非线性表达式de微分计算中具有最小de计算代价，同时也非常适合于微分系统de软件实现。同时，对于某些特殊de运算操作（除法、乘方）和特殊函数（如sqrt、exp），DFT系统较好地利用了基态值计算得到de中间结果，避免了微分实现中de冗余计算。