[發明專利]多目標編譯優化序列選擇的代理建模方法

有效

• 申請號: 202010869346.0
• 申請日: 2020-08-26
• 公開（公告）號: CN112035116B
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 江賀;高國軍;任志磊
• 申請（專利權）人: 大連理工大學
• 主分類號: G06F8/41
• 分類號: G06F8/41;G06N3/12;G06N5/00
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 李曉亮;潘迅

本發明提供一種多目標編譯優化序列選擇的代理建模方法，是一種針對其計算代價約束問題的解決方案，屬于編譯器優化領域。首先將編譯優化序列進行二進制編碼，針對兩個優化目標代碼規模和運行速度分別設計適應度函數，在選擇、交叉操作后產生的子種群，并與父種群合并快速非支配排序產生新種群，最終獲得Pareto最優解集。在搜索迭代過程中，使用編譯優化序列以及對應的兩個目標適應度值分別構造代理模型，針對進化操作產生的子種群使用代理模型計算近似適應度值，并對其中優秀解計算實際適應度值，從而提高進化效率。本發明能夠有效地為待編譯程序選擇滿足多目標(如運行速度、代碼規模)的編譯優化序列，并解決迭代過程中帶來的計算代價約束問題。

技術領域

本發明屬于編譯器優化技術領域，涉及一種針對多目標編譯優化序列選擇中計算代價約束問題的代理建模方法。

背景技術

在實際開發過程中，編譯之后的目標機器代碼需要具有比較理想的性能，比如可執行代碼規模小和執行速度快。然而，對于編譯后的目標機器代碼來說，代碼規模和運行速度是具有一定沖突的優化目標。如果追求程序運行速度，將會使程序規模擴大。如果追求可執行代碼規模更小，則會影響程序運行速度。因此，如何為待編譯程序選擇合適的編譯優化序列使得其在代碼規模和運行速度兩個優化目標上得到一個權衡是一個關鍵問題。雖然編譯器提供了一些預定義的標準編譯優化序列(-O1、-O2、-O3、-Os等)。但是，對于同樣的編譯優化序列，由于待編譯程序、編譯環境以及編譯目標的不同，編譯器會產生不同優化效果的可執行代碼。因此，針對不同的待編譯程序，自適應的構造編譯優化序列相對于標準優化序列具有更強的優勢。

現代編譯器提供了大量的編譯優化選項，比如編譯器GCC提供了超過200個編譯優化選項，使用窮舉搜索或者人工的方式在數量龐大的選項組合中選擇最優的編譯優化序列是不現實的。針對多目標編譯優化序列選擇，以非支配排序多目標遺傳算法(NSGA-II)為代表的啟發式搜索算法是一種比較典型的解決發明，其利用進化的思想為待編譯程序搜索滿足多目標的編譯優化序列。但是，若將啟發式搜索算法中多目標優化算法應用于編譯優化序列選擇，在此過程中由于需要對種群個體進行大量的適應度評價，實際應用時需要對待編譯程序實際編譯得到可執行代碼，獲取代碼規模，另一個優化目標運行速度方面計算適應度值還需要實際運行該程序，這將會帶來相當大的計算代價約束的問題。例如，在非支配排序多目標遺傳算法中，每輪迭代過程中需要計算種群中每一個個體編碼對應的編譯優化序列的適應度值，即編譯器需要使用每一條優化序列對待編譯程序進行一次編譯，并執行程序以獲得其運行速度以及代碼規模，這將使得算法的執行時間開銷非常巨大，以此帶來計算代價約束問題。

為了解決上述問題，本發明通過一種基于代理的非支配排序多目標遺傳算法，在迭代搜索過程中構造編譯優化序列與編譯后可執行代碼規模以及運行速度之間的代理模型，通過代理模型獲取種群中個體對應的近似適應度值，只對其中部分優秀解計算實際適應度值，進而減少整個算法運行時間。

發明內容

本發明的目的是為多目標編譯優化序列選擇中計算代價約束問題提供了一種基于代理的非支配排序多目標遺傳算法，其利用代理模型提高算法的進化效率。

為了達到上述目的，本發明采用的技術方案為：

一種多目標編譯優化序列選擇的代理建模方法，步驟如下：

步驟1：編碼

使用二進制編碼，即由{0，1}字符集產生的0，1字符串來表示編譯優化序列；針對編譯器GCC中二值型的編譯優化選項(flag)，即使用或者不使用該選項；在二進制編碼字符串中，0表示不使用對應位置的優化選項，1表示使用對應位置的優化選項，例如編譯優化序列“-fno-auto-inc-dec-fcompare-elim-fdce…-fno-defer-pop”編碼為[0 1 1 … 0]；因本發明針對編譯器GCC的編譯優化選項順序對于最終編譯構建結果沒有影響，故使用固定順序的二進制編碼即可滿足實際需求；同時二進制編碼方式編碼、解碼操作簡單易行，交叉等遺傳操作便于實現，符合最小字符集編碼原則。