自动微分软件中的IO相关性分析技术
|
摘要
自动微分方法基于链式求导法则,通过各种预编译手段,把一个数值程序代码转换成对应的计算导数的程序代码。在计算函数梯度、海森矩阵时,自动微分方法和有限差分相比在计算时间代价方面具有巨大的优势,且无截断误差。例如,运用伴随模式来计算函数梯度的浮点计算代价仅有原程序的几倍,与独立变量的数目无关。目前,大量的微分模式都可以方便地通过自动微分工具来得到,例如DFT/ADG系统。
目前,除了生成正向模式的微分工具比较成熟之外,几乎所有生成反向模式(特别是伴随模式)的微分工具在准确性和性能方面还有很长一段路要走。因此,微分代码评价具有很重要的作用。它通过统计评价的手段对所生成的微分模式在可靠性、计算时间和空间开销等方面进行评价。而变量的IO属性信息则是生成可靠微分测试代码的必要条件。DFT/ADG系统之前的相关性分析模块并不可靠,在实际的开发中常常需要大量的人工介入。本文旨在根据现有系统的基础,分析软件的需求。为DFT/ADG系统建立可靠的IO相关性分析模块,为微分测试代码的生成提供准确的信息。主要工作包括:
1、总结DFT/ADG系统的现有功能,指出现有微分代码评价体系的缺点,并由此指出IO相关性分析模块的重要性;
2、通过对现有软件运行机制的分析,构造并完善IO相关性分析模块;
3、对新模块进行算法研究以及整体流程设计,同时给出我们在实际应用中所遇到的边界条件,并总结现有接口的不足;
4、对XIAMEN程序进行优化,通过对优化算法和程序对象的分析,指出优化策略;具体给出优化过程中所遇到的一些难点,尝试提出通用且可行的解决方案;
5、给出XIAMEN程序优化的数值测试结果以及IO相关性分析模块的测试结果,分别验证伴随模式在求解梯度时的性能优势以及新的静态IO相关性分析模块的正确性。
Automatic Differentiation (AD) is a set of techniques based on the mechanical application of the chain rule to obtain derivatives of a function given as a computer program. Compared to finite differencing method, AD can calculate gradients and Hessian matrix in a much faster way without truncation error. For example, the adjoint model can calculate gradients with the time cost only several times of the underlying function and independent of the number of the independent variables. In recent years, Automatic differentiation tools, including the DFT/ADG software, are widely used to obtain differentiation models.
Currently, the forward model generators show a lot of maturity in validation an efficiency, while almost all of the reverse model generators (espically the adjoint model generators) still have a long way to go. That’s why the code evaluation system, which can evaluate the two models in time cost, memory cost and reliability by statistics method, plays a key role in AD software. As the upper and input layer of the code evaluation system, the static IO analysis is also an undisplacable part. In the past, the instability of the IO analysis in DFT/ADG software resulted in a lot of hand-on work. In this paper, we mean to analyze the need on the basic of the current system, and rebuild a stable IO analysis module of the DFT/ADG software, which can offer a more precise IO result to the generation of the testing code. The work include the following parts:
1. Summarize the functionality of the current version of DFT/ADG, find the defect of the code evaluation system, and tell the importance of the IO analysis;
2. Find a right position of the new module by analyzing how the system runs;
3. Overall data flow design and detailed algorithm design. And I am going to present some boundary conditions which are brought up mainly by the defect of the interface.
4. Do optimization for XIAMEN software. Make optimization plan by analyzing the underlying function. Finally, point out the difficulties in the application, and try to give out general methods in solving the problems.
5. Finally, a lot of tests have been done to prove the efficiency of DFT/ADG software, the validation of the IO analysis, and the performance by using AD.
目前,除了生成正向模式的微分工具比较成熟之外,几乎所有生成反向模式(特别是伴随模式)的微分工具在准确性和性能方面还有很长一段路要走。因此,微分代码评价具有很重要的作用。它通过统计评价的手段对所生成的微分模式在可靠性、计算时间和空间开销等方面进行评价。而变量的IO属性信息则是生成可靠微分测试代码的必要条件。DFT/ADG系统之前的相关性分析模块并不可靠,在实际的开发中常常需要大量的人工介入。本文旨在根据现有系统的基础,分析软件的需求。为DFT/ADG系统建立可靠的IO相关性分析模块,为微分测试代码的生成提供准确的信息。主要工作包括:
1、总结DFT/ADG系统的现有功能,指出现有微分代码评价体系的缺点,并由此指出IO相关性分析模块的重要性;
2、通过对现有软件运行机制的分析,构造并完善IO相关性分析模块;
3、对新模块进行算法研究以及整体流程设计,同时给出我们在实际应用中所遇到的边界条件,并总结现有接口的不足;
4、对XIAMEN程序进行优化,通过对优化算法和程序对象的分析,指出优化策略;具体给出优化过程中所遇到的一些难点,尝试提出通用且可行的解决方案;
5、给出XIAMEN程序优化的数值测试结果以及IO相关性分析模块的测试结果,分别验证伴随模式在求解梯度时的性能优势以及新的静态IO相关性分析模块的正确性。
Automatic Differentiation (AD) is a set of techniques based on the mechanical application of the chain rule to obtain derivatives of a function given as a computer program. Compared to finite differencing method, AD can calculate gradients and Hessian matrix in a much faster way without truncation error. For example, the adjoint model can calculate gradients with the time cost only several times of the underlying function and independent of the number of the independent variables. In recent years, Automatic differentiation tools, including the DFT/ADG software, are widely used to obtain differentiation models.
Currently, the forward model generators show a lot of maturity in validation an efficiency, while almost all of the reverse model generators (espically the adjoint model generators) still have a long way to go. That’s why the code evaluation system, which can evaluate the two models in time cost, memory cost and reliability by statistics method, plays a key role in AD software. As the upper and input layer of the code evaluation system, the static IO analysis is also an undisplacable part. In the past, the instability of the IO analysis in DFT/ADG software resulted in a lot of hand-on work. In this paper, we mean to analyze the need on the basic of the current system, and rebuild a stable IO analysis module of the DFT/ADG software, which can offer a more precise IO result to the generation of the testing code. The work include the following parts:
1. Summarize the functionality of the current version of DFT/ADG, find the defect of the code evaluation system, and tell the importance of the IO analysis;
2. Find a right position of the new module by analyzing how the system runs;
3. Overall data flow design and detailed algorithm design. And I am going to present some boundary conditions which are brought up mainly by the defect of the interface.
4. Do optimization for XIAMEN software. Make optimization plan by analyzing the underlying function. Finally, point out the difficulties in the application, and try to give out general methods in solving the problems.
5. Finally, a lot of tests have been done to prove the efficiency of DFT/ADG software, the validation of the IO analysis, and the performance by using AD.
引文
1 M. Berz,C. H. Bischof,G. F. Corliss and A. Griewank,editors,Computational Differentiation: Techniques, Applications and Tools,SIAM,Philadelphia,PA,1996
2 G. F. Corliss,C. Faure,A. Griewank,L.Hasco?t and U. Naumann,editors,Automatic Differentiation of Algorithms: From Simulation to Optimization,Computer and Information Science,Springer,NewYork,NY,2002
3 A. Griewank and G. F. Corliss,Editors,Automatic Differentiation of Algorithms: Theory,Implementation and Application,SIAM,Philadelphia,PA,1991
4 Andreas Griewank,Some Bounds on the Complexity of Gradients, Jacobians, and Hessians Technical Report MCS-P355-0393
5 A. Griewank,Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation,Optimization Methods and Software 1(1992),pp33-54
6 A. Griewank,A mathematical view of automatic differentiation,In Acta Numerica,Vol. 12,pp321-398,Cambridge University Press,2003
7 A. Griewank and C. Mitev,Detecting Jacobian sparsity patterns by Bayesian probing,Mathematical Programming,Ser. A,93(1),pp1-25,2002
8 A.Griewank and A.Walther,On constrained optimization by adjoint based quasi-Newton methods,Optimization Methods and Software 17(2002),pp869-88
9 Ralf Giering and Thomas Kaminski,Recipes for Adjoint Code Construction,ACM transaction on Mathematical Software,Volume 24.4(1998),pp437-474
10 Christian Bischof and Lucas Roh, ADIC: An Extensible Automatic Differentiation Tool for ANSI-C, Mathematics and Computer Science Division, Argonne Preprint ANL / MCS - P626 - 1196 (revised May 1997)
11 Nicole Rostating, Stephane Dalmas and Andre Galligo. Automatic Differentiation in Odyssee. Tellus, 1993, 45(A):558-568
12 R.E.Wengert. A simple automatic derivative evaluation program.Comm.ACM, 7(8):463-464,1964
13 Andreas Griewank. On Automatic Differentiation, Mathematical Programming:Recent Developments and Applications (Amsterdam). M. Iri and K. Tanabe, eds., Kluwer Academic Publishers. 1989, pp.83-108
14 Le Dimet, F. X and O. Talagrand. Variational algorithms for analysis and assimilation of meteor-ological observations: theoretical aspects. Tellus, 38(A): 97-110, 1986
15 D.G. Cacui. Sensitivity theory for nonlinear systems, II: Extension to additional classes of responses. Journal of Mathematical Physics, 22(12): 2803-2812, 1981
16 Christian Bischof, Gordon Pusch and Ralf Knoesel. Sensitivity Analysis of the MM5 Weather Model using Automatic Differentiation. Computers in Physics, 0: 605-612, 1996
17 Cheng Qiang, Zhang Linbo and Wang Bin,Model Adjointisation and Its Costs, Science in China(F), Vol. 47, No. 5, 587-611, 2004
18 Cheng Qiang, Wang Bin and Zhang Linbo, Differentiation Transforming System (DFT), Users’ Manual, LASG, Institute of Atmospheric Physics (IAP), 2006
19 Cheng Qiang, Wang Bin, Adjoint Code Generator (ADG), Users’ Manual, LASG, Institute of Atmospheric Physics (IAP), 2006
20 Wu W., Song L., Mo Y., et al., Xiamen―An ab initio spin-free valence bond (VB) program, Xiamen, Xiamen University, 1998
21 J.Verbeer, J.H.Langenberg, C.P.Byrman,F. Dijkstra and J.H.van Lenthe, TURTLE an Ab Initio VB/VBSCF program, Utrecht, 1998-1999.
22 Haruyuki Nakano, Cooper D.L. et al, J.Mole.Stru(Theochem), 1999, 461, 55
23 M.J.D. Powell, J. Inst. Math. Appl., 1971, 7, 21
24 S. Shaik and A. Shurki, Angew., Chem. Int. Ed., 1999, 38: 586-625.
25 Mu Mu. Nonlinear singular vectors and nonlinear singular values. Science in China (D), 43: 375-385, 2000
2 G. F. Corliss,C. Faure,A. Griewank,L.Hasco?t and U. Naumann,editors,Automatic Differentiation of Algorithms: From Simulation to Optimization,Computer and Information Science,Springer,NewYork,NY,2002
3 A. Griewank and G. F. Corliss,Editors,Automatic Differentiation of Algorithms: Theory,Implementation and Application,SIAM,Philadelphia,PA,1991
4 Andreas Griewank,Some Bounds on the Complexity of Gradients, Jacobians, and Hessians Technical Report MCS-P355-0393
5 A. Griewank,Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation,Optimization Methods and Software 1(1992),pp33-54
6 A. Griewank,A mathematical view of automatic differentiation,In Acta Numerica,Vol. 12,pp321-398,Cambridge University Press,2003
7 A. Griewank and C. Mitev,Detecting Jacobian sparsity patterns by Bayesian probing,Mathematical Programming,Ser. A,93(1),pp1-25,2002
8 A.Griewank and A.Walther,On constrained optimization by adjoint based quasi-Newton methods,Optimization Methods and Software 17(2002),pp869-88
9 Ralf Giering and Thomas Kaminski,Recipes for Adjoint Code Construction,ACM transaction on Mathematical Software,Volume 24.4(1998),pp437-474
10 Christian Bischof and Lucas Roh, ADIC: An Extensible Automatic Differentiation Tool for ANSI-C, Mathematics and Computer Science Division, Argonne Preprint ANL / MCS - P626 - 1196 (revised May 1997)
11 Nicole Rostating, Stephane Dalmas and Andre Galligo. Automatic Differentiation in Odyssee. Tellus, 1993, 45(A):558-568
12 R.E.Wengert. A simple automatic derivative evaluation program.Comm.ACM, 7(8):463-464,1964
13 Andreas Griewank. On Automatic Differentiation, Mathematical Programming:Recent Developments and Applications (Amsterdam). M. Iri and K. Tanabe, eds., Kluwer Academic Publishers. 1989, pp.83-108
14 Le Dimet, F. X and O. Talagrand. Variational algorithms for analysis and assimilation of meteor-ological observations: theoretical aspects. Tellus, 38(A): 97-110, 1986
15 D.G. Cacui. Sensitivity theory for nonlinear systems, II: Extension to additional classes of responses. Journal of Mathematical Physics, 22(12): 2803-2812, 1981
16 Christian Bischof, Gordon Pusch and Ralf Knoesel. Sensitivity Analysis of the MM5 Weather Model using Automatic Differentiation. Computers in Physics, 0: 605-612, 1996
17 Cheng Qiang, Zhang Linbo and Wang Bin,Model Adjointisation and Its Costs, Science in China(F), Vol. 47, No. 5, 587-611, 2004
18 Cheng Qiang, Wang Bin and Zhang Linbo, Differentiation Transforming System (DFT), Users’ Manual, LASG, Institute of Atmospheric Physics (IAP), 2006
19 Cheng Qiang, Wang Bin, Adjoint Code Generator (ADG), Users’ Manual, LASG, Institute of Atmospheric Physics (IAP), 2006
20 Wu W., Song L., Mo Y., et al., Xiamen―An ab initio spin-free valence bond (VB) program, Xiamen, Xiamen University, 1998
21 J.Verbeer, J.H.Langenberg, C.P.Byrman,F. Dijkstra and J.H.van Lenthe, TURTLE an Ab Initio VB/VBSCF program, Utrecht, 1998-1999.
22 Haruyuki Nakano, Cooper D.L. et al, J.Mole.Stru(Theochem), 1999, 461, 55
23 M.J.D. Powell, J. Inst. Math. Appl., 1971, 7, 21
24 S. Shaik and A. Shurki, Angew., Chem. Int. Ed., 1999, 38: 586-625.
25 Mu Mu. Nonlinear singular vectors and nonlinear singular values. Science in China (D), 43: 375-385, 2000