1、現(xiàn)場可編程門陣列(FPGA)主要包括可配置邏輯模塊和布線模塊,它支持可編程重復配置,具有靈活、風險低、開發(fā)周期短等優(yōu)勢,在通信、工業(yè)控制、汽車電子、數(shù)據(jù)處理、消費電子等領域得到了廣泛應用。隨著FPGA內(nèi)部可配置資源容量的增加,對應的計算機輔助設計(CAD)工具也需要升級和優(yōu)化。隨著設計復雜程度的提高,將一個設計配置到FPGA上往往需要CAD工具計算很長時間方可滿足各種參數(shù)要求。而布線階段通常需要消耗整個CAD流程近30％的時間,因此,高

2、效的布線算法對縮短整個FPGA開發(fā)的時間至關(guān)重要。
　　 目前已開發(fā)多種布線算法并獲得應用,其中布爾可滿足性(SAT)布線算法及幾何查找布線算法是當前最為流行的兩種。兩者各有優(yōu)缺點?；趲缀尾檎业牟季€算法由基本迷宮(Maze)算法演化而來,它雖然可經(jīng)過優(yōu)化來提高布線速度,但由于一次只能布一根線,其可布通性較難確定,通常依靠設定運行時間的上限來實現(xiàn)算法終止。另外,其它由迷宮算法優(yōu)化演化而來的各種幾何查找算法也均存在依賴布線順序的缺

3、點。相比之下,基于SAT的算法由于可同時給所有線網(wǎng)布線,因此能從理論上證明可布通性。但是,這種算法需要大量的變量和約束條件,所以可擴展性并不好。
　　 最近,一種基于偽布爾可滿足性(PBS)的布線算法成為FPGA布線算法的研究熱點。和一般基于SAT的算法類似,PBS算法可同時給所有線網(wǎng)進行布線,因此也能準確判斷可布通性。和SAT算法不同的是,它將約束條件用精簡的表達式表示,需要的布線變量和公式大大減少,因此顯著降低了內(nèi)存需求,提

4、高了擴展性。但是,偽布爾可滿足性算法在布線過程中所需的轉(zhuǎn)換成本過大,不適用于大型布線基準。本文探索一種能有效解決以上問題的新型算法,具體研究工作和結(jié)果如下:
　　 (1)在全面調(diào)查FPGA結(jié)構(gòu)最新研究動態(tài)的基礎上,給出了一種FPGA布線結(jié)構(gòu)模型,即基于SRAM的對稱陣列(島狀)FPGA結(jié)構(gòu),僅需3個適合的參數(shù)即能表示布線結(jié)構(gòu)。詳細研究了布爾可滿足性算法、偽布爾可滿足性算法和兩種幾何查找布線算法,即一種基于協(xié)商性能驅(qū)動的布線算法P

5、athFinder和一種協(xié)商A幸布線算法Frontier。選取全局布線實例和Max-SAT布線基準的大規(guī)?；鶞孰娐?對Frontier、SAT和PBS進行了分析比較。結(jié)果表明,利用偽布爾約束編碼比用純粹的合取范式(CNF)顯示出更好的緊密性、更短的運行時間,且編碼更簡潔緊湊。針對偽布爾可滿足性問題擴展開發(fā)的解法器PBS,與以前所報道的兩種方法相比較--早期的幾何查找算法和現(xiàn)在用于純CNF約束的解法器Chaff,從而驗證了偽布爾可滿足性所

6、需存儲空間更小,并能有效加速求解的特性。
　　 (2)近年來0-1整數(shù)線性規(guī)劃(Integer Linear Programming,ILP)的發(fā)展進一步擴展了優(yōu)化線性目標函數(shù),這通常是通過解決一系列的SKT或者ILP決策問題來實現(xiàn)的。但是目標函數(shù)可能會使采用對稱的約束變得復雜化,即使目標函數(shù)的約束不可滿足,并且與目標函數(shù)不相關(guān)。本文在對稱破缺技術(shù)的基礎上,開發(fā)了一種自適應流程,結(jié)合靜態(tài)對稱破缺技術(shù)和動態(tài)對稱破缺技術(shù),可以分析一

7、個給定的布爾優(yōu)化問題,并能挑選最合適的對稱破缺技術(shù)。實驗結(jié)果證明,當這種技術(shù)用于布線時,比純粹的靜態(tài)對稱破缺或動態(tài)對稱破缺加速了問題的解決。
　　 (3)為了改善偽布爾可滿足性算法在布線過程中增加轉(zhuǎn)換成本的負面影響,提出了一種用于FPGA的新的布線算法,綜合了偽布爾可滿足性算法與幾何布線算法的優(yōu)點。在布線過程中,先選用Frontier或PathFinder這類幾何布線算法對FPGA進行布線,如果不能成功再采用偽布爾可滿足性算法。

8、并在布線流程中增加了靜態(tài)對稱破缺技術(shù)對偽布爾約束進行預處理,偵測并破缺其中的對稱,減少搜索路徑,從而減少成本。實驗結(jié)果表明,這種混合布線方法可以顯著減少運行時間,加速求解過程。
　　 (4)研究了用子集可滿足性(sub-SAT)算法求解FPGA詳細布線的問題。在布線資源固定的FPGA布線環(huán)境中,布爾公式可以證明所給電路的不可布通性,優(yōu)于典型的one-nebat-a-time方法。子集可滿足性方法把一個有N個約束的“嚴格的”SAT

9、問題轉(zhuǎn)換成一個新的“松弛的”SAT問題,僅當在原始問題中變量的不可滿足個數(shù)不超過閾值k(k<