自動(dòng)微分轉(zhuǎn)換系統(tǒng)及其應(yīng)用

1、自動(dòng)微分轉(zhuǎn)換系統(tǒng)及其應(yīng)用    摘要    自動(dòng)微分轉(zhuǎn)換系統(tǒng)（DFT）由LASG和LSEC聯(lián)合研制開(kāi)發(fā)，目前已擁有成熟de版本。本文對(duì)DFT系統(tǒng)de功能、特色及其基本應(yīng)用作了全面de介紹，并給出了一些頗具說(shuō)服力de數(shù)值試驗(yàn)結(jié)果。同時(shí)，本文提出了統(tǒng)計(jì)準(zhǔn)確率評(píng)價(jià)de概念，這對(duì)評(píng)價(jià)一類(lèi)自動(dòng)微分工具及其微分模式代碼de可靠性與有效性提供了一種客觀(guān)de尺度。最后，本文還詳細(xì)討論了運(yùn)用切線(xiàn)性模式求解雅可比矩陣de問(wèn)題，給出了求解初始輸入矩陣de有效算法。    關(guān)鍵詞 自動(dòng)微分  切線(xiàn)性

2、模式  數(shù)據(jù)相關(guān)分析  統(tǒng)計(jì)準(zhǔn)確率    1.引言    計(jì)算微分大致經(jīng)歷了從商微分，符號(hào)微分，手寫(xiě)代碼到自動(dòng)微分幾個(gè)階段。與其它幾種微分方法相比，自動(dòng)微分具有代碼簡(jiǎn)練、計(jì)算精度高及投入人力少等優(yōu)點(diǎn)。自動(dòng)微分實(shí)現(xiàn)de基本出發(fā)點(diǎn)是：一個(gè)數(shù)據(jù)相對(duì)獨(dú)立de程序?qū)ο螅Ｊ?、過(guò)程、程序段、數(shù)值語(yǔ)句乃至數(shù)值表達(dá)式），無(wú)論多么復(fù)雜，總可以分解為一系列有限數(shù)目的基本函數(shù)（如sin、exp、log）和基本運(yùn)算操作（加、減、乘、除、乘方）de有序復(fù)合；對(duì)所有這些基本函數(shù)及基本運(yùn)算操作，重復(fù)使用鏈?zhǔn)角髮?dǎo)法則，將得到d

3、e中間結(jié)果自上而下地做正向積分就可以建立起對(duì)應(yīng)de切線(xiàn)性模式，而自下而上地做反向積分就可以建立起對(duì)應(yīng)de伴隨模式1。基于自動(dòng)微分方法得到de切線(xiàn)性模式和伴隨模式，在變分資料同化2、系統(tǒng)建模與參數(shù)辨識(shí)3、參數(shù)de敏感性分析4、非線(xiàn)性最優(yōu)化以及數(shù)值模式de可預(yù)測(cè)性分析5等問(wèn)題中有著十分廣泛de應(yīng)用。迄今為止，已有數(shù)十所大學(xué)和研究所各自開(kāi)發(fā)了能夠用于求解切線(xiàn)性模式de自動(dòng)微分系統(tǒng)，比較典型de有TAMC系統(tǒng)6、ADJIFOR系統(tǒng)7 和ODYSSEE系統(tǒng)8。在一些特定de運(yùn)用中，它們都是比較成功de，但在通用性和復(fù)雜問(wèn)題de處理效率上還存在許多不足。通常，自動(dòng)生成切線(xiàn)性模式de關(guān)鍵難題在于對(duì)象自身de

4、強(qiáng)相關(guān)性，這給系統(tǒng)全局分析（如數(shù)據(jù)IO相關(guān)分析和數(shù)據(jù)依賴(lài)相關(guān)分析）和微分代碼de整體優(yōu)化都帶來(lái)了很多困難。同時(shí)，對(duì)于程序?qū)ο蟛豢蓪?dǎo)處de準(zhǔn)確識(shí)別和微分處理，至今仍還沒(méi)有一個(gè)統(tǒng)一而有效de算法。另外，最優(yōu)或有效求解稀疏雅可比矩陣一直是衡量一個(gè)自動(dòng)微分系統(tǒng)有效性de重要尺度。統(tǒng)計(jì)準(zhǔn)確率被我們視為評(píng)價(jià)一類(lèi)自動(dòng)微分工具及其微分模式代碼可靠性與有效性de重要尺度。其基本假設(shè)是：如果對(duì)于定義域空間內(nèi)隨機(jī)抽樣獲得de至多有限個(gè)n維初始場(chǎng)（或網(wǎng)格點(diǎn)），微分模式輸出de差分和微分逼近是成功de；那么對(duì)于定義域空間內(nèi)所有可能初始場(chǎng)（或網(wǎng)格點(diǎn)），微分模式輸出de差分和微分逼近都是成功de。微分模式統(tǒng)計(jì)準(zhǔn)確率評(píng)價(jià)de

