[發(fā)明專利]一種經(jīng)驗庫制導(dǎo)的浮點程序優(yōu)化加速方法

有效

• 申請?zhí)枺?/td>: 202110438904.2
• 申請日: 2021-04-22
• 公開（公告）號: CN113094021B
• 公開（公告）日: 2023-10-17
• 發(fā)明（設(shè)計）人: 湯恩義;肖安祥;陳鑫;王林章;李宣東
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: G06F7/483
• 分類號: G06F7/483;G06N5/02
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙) 32249
• 代理人: 沈廉

本發(fā)明提出了一種經(jīng)驗庫制導(dǎo)的浮點程序優(yōu)化加速方法。該方法基于浮點成因相似性原理，即若兩個浮點數(shù)值程序的計算過程相似，它們誤差累積的原因也往往是類似的，因而可以使用類似的程序轉(zhuǎn)換規(guī)則對其重寫，從而降低程序的累積誤差。基于此，加速策略將浮點數(shù)值程序的符號結(jié)構(gòu)特征以及優(yōu)化其累積誤差所用到的程序轉(zhuǎn)換規(guī)則提取出來，作為優(yōu)化經(jīng)驗保存于經(jīng)驗庫中。待優(yōu)化其他程序時，首先在經(jīng)驗庫中匹配待優(yōu)化程序的符號結(jié)構(gòu)特征，尋找相似程序的優(yōu)化經(jīng)驗，并利用這些經(jīng)驗來指導(dǎo)并加速優(yōu)化過程。優(yōu)化經(jīng)驗中保存的程序轉(zhuǎn)換規(guī)則會被優(yōu)先用于重寫待優(yōu)化程序，避免了對整個規(guī)則庫進行遍歷。這個過程減少了優(yōu)化所需的時間開銷，提高了浮點優(yōu)化的可用性。

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

本發(fā)明涉及一種經(jīng)驗庫制導(dǎo)的浮點程序優(yōu)化加速方法，屬于程序可靠性保障技術(shù)應(yīng)用領(lǐng)域。

背景技術(shù)

浮點數(shù)值程序在科學(xué)、工程和金融等多個領(lǐng)域具有非常廣泛的應(yīng)用。它使用有限精度的浮點數(shù)運算來模擬實數(shù)運算，從而不可避免地引入了舍入誤差。不當(dāng)?shù)某绦驅(qū)崿F(xiàn)有可能導(dǎo)致舍入誤差被逐步累積和放大，最終導(dǎo)致程序的計算結(jié)果和預(yù)期不一致，從而引發(fā)系統(tǒng)故障。在生命攸關(guān)的計算系統(tǒng)中，浮點誤差引發(fā)的程序故障有可能帶來災(zāi)難性后果。因此，浮點數(shù)值程序的正確性和可靠性需要得到保障。

為了保障浮點數(shù)值程序的可靠性，基于程序重寫技術(shù)的自動化浮點優(yōu)化技術(shù)逐漸得到關(guān)注。它使用程序轉(zhuǎn)換規(guī)則將浮點數(shù)值程序以數(shù)值更為穩(wěn)定的算法進行重寫，以生成計算誤差更小的程序。由于程序轉(zhuǎn)換規(guī)則是一些經(jīng)過嚴(yán)格證明的數(shù)學(xué)等式，保證了重寫后的程序和重寫前的程序在語義上具備等價性。

程序重寫技術(shù)的缺陷在于優(yōu)化效率不高。為了找到合適的程序轉(zhuǎn)換規(guī)則，它需要反復(fù)遍歷規(guī)則庫。在遍歷過程中，需要嘗試用程序轉(zhuǎn)換規(guī)則對程序進行重寫，并通過觀察重寫后程序的計算誤差是否減小，來判斷規(guī)則的有效性。這個過程十分耗時，且大部分時間被浪費于無意義的規(guī)則嘗試中，造成了優(yōu)化效率的低下。

針對這一問題，本發(fā)明提出了一種經(jīng)驗庫制導(dǎo)的浮點程序優(yōu)化加速策略。該策略基于浮點成因相似性原理，即若兩個浮點數(shù)值程序的計算過程相似，它們誤差累積的原因也往往是類似的，因而可以使用類似的程序轉(zhuǎn)換規(guī)則對其重寫，從而降低程序的累積誤差。基于此，加速策略將浮點數(shù)值程序的符號結(jié)構(gòu)特征以及優(yōu)化其累積誤差所用到的程序轉(zhuǎn)換規(guī)則提取出來，作為優(yōu)化經(jīng)驗保存于經(jīng)驗庫中。待優(yōu)化其他程序時，首先在經(jīng)驗庫中匹配待優(yōu)化程序的符號結(jié)構(gòu)特征，尋找相似程序的優(yōu)化經(jīng)驗，并利用這些經(jīng)驗來指導(dǎo)并加速優(yōu)化過程。優(yōu)化經(jīng)驗中保存的程序轉(zhuǎn)換規(guī)則會被優(yōu)先用于重寫待優(yōu)化程序，從而避免了對整個規(guī)則庫進行遍歷。這個過程減少了優(yōu)化所需的時間開銷，從而提高了浮點優(yōu)化技術(shù)的可用性。

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

技術(shù)問題：本發(fā)明提出了一種經(jīng)驗庫制導(dǎo)的浮點程序優(yōu)化加速方法，該方法可以提高基于程序重寫技術(shù)的浮點程序優(yōu)化方法的優(yōu)化效率，從而顯著提高這類技術(shù)的可用性。

技術(shù)方案：本發(fā)明基于經(jīng)驗庫制導(dǎo)技術(shù)，可以幫助優(yōu)化算法快速找出能有效降低程序計算誤差的程序轉(zhuǎn)換規(guī)則。使用這些規(guī)則對程序進行重寫，可以生成計算誤差更小的等價程序，從而提高浮點程序的數(shù)值穩(wěn)定性。本方法包含的具體步驟為：

1-1.從優(yōu)化經(jīng)驗庫中查詢相似程序的優(yōu)化經(jīng)驗，并生成一個候選優(yōu)化經(jīng)驗集，這些經(jīng)驗記錄了在優(yōu)化相似程序時使用過的程序轉(zhuǎn)換規(guī)則序列，這些規(guī)則序列將被用于指導(dǎo)優(yōu)化過程；

1-2.獲取到優(yōu)化經(jīng)驗后，優(yōu)化算法優(yōu)先使用優(yōu)化經(jīng)驗記錄的程序轉(zhuǎn)換規(guī)則對待優(yōu)化程序進行重寫，并生成一個程序候選集；通過區(qū)間劃分技術(shù)，優(yōu)化算法從程序候選集中挑選出合適的候選程序，并對其進行合并來生成最終的優(yōu)化結(jié)果；

1-3.通過對優(yōu)化后程序進行解析，抽取出該程序的優(yōu)化經(jīng)驗；這些優(yōu)化經(jīng)驗被保存到優(yōu)化經(jīng)驗庫中，以便在優(yōu)化其他程序時發(fā)揮其指導(dǎo)作用。

其中,

所述的步驟1-1，從優(yōu)化經(jīng)驗庫中查詢相似程序的優(yōu)化經(jīng)驗，匹配待優(yōu)化程序與經(jīng)驗庫程序的相似程度，找到相似程度較高的程序，并將它們的優(yōu)化經(jīng)驗抽取出來。