[發明專利]基于振蕩器相位同步的嵌入式系統寄存器分配方法

無效

• 申請號: 201210334909.1
• 申請日: 2012-09-11
• 公開（公告）號: CN102902570A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 吳建設;侯霄茹;焦李成;尚榮華;戚玉濤;吳家驥;韓紅;白靜;王達
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于計算機技術領域，特別是編譯過程對中間變量的寄存器分配，可用于嵌入式系統。

背景技術

隨著信息網絡技術的發展，以計算機技術為基礎的嵌入式系統對性能、實時性和可靠性的要求越來越高。在嵌入式系統中，編譯器直接影響系統性能，而寄存器分配又對編譯器生成的代碼質量有著重要影響。因此從寄存器分配角度出發優化編譯器的技術可有效提高嵌入式系統中程序的執行效率。相對于存儲器，寄存器操作速度快但數量有限，需要盡可能的高效使用。因此寄存器分配問題就是決定如何優化使用嵌入式系統中的寄存器，盡量減少對嵌入式系統中存儲器的操作。具體地說就是在程序編譯過程中將產生的中間變量盡可能多的保存在寄存器中，減少被迫溢出到存儲器的中間變量個數，降低溢出代價。

現有的嵌入式系統寄存器分配方法主要是基于圖論的方法，將寄存器分配問題轉換成圖著色模型，然后利用解決圖著色問題的算法獲得寄存器分配的結果。較早的基于圖著色模型的啟發式算法OCH，設計簡單，用時很少，但分配效果差。后來的混合進化算法HEA，對種群初始化后，通過免沖突交叉算子CFPX盡量使每個寄存器中的變量不沖突，然后通過局部搜索LSP調整個體中的中間變量從而減少中間變量的溢出個數，降低寄存器的溢出代價。這種方法雖然能夠得到較好的寄存器分配結果，但是需要大量的時間。

發明內容

本發明的目的在于針對上述已有技術的不足，提出一種基于振蕩器相位同步的嵌入式系統寄存器分配方法，以減少寄存器分配時間，從而提高嵌入式系統程序的執行效率。

為了實現上述目的，本發明的技術方案包括如下步驟：

(1)將嵌入式系統編譯中的中間變量用節點表示，連接相互干擾的中間變量所對應的節點，得到干擾圖H；

(2)保持干擾圖H中的節點不變，去掉干擾圖H中相連節點間的邊，連接干擾圖H中未連接的節點，得到干擾圖H的補圖G，生成補圖G的鄰接矩陣A={a_xy}，x=1,2,...N，y=1,2,...N，其中N為補圖G的節點數目；

(3)用振蕩器對應補圖G中的節點，分別記為1,2,...,N，在[0,2π]中隨機產生N個振蕩器初始相位，在[-0.1,0.1]隨機產生N個振蕩器初始頻率，根據以下公式計算振蕩器的相位變化值：