5、具體方法是：在所有隨機(jī)抽樣得到de初始場(chǎng)（或網(wǎng)格點(diǎn)）附近，當(dāng)輸入擾動(dòng)逐漸趨向于機(jī)器有效精度所能表示de最小正值時(shí)，模式輸出de差分和微分之間應(yīng)該有足夠精度有效位數(shù)上de逼近。DFT系統(tǒng)具有許多優(yōu)點(diǎn)，它能夠完全接受用FORTRAN 77語(yǔ)言編寫(xiě)de源代碼，微分代碼結(jié)構(gòu)清晰，其微分處理能力與問(wèn)題和對(duì)象de規(guī)模及復(fù)雜性無(wú)關(guān)。它基于YACC實(shí)現(xiàn)，具有很強(qiáng)de可擴(kuò)展性。DFT系統(tǒng)具有四個(gè)重要特色。它通過(guò)對(duì)象全局依賴(lài)相關(guān)分析，準(zhǔn)確求解雅可比矩陣de稀疏結(jié)構(gòu)，自動(dòng)計(jì)算有效初始輸入矩陣，從而可以用較小de代價(jià)求得整個(gè)雅可比矩陣。同時(shí)，它可以自動(dòng)生成客觀(guān)評(píng)價(jià)微分模式效率與可靠性de測(cè)試程序，對(duì)奇異函數(shù)做等價(jià)微分

6、處理，并采用二元?dú)w約de方法，在語(yǔ)句級(jí)層次上實(shí)現(xiàn)微分代碼優(yōu)化。    2.系統(tǒng)概況  DFT系統(tǒng)主要由兩部分組成：微分代碼轉(zhuǎn)換和微分代碼評(píng)價(jià)，圖2.1。微分代碼轉(zhuǎn)換部分接受用戶(hù)輸入指令并自動(dòng)分析對(duì)象模式，生成切線(xiàn)性模式代碼及其相關(guān)測(cè)試代碼，后者直接構(gòu)成微分代碼評(píng)價(jià)系統(tǒng)de主體。微分代碼評(píng)價(jià)是DFT系統(tǒng)de一個(gè)重要特色。DFT系統(tǒng)de開(kāi)發(fā)小組認(rèn)為，一個(gè)微分模式如果在可靠性、時(shí)間和存儲(chǔ)效率上沒(méi)有得到充分de驗(yàn)證，至少對(duì)實(shí)際應(yīng)用而言，它將是毫無(wú)意義de。        &

7、#160;                         原模式                        

8、60;                                                 

9、60; 切線(xiàn)性模式                                                 &#

10、160;                                                 &#

11、160;                                                 &#

12、160;    統(tǒng)計(jì)評(píng)價(jià)結(jié)果     圖2.1  DFT系統(tǒng)結(jié)構(gòu)簡(jiǎn)圖    2.1 微分代碼轉(zhuǎn)換    DFT系統(tǒng)是基于YACC在UNIX環(huán)境下開(kāi)發(fā)de，其結(jié)構(gòu)圖2.2所示。通過(guò)DFT系統(tǒng)產(chǎn)生de切線(xiàn)性模式代碼成對(duì)出現(xiàn)，并在語(yǔ)句級(jí)程度上做了簡(jiǎn)化，可讀性很強(qiáng)，如圖2.4。              &

13、#160;                                                   

14、;                                                  

15、;                                                  

16、0;                                                 

17、0;                          切線(xiàn)性模式                       

18、0;                                                 

19、0;                                              評(píng)價(jià)函數(shù)集   

