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

有效

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

本發(fā)明提出了一種數(shù)值程序的全局優(yōu)化方法，利用符號(hào)執(zhí)行技術(shù)從源程序中抽取用于表述路徑約束條件以及數(shù)值計(jì)算過(guò)程的代數(shù)表示。并分析每個(gè)代數(shù)表示，通過(guò)運(yùn)用不同地代數(shù)變換規(guī)則將其轉(zhuǎn)換成數(shù)值計(jì)算誤差更小的代數(shù)形式。最終把每個(gè)代數(shù)表示轉(zhuǎn)成相應(yīng)的代碼片段，并將它們組合生成目標(biāo)程序。本發(fā)明具有以下優(yōu)勢(shì)：所有過(guò)程均為自動(dòng)化過(guò)程，無(wú)需人為干預(yù)；程序編寫(xiě)者可以更專(zhuān)注于業(yè)務(wù)邏輯，而無(wú)需關(guān)心與數(shù)值分析相關(guān)的細(xì)節(jié)操作。這樣既提高了開(kāi)發(fā)效率，又使代碼邏輯直觀易懂，易于維護(hù)。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)數(shù)值計(jì)算與程序分析應(yīng)用領(lǐng)域，涉及數(shù)值程序的全局優(yōu)化技術(shù)，主要通過(guò)收集數(shù)值程序的全局計(jì)算過(guò)程而獲得對(duì)應(yīng)代數(shù)表示，并將其轉(zhuǎn)換成數(shù)值誤差累積更小的計(jì)算過(guò)程，以便生成相對(duì)原始數(shù)值程序更為準(zhǔn)確，高效的優(yōu)化程序。

背景技術(shù)

根據(jù)IEEE745標(biāo)準(zhǔn)，單精度浮點(diǎn)數(shù)占用32個(gè)比特位，雙精度浮點(diǎn)數(shù)占用64個(gè)比特位，盡管很多軟件開(kāi)發(fā)人員在開(kāi)發(fā)程序時(shí)將它們看作實(shí)數(shù)值，但實(shí)際上它們能表示的數(shù)值是有限且不連續(xù)的。因此，對(duì)于大部分程序而言，浮點(diǎn)數(shù)會(huì)因?yàn)橹荒鼙硎緦?shí)數(shù)的近似值而不可避免地引入數(shù)值誤差。在一個(gè)源程序中，可能涉及大量浮點(diǎn)數(shù)運(yùn)算，這些浮點(diǎn)數(shù)運(yùn)算的誤差會(huì)隨著程序的推進(jìn)而累積，最終導(dǎo)致程序計(jì)算錯(cuò)誤。

為了避免這些數(shù)值計(jì)算錯(cuò)誤，軟件開(kāi)發(fā)人員在編寫(xiě)數(shù)值計(jì)算程序前往往需要經(jīng)過(guò)專(zhuān)業(yè)的數(shù)值分析培訓(xùn)，掌握許多數(shù)值分析的背景知識(shí)，并在編寫(xiě)相關(guān)程序時(shí)引入大量數(shù)值相關(guān)的細(xì)節(jié)操作。由于許多這樣的細(xì)節(jié)操作與硬件平臺(tái)相關(guān)，不僅非常繁瑣，且極易出錯(cuò)，從而導(dǎo)致數(shù)值程序的主要邏輯被這些細(xì)節(jié)操作掩蓋，降低了源代碼的可讀性，既不利于代碼的正確開(kāi)發(fā)，也不利于后續(xù)的代碼維護(hù)。因此，本發(fā)明構(gòu)建了一種數(shù)值程序的全局優(yōu)化方法來(lái)解決這一問(wèn)題。我們首先收集數(shù)值程序的全局計(jì)算過(guò)程，并而獲得對(duì)應(yīng)代數(shù)表示，并將其轉(zhuǎn)換成數(shù)值誤差累積更小的計(jì)算過(guò)程，以便生成相對(duì)原始數(shù)值程序更為準(zhǔn)確，高效的優(yōu)化程序。

為了完成對(duì)數(shù)值程序計(jì)算過(guò)程的抽取，我們需要使用符號(hào)執(zhí)行技術(shù)。符號(hào)執(zhí)行技術(shù)最早由James King于1976年應(yīng)用于系統(tǒng)測(cè)試領(lǐng)域。其主要思想在于用符號(hào)代替程序的具體輸入值，然后按照程序邏輯在一定平臺(tái)上進(jìn)行模擬執(zhí)行。在執(zhí)行過(guò)程中，符號(hào)執(zhí)行引擎會(huì)收集執(zhí)行路徑的路徑約束。通過(guò)約束求解器對(duì)路徑約束進(jìn)行求解，可以生成覆蓋各個(gè)執(zhí)行路徑的測(cè)試用例。在符號(hào)執(zhí)行引擎現(xiàn)有基礎(chǔ)上，我們將對(duì)其進(jìn)行改進(jìn)，從而完成對(duì)數(shù)值程序計(jì)算過(guò)程的抽取工作。

發(fā)明內(nèi)容

技術(shù)問(wèn)題：本發(fā)明提出了一種數(shù)值程序的全局優(yōu)化方法，它將原始數(shù)值程序自動(dòng)地轉(zhuǎn)化成計(jì)算邏輯相同但誤差積累更小的優(yōu)化數(shù)值程序。所述的數(shù)值程序的全局優(yōu)化方法通過(guò)動(dòng)態(tài)符號(hào)執(zhí)行的方式抽取了程序返回值的符號(hào)表達(dá)式，同時(shí)通過(guò)數(shù)學(xué)代數(shù)變換的方式尋找等價(jià)且數(shù)值誤差更小的表達(dá)式，將復(fù)雜的程序邏輯轉(zhuǎn)換為對(duì)表達(dá)式的分析，從而實(shí)現(xiàn)對(duì)數(shù)值計(jì)算的全局優(yōu)化。

技術(shù)方案：本發(fā)明的一種數(shù)值程序的全局優(yōu)化方法通過(guò)符號(hào)執(zhí)行技術(shù)抽取關(guān)于數(shù)值程序計(jì)算過(guò)程的全局代數(shù)表示，不斷尋找數(shù)值誤差更小的代數(shù)表示，從而使得數(shù)值計(jì)算得到優(yōu)化，具體步驟為：

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

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

1-3)、遍歷原始程序的抽象語(yǔ)法樹(shù)以及步驟1-2)生成的經(jīng)過(guò)優(yōu)化的代數(shù)表示形式，將代數(shù)表示形式對(duì)應(yīng)的代碼拼接到語(yǔ)法樹(shù)節(jié)點(diǎn)中路徑約束的提取位置(例如分支語(yǔ)句、循環(huán)語(yǔ)句)，合成所有代碼片段，最終構(gòu)成目標(biāo)程序。

其中，