[發(fā)明專利]一種數(shù)值程序的全局優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201810001948.7
• 申請日: 2018-01-02
• 公開（公告）號: CN108228187B
• 公開（公告）日: 2020-03-17
• 發(fā)明（設(shè)計）人: 王協(xié);肖安祥;湯恩義;王林章;馬駿;李宣東
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: G06F8/41
• 分類號: G06F8/41
• 代理公司: 南京瑞弘專利商標事務(wù)所(普通合伙) 32249
• 代理人: 沈廉

1.一種數(shù)值程序的全局優(yōu)化方法，其特征在于該方法通過符號執(zhí)行技術(shù)抽取關(guān)于數(shù)值程序計算過程的全局代數(shù)表示，不斷尋找數(shù)值誤差更小的代數(shù)表示，從而使得數(shù)值計算得到優(yōu)化，具體步驟為：

1-1)、利用符號執(zhí)行技術(shù)動態(tài)執(zhí)行原始數(shù)值程序，記錄數(shù)值程序的結(jié)構(gòu)信息、每條執(zhí)行路徑的路徑約束條件以及計算過程的代數(shù)表示；

1-2)、分別分析步驟1-1)收集的每個代數(shù)表示的全局形式，運用代數(shù)變換規(guī)則將原代數(shù)表示形式優(yōu)化成數(shù)值計算誤差更小的代數(shù)表示形式，再使用區(qū)間分析技術(shù)檢驗變換后代數(shù)形式的正確性，從而完成對每個代數(shù)表示形式的優(yōu)化；

1-3)、遍歷原始程序的抽象語法樹以及步驟1-2)生成的經(jīng)過優(yōu)化的代數(shù)表示形式，將代數(shù)表示形式對應(yīng)的代碼拼接到語法樹節(jié)點中路徑約束的提取位置合成所有代碼片段，最終構(gòu)成目標程序；

其中所述的步驟1-2)中運用代數(shù)變換規(guī)則將原代數(shù)表示形式轉(zhuǎn)換成數(shù)值計算誤差更小的代數(shù)表示形式，具體過程如下：

3-1)、初始化原始代數(shù)表示集合F；

3-2)、對于F中的每個代數(shù)表示E，構(gòu)建代數(shù)表示集合S＝{E}；

3-3)、用戶任選一種配置好的選擇策略包括隨機策略、機器學(xué)習(xí)、或者遺傳算法策略，并按照該策略從S中選取一個代數(shù)表示E_i，并任選一種選擇策略從變換規(guī)則集中選取一個數(shù)學(xué)代數(shù)變換規(guī)則R_i，將R_i應(yīng)用于E_i生成一個數(shù)學(xué)等價的代數(shù)表示E_i'；

3-4)、使用區(qū)間分析技術(shù)分析E_i'的誤差區(qū)間是否擴大，如果沒有擴大，則代數(shù)表示Ei'即為原始代數(shù)表示E的優(yōu)化結(jié)果，將E從原始代數(shù)表示集合F中移除，跳轉(zhuǎn)到步驟3-6)；否則，執(zhí)行步驟3-5)；

3-5)、將代數(shù)變換后的代數(shù)表示E_i'加入代數(shù)表示S，跳轉(zhuǎn)回到步驟3-3)；

3-6)、判斷原始代數(shù)表示集合F是否還存在待優(yōu)化的代數(shù)表示，如果存在，跳轉(zhuǎn)回到步驟3-2)；否則，優(yōu)化過程結(jié)束。

2.根據(jù)權(quán)利要求1所述的一種數(shù)值程序的全局優(yōu)化方法，其特征在于所述步驟1-1)中利用符號執(zhí)行技術(shù)動態(tài)執(zhí)行原始數(shù)值程序，記錄數(shù)值程序的結(jié)構(gòu)信息、每條執(zhí)行路徑的路徑約束條件以及計算過程的代數(shù)表示，它的輸出是一棵抽象語法樹；該抽象語法樹只有四種節(jié)點，分別為代數(shù)表示節(jié)點，基本語句塊節(jié)點，分支節(jié)點和循環(huán)節(jié)點；代數(shù)表示節(jié)點是數(shù)值程序計算過程的抽象，用于記錄符號的代數(shù)表示；基本語句塊節(jié)點用于表示數(shù)值程序的順序結(jié)構(gòu)，它的子節(jié)點可以由任意四種節(jié)點按序構(gòu)成；分支節(jié)點用于表示數(shù)值程序的分支結(jié)構(gòu)；循環(huán)節(jié)點用于抽象數(shù)值程序的循環(huán)結(jié)構(gòu)，通過循環(huán)節(jié)點可以將循環(huán)的計算過程抽象成為一條累積求值表達式，整個抽象語法樹抽象了數(shù)值程序的結(jié)構(gòu)信息以及計算過程。

