[發明專利]一種用于集成電路布局的加速型模擬退火方法

在審

• 申請號: 201310645831.X
• 申請日: 2013-12-03
• 公開（公告）號: CN104679931A
• 公開（公告）日: 2015-06-03
• 發明（設計）人: 楊海鋼;黃俊英;林郁;崔秀海;羅楊;王飛
• 申請（專利權）人: 中國科學院電子學研究所
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 宋焰琴

技術領域

本發明涉及優化現場可編程邏輯芯片(FPGA)的布局，減小布局時間，同時將電路的布線長度和頻率保持在規定的范圍內。

背景技術

(1)隨著集成電路工藝節點的不斷縮小，現代現場可編程邏輯芯片(Field?Programmable?Gate?Array-FPGA)包含的查找表模塊(Look?Up?Table-LUT)數目已經達到百萬量級，同時還嵌入了很多硬模塊，如數字信號處理模塊(Digital?Signal?Process-DSP)、隨機存儲模塊(RandomAccess?Memory-RAM)等。由于異質FPGA復雜性的增加，計算機輔助設計(CAD)工具的編譯時間越來越長，而在FPGA的整個編譯流中，布局是最耗時的步驟之一，其負面效應是數字電路設計者設計時間的延長，增加了電路的設計成本。

(2)FPGA的布局是個非確定性多項式時間完全(Nondeterministic?Polynomial?Time?Complete-NPC)問題，即不能在確定性的多項式時間內找到最優的布局，因此大量的啟發式的方法被用于求解這一問題，其中最常用的是模擬退火(SA)方法。它得到了學術界和工業界的廣泛研究和應用。模擬退火方法是迭代改進算法，它通過對已經存在的解進行局部的改變(通過交換電路模塊實現)產生一個新解，然后用成本函數評估新解是否被接受。如果新解的成本函數值比舊解小，那么就接受這個新解，否則就以一定的概率接受新解。為了加速解的收斂，在模擬退火方法中引入交換窗口的概念是一種有效的措施，可以減小算法的運行時間。

(3)改進模擬退火算法運行時間的策略主要有五種：采用好的初始布局、定向移動電路模塊、改變模擬退火表、智能搜索解空間、動態調整交換窗口。以寬度優先的方式遞歸地進行二劃分可以得到更好的初始布局，使得退火只需要在低溫區域進行，從而減小布局時間。定向移動電路模塊的策略是指智能地選擇和放置電路模塊，而不是傳統模擬退火算法中的隨機選擇和放置，加快了算法的收斂。由熱力學組合優化方法得到的高效模擬退火表可以在更短的時間內得到與傳統退火表相當的布局質量。智能搜索解空間的策略是指通過對解空間進行分析，跳過局部最小解，而且以不同的概率選擇不同的移動類型。動態調整交換窗口的方法是最新提出的一種加速低溫模擬退火的技術。傳統的模擬退火算法的交換窗口僅僅是由溫度間接決定的，而在這種方法中交換窗口的大小還與每次移動產生的隨機數有關。把這種方法應用在低溫模擬退火中可以減少無效移動(即對最終的布局結果沒有貢獻的移動)的次數，從而減小布局時間。

(4)考慮模擬退火算法的加速方法是目前工程應用的必然選擇。但是，由于在減小算法運行時間的同時，電路的面積和頻率都會受到影響，這樣使得對算法的各個參數進行優化設計顯得至關重要。

(5)為了適應模擬退火算法本身的隨機性，尋求如何用最小代價(即最短的線長和最高的電路頻率)減小算法的運行時間，并使得線長和頻率滿足要求顯得尤其重要。

現有技術的動態調整交換窗口的方法最主要的技術缺陷是：動態調整交換窗口的方法用在解析布局的全局布局和詳細布局兩個階段之間的，相當于只用在低溫模擬退火中，因為全局布局階段所做的工作相當于高溫模擬退火。因此，這種方法不能直接用在從高溫到低溫的整個模擬退火過程中。

發明內容

(一)要解決的技術問題

為了克服現有技術的缺陷，本發明技術方案模擬退火算法被廣泛用于解決FPGA的布局問題，但是隨著FPGA芯片容量的增加，算法的運行時間變得不能接受；為此，本發明的目的是提出一種模擬退火算法的加速方法，并將其用于FPGA的布局，減小布局時間，同時將電路的布線長度和頻率保持在規定的范圍內。

(二)技術方案

為實現上述目的，本發明一種用于集成電路布局的加速型模擬退火方法所采用的技術方案包括：改變集成電路所包含的電路模塊的動態交換窗口尺寸大小；由上一溫度下的交換成功率以及確定某一交換是否接受的一個隨機數決定動態交換窗口大小，使得每個交換的動態交換窗口大小隨隨機數動態地變化；對退火的高溫和低溫階段采用不同的動態交換窗口調整策略，從而對電路模塊的布局實現從高溫到低溫的整個模擬退火。

(三)本發明的有益效果