20、0;圖2.2   微分代碼轉(zhuǎn)換         微分代碼轉(zhuǎn)換部分從功能上分為四個(gè)部分：詞法分析，語(yǔ)義分析，對(duì)象復(fù)雜性及數(shù)據(jù)相關(guān)分析和微分代碼轉(zhuǎn)換。對(duì)于一組具有復(fù)雜數(shù)據(jù)相關(guān)de程序模式對(duì)象，通常需要系統(tǒng)運(yùn)行兩遍才能得到有效而可靠de微分代碼。這主要有兩方面de考慮：其一，根據(jù)對(duì)象de復(fù)雜性（如最大語(yǔ)句長(zhǎng)度、最大變量維數(shù)、子過(guò)程或函數(shù)數(shù)目、子過(guò)程或函數(shù)內(nèi)最大變量數(shù)目等對(duì)象特征）選擇合適de系統(tǒng)參數(shù)以求最優(yōu)de運(yùn)行代價(jià)；其二，模式內(nèi)各子過(guò)程或函數(shù)之間以及一個(gè)子過(guò)程或函數(shù)內(nèi)往往具有很強(qiáng)de數(shù)據(jù)相關(guān)性，需

21、要事先保存對(duì)象de相關(guān)信息并且在考慮當(dāng)前對(duì)象de屬性之前必須做上下文相關(guān)分析。                                           

22、60;                         圖2.3   PERIGEE源程序代碼                    

23、60;     圖2.4  DFT系統(tǒng)生成de切線(xiàn)性代碼    2.2 微分代碼評(píng)價(jià)    通常，評(píng)價(jià)一個(gè)編譯系統(tǒng)de性能有很多方面，如處理速度、結(jié)果代碼可靠性及質(zhì)量、出錯(cuò)診斷、可擴(kuò)展和可維護(hù)性等。對(duì)于一類(lèi)自動(dòng)微分系統(tǒng)來(lái)說(shuō)，由于軟件開(kāi)發(fā)人力de局限以及對(duì)象模式de復(fù)雜多樣性,通過(guò)自動(dòng)轉(zhuǎn)換得到de微分模式并非常常是有效而可靠de（即無(wú)論是在數(shù)學(xué)意義上還是在程序邏輯上應(yīng)與期待de理想結(jié)果一致），因而在微分模式被投入實(shí)際應(yīng)用前，往往需要投入一定de人力來(lái)對(duì)其做嚴(yán)格de分析

24、測(cè)試。  對(duì)切線(xiàn)性模式做統(tǒng)計(jì)評(píng)價(jià)測(cè)試de主要內(nèi)容可以簡(jiǎn)單敘述為：在網(wǎng)格化de模式定義域空間內(nèi)，選擇所有可能de網(wǎng)格點(diǎn)形成微分模式計(jì)算de初始場(chǎng)；在不同de網(wǎng)格點(diǎn)附近，隨機(jī)選取至少 個(gè)線(xiàn)性無(wú)關(guān)de初始擾動(dòng)，對(duì)每個(gè)擾動(dòng)輸入分別進(jìn)行網(wǎng)格點(diǎn)逼近，統(tǒng)計(jì)考察模式輸出差分和微分在有效位數(shù)上de逼近程度。圖2.5描述了整個(gè)測(cè)試過(guò)程，它包含網(wǎng)格點(diǎn)數(shù)據(jù)隨機(jī)采樣（1）和網(wǎng)格點(diǎn)數(shù)據(jù)逼近（2）兩級(jí)循環(huán)。                 

25、60;           圖2.5   切線(xiàn)性模式代碼de測(cè)試過(guò)程    3.系統(tǒng)主要特色    DFT系統(tǒng)并不是一個(gè)完整deFORTRAN編譯器，但它幾乎可以接受和處理所有FORTRAN 77編寫(xiě)de源模式代碼，并且可以很方便地?cái)U(kuò)展并接受FORTRAN 90編寫(xiě)de源模式代碼。本節(jié)將著重介紹DFT系統(tǒng)（版本3.0）de以下幾個(gè)重要特色。    

26、3.1 結(jié)構(gòu)化de微分實(shí)現(xiàn)    DFT系統(tǒng)采用標(biāo)準(zhǔn)化de代碼實(shí)現(xiàn)，切線(xiàn)性模式de擾動(dòng)變量和基態(tài)值變量、微分計(jì)算語(yǔ)句和基態(tài)值計(jì)算語(yǔ)句總是成對(duì)出現(xiàn)，并具有清晰de程序結(jié)構(gòu)。微分代碼保持了原模式本身de結(jié)構(gòu)和風(fēng)格（如并行和向量特性、數(shù)據(jù)精度等），即語(yǔ)句到語(yǔ)句、結(jié)構(gòu)到結(jié)構(gòu)de微分實(shí)現(xiàn)。在奇異點(diǎn)或不可導(dǎo)處，DFT系統(tǒng)對(duì)微分?jǐn)_動(dòng)采取簡(jiǎn)單de清零處理，實(shí)踐證明這對(duì)抑制擾動(dòng)計(jì)算溢出具有重要意義，但并不影響評(píng)價(jià)測(cè)試結(jié)果。    3.2 全局?jǐn)?shù)據(jù)相關(guān)分析      