3.根據(jù)權(quán)利要求1或2所述的一種數(shù)值程序的全局優(yōu)化方法，其特征在于所述的抽象語法樹，其構(gòu)造過程具體如下：

2-1)、啟動符號執(zhí)行，初始化根節(jié)點為基本塊節(jié)點，在執(zhí)行過程中對基本塊結(jié)構(gòu)、分支結(jié)構(gòu)以及循環(huán)結(jié)構(gòu)分別進行處理；

2-2)、如果當前執(zhí)行的是基本塊結(jié)構(gòu)，將根據(jù)以下三種情況進行處理：

當遇到基本語句，將計算過程轉(zhuǎn)換為一個代數(shù)表示，并生成一個代數(shù)表示節(jié)點作為當前基本塊節(jié)點的子節(jié)點；

當遇到分支語句，轉(zhuǎn)步驟2-3)生成一個分支節(jié)點作為當前基本塊節(jié)點的子節(jié)點；

當遇到循環(huán)語句，轉(zhuǎn)步驟2-4)生成一個循環(huán)節(jié)點作為當前基本塊節(jié)點的子節(jié)點；

2-3)、如果當前執(zhí)行的是分支結(jié)構(gòu)，將分支條件作為一個路徑約束，生成一個分支節(jié)點，分支結(jié)構(gòu)的執(zhí)行體是一個基本塊，根據(jù)步驟2-2)，生成一個基本塊節(jié)點并將其作為當前分支節(jié)點的子節(jié)點；

2-4)、如果當前執(zhí)行的是循環(huán)結(jié)構(gòu)，將循環(huán)的計算過程抽象成為一個代數(shù)表示，并生成一個循環(huán)節(jié)點。

4.根據(jù)權(quán)利要求1所述的一種數(shù)值程序的全局優(yōu)化方法，其特征在于所述的步驟1-3)中遍歷原始程序的抽象語法樹以及步驟1-2)生成的經(jīng)過優(yōu)化的代數(shù)表示形式，將代數(shù)表示形式對應(yīng)的代碼拼接到語法樹節(jié)點中路徑約束的提取位置合成所有代碼片段，最終構(gòu)成目標程序，具體過程如下：

4-1)、先序遍歷抽象語法樹，根據(jù)不同的語法樹節(jié)點類型生成不同的代碼片段，組合所有生成的代碼片段最終生成目標程序；

4-2)、遇到代數(shù)表示節(jié)點，如果存在輸入?yún)^(qū)間使得該代數(shù)表示的數(shù)值計算發(fā)生錯誤，則生成一個分支語句，分支條件記為C，它判斷輸入是否處于這個輸入?yún)^(qū)間；如果C為真，將經(jīng)過優(yōu)化的代數(shù)表示轉(zhuǎn)換為相應(yīng)代碼；否則，將原始的代數(shù)表示轉(zhuǎn)換為相應(yīng)代碼；如果不存在這樣的輸入?yún)^(qū)間，則直接將原始的代數(shù)表示轉(zhuǎn)換為相應(yīng)代碼；

4-3)、以下節(jié)點為結(jié)構(gòu)節(jié)點，主要通過遞歸處理子節(jié)點來生成代碼片段，根據(jù)結(jié)構(gòu)節(jié)點的不同作不同處理，具體步驟為：

當遇到基本塊節(jié)點，遞歸處理它的子節(jié)點；

當遇到分支節(jié)點，生成一個分支語句，將該節(jié)點記錄的路徑約束轉(zhuǎn)換成分支條件，遞歸處理該節(jié)點的子節(jié)點生成分支語句的執(zhí)行體部分；

當遇到循環(huán)節(jié)點，將循環(huán)結(jié)構(gòu)抽象出來的代數(shù)表示轉(zhuǎn)換為相應(yīng)代碼。