【導(dǎo)讀】外文資料翻譯。學(xué)生姓名：。學(xué)號(hào)：。所在學(xué)院：。專業(yè)：。指導(dǎo)教師：。2021年4月18日。2. AnjaliMahajan. Email:. MSAli. Badnera,Amravati,India. Email:. systems. I.INTRODUCTION. registers).3. searchfunction.

　　

【正文】 ithms, HEA is one of the most efficient algorithms with highly specialized, domain specific crossover and local search function. It outperforms the IRC algorithm with minimized spill costs. Being hybrid algorithm, it is not putationally expensive to obtain high quality solutions. The HEA can be easily parallelized, thus the puting time can be largely reduced. Population size of the problem should be set properly. Compared to the size of population, the length of iterations L of LS is more critical on the performance of the algorithm. In the future, we intend to test our HEA heuristic on graphs using coalescing and on chordal interference graphs generated from a large set of applications. HEA can also be applied to other piler optimization problems such as instruction scheduling and phase coupling of the piler. TABLE III RESULTS OF EXECUTION TIME 12 TABLE IV RESULT OF LOAD/ STORE GENERATED 13 基于嵌入式系統(tǒng)的寄存器分配的混合進(jìn)化算法的解決方案 綜合外電馬哈詹 G H Raisoni工程學(xué)院，印度那格浦爾， 電子郵件： M S阿里 教授拉姆 Meghe研究所的技術(shù)研究， Badnera，印度 Amravati 電子郵件： 摘要： 嵌入式系統(tǒng)有一個(gè)不斷增長(zhǎng)的需求，優(yōu)化編譯器， 用有限的通用寄存器設(shè)置 以生產(chǎn)高品質(zhì)的代碼 。 存儲(chǔ)器或寄存器，用于存儲(chǔ)一個(gè)程序的計(jì)算結(jié)果。相比內(nèi)存，訪問(wèn)寄存器的速度要快得多，但它們是稀缺資 源，可以非常有效地利用。優(yōu)化目標(biāo)是保持盡可能多 的 現(xiàn)場(chǎng)變量寄存器，以避免昂貴的內(nèi)存訪問(wèn)。我們提出了一個(gè)混合進(jìn)化算法對(duì)圖的著色寄存器分配的基礎(chǔ)上一個(gè)新的交叉運(yùn)營(yíng)商稱為無(wú)沖突集（ CCS）和一個(gè)新的本地搜索功能交叉的問(wèn)題。 索引條款編譯器，編譯器優(yōu)化，寄存器分配，混合進(jìn)化算法，嵌入式系統(tǒng) 寄存器分配的最重要的一個(gè)編譯器執(zhí)行的優(yōu)化和處理器速度，存儲(chǔ)器訪問(wèn)時(shí)間變寬之間的間隙變得越來(lái)越重要。它的目標(biāo)是找到一種方法來(lái)映射到物理內(nèi)存中的位置（不論是主存儲(chǔ)器或機(jī)器寄存器）在程序中使用的臨時(shí)變量。 訪問(wèn)寄存器的速度遠(yuǎn)遠(yuǎn) 超過(guò)訪問(wèn)內(nèi)存， 因此人們?cè)噲D盡可能使用寄存器。當(dāng)然，這并不總是可能的，從而必須 從內(nèi)存中 轉(zhuǎn)移一些變量（溢出）。這是有成本的，需成本的加載和存儲(chǔ)操作 應(yīng)盡可能地避免。通常情況下，這降低了運(yùn)行時(shí)的性能，并增加了功耗。因此，高效率的映射，一般應(yīng)盡量減少寄存器的要求和溢出指示的數(shù)目。關(guān)鍵應(yīng)用程序，尤其是在嵌入式計(jì)算機(jī)，工業(yè)編譯器都愿意接受較長(zhǎng)的編譯時(shí)間，如果最終的代碼得到改善。 這種方法試圖結(jié)合性能由特定域 architectureoptimizations 實(shí)現(xiàn)通用可編程處理器的靈活性。嵌入式處理器的編譯器必須應(yīng)對(duì)這些建筑 的優(yōu)化，并能夠 14 利用它們。 本文提出了一種啟發(fā)式算法對(duì)圖的著色寄存器分配問(wèn)題的基礎(chǔ)上一個(gè)新的交叉算子和一個(gè)新的本地搜索功能的嵌入式系統(tǒng)。 圖著色分配寄存器 是 抽象的問(wèn)題，程序問(wèn)題干擾圖中的節(jié)點(diǎn)指定顏色的生活范圍。寄存器分配程序試圖 讓 “彩色”的圖形與有限數(shù)量的機(jī)器寄存器 對(duì)應(yīng) ， 且與約束連接的任意兩個(gè)節(jié)點(diǎn)之間的干擾邊緣必須與不同的寄存器著色。 模型寄存器分配圖著色問(wèn)題，編譯器首先構(gòu)造一個(gè)干擾圖 G G 中對(duì)應(yīng)的節(jié)點(diǎn)的生活范圍，和邊緣的干擾。因此，在 G中有一條邊從節(jié)點(diǎn) i到節(jié)點(diǎn) j 的 i 的生存區(qū)間干擾活 j的范圍，也就是，如果他們 被同時(shí)住在一些點(diǎn)，不能占據(jù)相同的寄存器。 找到一個(gè)分配從 G，編譯器查找的 kG，即， k 種顏色分配到節(jié)點(diǎn) G 的相鄰節(jié)點(diǎn)總是有不同的顏色著色。如果我們選擇 k 機(jī)器寄存器的數(shù)量相匹配，那么，我們可以映射成一個(gè)可行的 kG 的著色寄存器分配底層代碼。由于圖著色是 NP完全的，編譯器采用了啟發(fā)式搜索著色的方法，它不能保證找到所有的 k染色圖的 k著色。如果沒(méi)有找到，一個(gè) k著色灑一些值，而不是在寄存器的值保存在內(nèi)存中。 溢出的一個(gè)或多個(gè)現(xiàn)場(chǎng)范圍內(nèi)創(chuàng)建了一個(gè)新的和不同的干擾圖。編譯器進(jìn)行反復(fù)溢出一些現(xiàn)場(chǎng)的范圍和嘗試顏色所產(chǎn)生的 新圖。在嵌入式處理器的上下文中，圖著色的方法的最重要的限制是，它是基于這樣的假設(shè)的均勻的寄存器集。由嵌入式處理器違規(guī) differentlyimpacted 寄存器分配的不同階段。 II. 相關(guān)工作 寄存器分配已經(jīng)在文獻(xiàn)中廣泛討論，已經(jīng)提出了許多方法。他們中的大多數(shù)都涉及到蔡廷 [6]的方法，但很少有解決問(wèn)題所提出的嵌入式處理器的架構(gòu)，如支持通過(guò)寄存器類不規(guī)則的寄存器和寄存器設(shè)置串聯(lián)。雖然文獻(xiàn) [13]提出了一種采用整數(shù)規(guī)劃支持不規(guī)則的寄存器組，這種方法需要注冊(cè)不等式約束建模，使其難以在工業(yè)編譯器實(shí)現(xiàn)。布里格斯 [3,4]提出了一種干涉圖中的寄存器對(duì)建模。他介紹了一個(gè)改進(jìn)的著色策略，產(chǎn)生更好的分配給許多圖形，蔡廷的方法失敗。不同之處在于在溢油決定的時(shí)機(jī)。喬治和蘋果 [11]提出迭代凝聚他們積極凝聚完全消除。 15 嵌入式處理器的特點(diǎn)往往是少量的寄存器。算法和啟發(fā)式已經(jīng)適應(yīng)在我們的基礎(chǔ)設(shè)施，以限制泄漏幾個(gè)寄存器時(shí)。樓盤。 [17]提出了一種泛化的程度 K測(cè)試，稱為 P, Q，檢驗(yàn)，處理不規(guī)則的寄存器設(shè)置和注冊(cè)類。 VPO[13]是一種便攜式優(yōu)化的 DSP，基于和風(fēng)重定向編譯基礎(chǔ)設(shè)施。 VPO解決這個(gè)問(wèn)題的異構(gòu)寄存器類別計(jì)算和沿 IR 樹(shù)傳播正確的減少寄存器類（注冊(cè)類產(chǎn)生交集的兩個(gè)指令的目標(biāo) /源操作數(shù)），允許寄存器進(jìn)行分配而不會(huì)插入額外的移動(dòng)操作。 PROPAN postpass 優(yōu)化 [14]依賴于整數(shù)線性規(guī)劃進(jìn)行寄存器分配和調(diào)度。 一些研究人員嘗試使用非圖形著色方法。 koes[15]提出了一種漸進(jìn)式的寄存器分配程序使用一個(gè)多商品 workflow 的模式 TP 代表不規(guī)則的硬件架構(gòu)的復(fù)雜性的。肖爾茨 [18]制定，寄存器分配分區(qū)布爾二次優(yōu)化問(wèn)題，允許處理器的通用建模特殊性。 Hirnschrott[11]采用分區(qū)布爾二次編程寄存器分配顯示 溢油成本和凝聚設(shè)置及效益更好的結(jié)果。馬哈詹 [16]提出一種新的混合進(jìn)化算法（ HGR）嵌入式系統(tǒng)作為一個(gè)高度專業(yè)化的，特定領(lǐng)域的交叉和本地搜索功能的最有效的算法對(duì)圖的著色寄存器分配問(wèn)題。 有許多局部搜索算法對(duì)圖的著色，如模擬退火 [7]，禁忌搜索 [10]等Galinier 和浩 [8]提出了一種基于混合進(jìn)化算法的算法。在此算法中的一個(gè)重要特點(diǎn)是一個(gè)專門的交叉，但對(duì) GA 的變異算子被替換為一個(gè) LS 運(yùn)算符。 III. 混合進(jìn)化算法 進(jìn)化算法涉及自然進(jìn)化和遺傳。遺傳算法是一種經(jīng)典方法，在這個(gè)類別。它已被應(yīng)用于各種優(yōu)化問(wèn)題。 還有其他一些方法，如遺傳規(guī)劃，蟻群優(yōu)化等簡(jiǎn)單的進(jìn)化算法效率不是一般的復(fù)雜的組合問(wèn)題。進(jìn)化算法的性能的提高與另外的問(wèn)題的具體知識(shí)。進(jìn)化算法相結(jié)合，與專業(yè)運(yùn)營(yíng)商來(lái)產(chǎn)生復(fù)雜的混合動(dòng)力系統(tǒng)稱為混合遺傳算法，混合進(jìn)化算法，遺傳局部搜索算法和模因算法。 方法組合優(yōu)化人口進(jìn)化算法的框架，導(dǎo)致混合進(jìn)化算法嵌入本地搜索。 HEA是基于兩個(gè)要素：一個(gè)高效的本地搜索（ LS）運(yùn)算符和一個(gè)高度專業(yè)化的交叉運(yùn)營(yíng)商。的基本思路包括使用交叉運(yùn)營(yíng)商創(chuàng)造新的和潛在的有趣的配置，然后由LS運(yùn)營(yíng)商改善。 我們提出了一個(gè)混合進(jìn)化算法對(duì)圖的著色寄存器 分配問(wèn)題，也是一個(gè)新的本地搜索功能的基礎(chǔ)上一個(gè)新的交叉算子。本節(jié)介紹我們的算法混合進(jìn)化算法圖著 16 色寄存器分配與建議運(yùn)營(yíng)商稱為無(wú)沖突集（ CCS）交叉。 A. 算法 HEA 由遺傳因素和本地搜索（ LS）。遺傳組成部分初始化和發(fā)展人口的解決方案。一般的算法，如下所示： Input : Interference graph , IG = ( V,E ) 。 number of registers , k Output : best configuration begin P = generate_population(|P|) iter = 0 while ( iter MaxIter or popudiversity0 ) do (p1, p2) = select_parents(P) p = crossover (p1, p2) p = local_search( p, L ) P = update_population(P,p) iter =iter + 1 endwhile end 該算法首先建立一個(gè)初始人口配置（ generate_population），然后執(zhí)行一系列稱為生成的周期。在每一代中， p1 和 p2 兩個(gè)配置選擇中的的人口（ select_parents）。一個(gè)交叉，然后用產(chǎn)生的后代 P 從 P1 和 P2（交叉）。 LS運(yùn)營(yíng)商適用，提高 p 為固定數(shù)目 L 的迭代（ local_search）。最后，改進(jìn)的配置p插入在人口，通過(guò)更換另一個(gè)配置（ update_population）。重復(fù)該過(guò)程直到迭代的值小于或等于一個(gè)前綴的數(shù)字 MAXITER 達(dá)到或種群的多樣性（群體多樣性）大于零。 計(jì)算種群多樣性之間 的平均距離在人群中的所有配置。對(duì)于兩種配置 p1 和p2， p1 和 p2 之間的距離是要變換 p1 的 p2 的初等變換的最小數(shù)目。 在我們的方法，我們認(rèn)為字符串表示的分區(qū)方法 [8]。每個(gè)解決方案 PI 分區(qū)變量到寄存器類， PI= {R1， R2， ...... RK}，其中每個(gè)類日包括被映射到的寄存器里，而 k 是寄存器的總數(shù)的變量的生存區(qū)間。鑒于兩位家長(zhǎng) P1 ={R11，R12， .... R1K}和 p2= {R21， R22， ...。 R2K}，部分配置將集合 {R1， R2， ...。 RK}的節(jié)點(diǎn)不相交的集合，其中每個(gè)子集包含在一個(gè)類中 的兩個(gè)親本之一，和所有 RI RI 是無(wú)沖突集。 （節(jié)點(diǎn) i 和 j干擾圖中被說(shuō)成是無(wú)沖突的時(shí)候，有沒(méi)有連接它們的邊緣） 17 B. 初始人口代 一般來(lái)說(shuō)使用的 DSatur 算法 [5]，它是一個(gè)曲線圖著色的啟發(fā)式生成初始種群。它認(rèn)為，它可以被定義為不同的顏色的數(shù)量，其中該節(jié)點(diǎn)是相鄰的每個(gè)節(jié)點(diǎn)上的飽和度。在寄存器分配的問(wèn)題，無(wú)論是泄漏的成本和被認(rèn)為是在一個(gè)給定的干擾圖的節(jié)點(diǎn)的程度。我們采用的新的指標(biāo)，稱為泄漏程度提出的 [17]，可用于排序節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)的泄漏程度，我可以由下面給出的三個(gè)方程之一定義 SDegree1(i) = SCost(i) x Degree(i) SDegree2(i) = SCost(i) x Degree2(i) SDegree3(i) = SCost(i) (1) 這些表達(dá)式， SCost 的（ i）為漏油成本和學(xué)位（ I）是節(jié)點(diǎn) i的邊數(shù)事件。為了生成初始種群，溢油度設(shè)置三個(gè)方程（ 1）結(jié)合使用。節(jié)點(diǎn)進(jìn)行排序在溢油度遞減順序。在每次迭代中，一個(gè)無(wú)符號(hào)映射寄存器類節(jié)點(diǎn)的最大的泄漏程度盡可能最低的指數(shù)值，其中選取的節(jié)點(diǎn)應(yīng)該是在同一類的其他節(jié)點(diǎn)沖突。重復(fù)這一過(guò)程，直到所 有的節(jié)點(diǎn)（即，其相應(yīng)的變量）被映射到了寄存器類別之一。 C. 交叉算 這里使用的是交叉無(wú)沖突集（ CCS）的新建議的操作交叉。鑒于兩個(gè)父配置P1 ={R11， R12， .... R1K}和 p2= {R21， R22， ...。 R2K}，隨機(jī)選擇由select_parents 運(yùn)營(yíng)商從人口，的算法交叉（ P1， P2）建立一個(gè)后代 P = {R1，R2， ...... RK}如下： Input: configurations p1= { R11 , R12 , …. R1k} and p2= { R21 , R22 , …. R2k} Output: configuration p= { R1 , R2 , …. Rk} begin // consider p1 if conflict(p1