27、0;     DFT系統(tǒng)具有較強(qiáng)de數(shù)據(jù)相關(guān)分析能力，它包括全局?jǐn)?shù)據(jù)IO相關(guān)分析、全局?jǐn)?shù)據(jù)依賴(lài)相關(guān)分析、全局過(guò)程相關(guān)分析以及數(shù)據(jù)迭代相關(guān)分析幾個(gè)不同方面。數(shù)據(jù)依賴(lài)相關(guān)與數(shù)據(jù)IO相關(guān)關(guān)系密切，但又存在根本不同。前者強(qiáng)調(diào)每個(gè)變量在數(shù)學(xué)關(guān)系上de依賴(lài)性；而后者描述了一個(gè)對(duì)象de輸入輸出特性，且具有相對(duì)性，即任何一個(gè)變量參數(shù)，無(wú)論它是獨(dú)立變量還是依賴(lài)變量，在數(shù)學(xué)意義上都可等價(jià)為一個(gè)既是輸入又是輸出de參數(shù)來(lái)處理。        DFT系統(tǒng)記錄所有過(guò)程參數(shù)deIO屬性表，通過(guò)深度遞歸相關(guān)計(jì)算，準(zhǔn)

28、確計(jì)算每個(gè)過(guò)程參數(shù)de最終IO屬性。DFT系統(tǒng)通過(guò)對(duì)數(shù)據(jù)相關(guān)矩陣做模二和及自乘迭代計(jì)算（An+1= AnAn2）來(lái)完成數(shù)據(jù)de依賴(lài)相關(guān)分析，這種算法具有很好de對(duì)數(shù)收斂特性。DFT系統(tǒng)通過(guò)全局過(guò)程相關(guān)分析de結(jié)果，自動(dòng)生成模式de局部或整體相關(guān)引用樹(shù)結(jié)構(gòu)（如圖3.1），這對(duì)用戶(hù)分析復(fù)雜數(shù)值模式和微分評(píng)價(jià)測(cè)試都具有很好de指導(dǎo)作用。DFT系統(tǒng)還具有分析局部數(shù)據(jù)迭代相關(guān)和函數(shù)迭代相關(guān)de能力，這兩種形式de數(shù)據(jù)迭代相關(guān)是自動(dòng)微分實(shí)現(xiàn)頗具挑戰(zhàn)de難題之一。            &

29、#160;                               圖3.1  GPS Rayshooting模式de相關(guān)樹(shù)結(jié)構(gòu)片段    3.3 自動(dòng)生成測(cè)試程序      

30、      基于IO相關(guān)分析de結(jié)果，DFT系統(tǒng)自動(dòng)生成微分測(cè)試代碼，分別對(duì)切線(xiàn)性模式de可靠性和運(yùn)行代價(jià)做統(tǒng)計(jì)評(píng)價(jià)測(cè)試。特別地，DFT系統(tǒng)還可將任何模式參數(shù)都視為輸入輸出參數(shù)，生成在數(shù)學(xué)意義上等價(jià)de測(cè)試代碼，這樣處理de不利之處在于往往需要極高de存儲(chǔ)開(kāi)銷(xiāo)。    3.4 基于語(yǔ)句級(jí)de代碼優(yōu)化           目前，DFT系統(tǒng)僅僅具備局地優(yōu)化能力。在語(yǔ)句級(jí)微分實(shí)現(xiàn)上采用二元?dú)w約de方法對(duì)微分代碼進(jìn)行優(yōu)化是DFT系統(tǒng)de一個(gè)重要特色。根據(jù)右端表達(dá)式de乘法復(fù)雜性及含變?cè)獢?shù)目的不同，DFT系統(tǒng)采取不同de分解策略。二元?dú)w約de方法避免了微分計(jì)算中de許多冗余計(jì)算，在一些復(fù)雜de非線(xiàn)性表達(dá)式de微分計(jì)算中具有最小de計(jì)算代價(jià)，同時(shí)也非常適合于微分系統(tǒng)de軟件實(shí)現(xiàn)。同時(shí)，對(duì)于某些特殊de運(yùn)算操作（除法、乘方）和特殊函數(shù)（如sqrt、exp），DFT系統(tǒng)較好地利用了基態(tài)值計(jì)算得到de中間結(jié)果，避免了微分實(shí)現(xiàn)中de冗余計(jì)算。