模式伴随化的基本规则及其代价分析（.docVIP

PAGE 17 模式伴随化的基本规则及其代价分析? ? 本项研究工作得到了国家杰出青年科学基金项目和《国家重点基础研究发展规划项目》（G2839200、G1999032805、G1999032801）和中科院重要创新方向（KZCXZ 2-208）的资助。 2004年03月01日稿。 ?? E-mail: HYPERLINK mailto:walls@ walls@, HYPERLINK /walls /walls, Tel: 010程强1,2 张林波1 王斌2 1中国科学院计算数学与科学工程计算研究所科学与工程计算国家重点实验室（LSEC），100080 2中国科学院大气物理研究所大气科学和地球流体力学国家重点实验室（LASG），100029 摘要 本文从程序语法结构而不是从具体问题本身出发，提出了基于最小程序行为分解的模式伴随化方法。此方法无论在算法设计上还是在软件实现上均更具普遍性，并具有许多独特的优点。它保留了断点存储技术在减少浮点计算量和降低存储开销方面的优点，同时克服了其仅仅适用于计算过程均匀可分假设的局限性。本文首先给出了模式伴随化实现的基本规则，详细介绍了基于最小程序行为分解的模式伴随化方法。然后，基于自动微分（AD）基本假设定义了可分程序空间和微分代价函数，得到了两个反映计算微分代价的基本常数和。在计算过程均匀可分性假设下，讨论了断点存储在浮点计算量和空间存储开销上的最优实现，证明了深度划分在这两个方面同时具有对数复杂性的结论。最后，详细论证了基于最小程序行为分解的模式伴随化方法在浮点计算量和空间存储开销两个方面同时具有过程引用和划分深度依赖性。 关键词 自动微分 模式伴随化 最小程序行为 浮点计算 1 引言 随着观测手段和样本采集技术的飞速发展，反问题（如资料同化和遥感反演等）的研究和应用得到了人们越来越多的关注，并在一些领域（如大气和海洋科学）成为国际热门的前沿课题。最优化方法则是求解大规模反问题的有效途径之一，它依赖函数的一阶或高阶导数，以及多种形式的矩阵向量乘积实现。自动微分方法以合理的计算代价在无截断误差意义上求解函数的数值导数，在科学和工程计算领域逐渐得到人们的普遍重视和广泛应用[1-5] 。正向积分和反向积分是两种基本的计算微分方法，都基于链式求导法则实现。前者从独立变元出发，沿着程序运行的自然顺序自上而下地计算中间变元对独立变元的（方向）导数；相反地，后者从依赖变元出发，沿着与程序运行完全相反的顺序自下而上地计算依赖变元对中间变元的（方向）导数。切线性模式和伴随模式分别为与之相对应的最基本的代码实现形式，它们在精确求解函数梯度和雅可比矩阵方面分别具有不同的计算时间和空间存储代价。伴随模式在求解函数梯度方面具有理想的计算时间代价，但其存储代价往往随问题的计算规模线性增长[6]；因而在模式伴随化实现中，减少计算时间与降低存储开销总是一对矛盾。如今，由于处理器运算速度的增长同处理器与主存之间通信带宽相对缓慢的增长日渐增大的巨大差距，现代计算机多采用多级高速缓存体系结构实现。于是，处理器对数据访存的局部性就成了影响程序计算性能的一个重要特征。在模式伴随化实现中，频繁的重复计算意味着频繁的数据存取和巨大存储开销，而这种代码嵌入式的模式伴随化实现更容易破坏这种数据访存的局部性。一个具体实例是：通过拆分复杂数值表达式来实现微分代码，往往可以成倍降低浮点计算量，但同时也必然引入大量中间存储变元；并且不难证明，在伴随模式中这些中间存储变元的维数至多可以降低一维。其结果是，伴随模式在存储开销上的增加和在浮点计算量上的减小往往并不能获得理想计算性能，即浮点计算量的绝对减少往往并不意味着计算时间的绝对减少，或者计算时间降低的效率可能远远低于浮点计算量减少的速度。相反地，如果适当增加浮点计算量并适当控制模块划分的粒度，提高数据复用频度并减少主存访问次数，将会大大改善计算的整体性能。因此，如何通过适当增加浮点计算，从而降低空间存储开销，并针对特定的机器获得最优的计算性能，一直是自动微分领域研究的热点。 非线性函数的导数总是依赖于自变量的数值，或称为基态值（basic state, B.S.）。在自下而上的模式伴随化过程中，当前位置的基态值信息往往因其下文中被重复计算而发生改变。因此，模式伴随化的根本问题源于同一变量被多次重复计算或重复赋值。数据存储和重复计算是解决这一难题的两种不同方法。数据存储就是在程序对象首次运行过程中，将基态值改变前的所有必要信息用数据缓存或文件存储的方式保存；而在自下而上的模式伴随化过程中，通过逐步访问这些存储单元直接得到当前位置的基态值信息。重复计算则是通过重复上文所有计算过程，从而获得当前位置的基态值信息。显然