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

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

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

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

5、具體方法是：在所有隨機(jī)抽樣得到de初始場（或網(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語言編寫de源代碼，微分代碼結(jié)構(gòu)清晰，其微分處理能力與問題和對象de規(guī)模及復(fù)雜性無關(guān)。它基于YACC實(shí)現(xiàn)，具有很強(qiáng)de可擴(kuò)展性。DFT系統(tǒng)具有四個(gè)重要特色。它通過對象全局依賴相關(guān)分析，準(zhǔn)確求解雅可比矩陣de稀疏結(jié)構(gòu)，自動(dòng)計(jì)算有效初始輸入矩陣，從而可以用較小de代價(jià)求得整個(gè)雅可比矩陣。同時(shí)，它可以自動(dòng)生成客觀評(píng)價(jià)微分模式效率與可靠性de測試程序，對奇異函數(shù)做等價(jià)微分

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

7、#160;                         原模式                        

8、60;                                                 

9、60; 切線性模式                                                 &#

10、160;                                                 &#

11、160;                                                 &#

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

13、#160;                                                   

14、;                                                  

15、;                                                  

16、0;                                                 

17、0;                          切線性模式                       

18、0;                                                 

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

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

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

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

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

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

25、60;           圖2.5   切線性模式代碼de測試過程    3.系統(tǒng)主要特色    DFT系統(tǒng)并不是一個(gè)完整deFORTRAN編譯器，但它幾乎可以接受和處理所有FORTRAN 77編寫de源模式代碼，并且可以很方便地?cái)U(kuò)展并接受FORTRAN 90編寫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)，切線性模式de擾動(dòng)變量和基態(tài)值變量、微分計(jì)算語句和基態(tài)值計(jì)算語句總是成對出現(xiàn)，并具有清晰de程序結(jié)構(gòu)。微分代碼保持了原模式本身de結(jié)構(gòu)和風(fēng)格（如并行和向量特性、數(shù)據(jù)精度等），即語句到語句、結(jié)構(gòu)到結(jié)構(gòu)de微分實(shí)現(xiàn)。在奇異點(diǎn)或不可導(dǎo)處，DFT系統(tǒng)對微分?jǐn)_動(dòng)采取簡單de清零處理，實(shí)踐證明這對抑制擾動(dòng)計(jì)算溢出具有重要意義，但并不影響評(píng)價(jià)測試結(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ù)依賴相關(guān)分析、全局過程相關(guān)分析以及數(shù)據(jù)迭代相關(guān)分析幾個(gè)不同方面。數(shù)據(jù)依賴相關(guān)與數(shù)據(jù)IO相關(guān)關(guān)系密切，但又存在根本不同。前者強(qiáng)調(diào)每個(gè)變量在數(shù)學(xué)關(guān)系上de依賴性；而后者描述了一個(gè)對象de輸入輸出特性，且具有相對性，即任何一個(gè)變量參數(shù)，無論它是獨(dú)立變量還是依賴變量，在數(shù)學(xué)意義上都可等價(jià)為一個(gè)既是輸入又是輸出de參數(shù)來處理。        DFT系統(tǒng)記錄所有過程參數(shù)deIO屬性表，通過深度遞歸相關(guān)計(jì)算，準(zhǔn)

28、確計(jì)算每個(gè)過程參數(shù)de最終IO屬性。DFT系統(tǒng)通過對數(shù)據(jù)相關(guān)矩陣做模二和及自乘迭代計(jì)算（An+1= AnAn2）來完成數(shù)據(jù)de依賴相關(guān)分析，這種算法具有很好de對數(shù)收斂特性。DFT系統(tǒng)通過全局過程相關(guān)分析de結(jié)果，自動(dòng)生成模式de局部或整體相關(guān)引用樹結(jié)構(gòu)（如圖3.1），這對用戶分析復(fù)雜數(shù)值模式和微分評(píng)價(jià)測試都具有很好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)樹結(jié)構(gòu)片段    3.3 自動(dòng)生成測試程序      

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