偽布爾可滿足性算法及其在FPGA布線中的研究應(yīng)用.pdf

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

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

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

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

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

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

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

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

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