用于FPGA的新型混合布線算法的研究.pdf

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

2、。布線階段通常消耗整個CAD流程近30%的時間，因此，高效的布線算法對縮減整個FPGA開發(fā)流程的時耗和滿足各種約束條件至關(guān)重要。
　　 當(dāng)今廣泛采用的FPGA布線算法主要包括基于幾何查找的布線算法和基于布爾可滿足性(SAT)的布線算法；兩者各有優(yōu)缺點(diǎn)?；趲缀尾檎业牟季€算法均由基本迷宮(Maze)算法演化而來，它雖然可經(jīng)過優(yōu)化提高布線速度，但由于一次只能布一根線，可布線性較難確定，通常依靠設(shè)定運(yùn)行時間上限來實(shí)現(xiàn)算法終止。另外，其

3、它由迷宮算法優(yōu)化而來的各種幾何查找算法也均存在依賴布線順序的缺點(diǎn)。相比之下，基于SAT的算法由于可同時給所有線網(wǎng)布線，因此能從理論上證明可布線性。但是，這種算法需要大量變量和約束條件公式，所以可擴(kuò)展性并不好。
　　 最近，一種基于偽布爾可滿足性(PB-SAT)的布線算法成為FPGA布線算法的研究熱點(diǎn)。和布爾SAT算法類似，PB-SAT算法可同時給所有線網(wǎng)進(jìn)行布線，因此也能準(zhǔn)確判斷可布線性。和布爾SAT算法不同的是，它將約束條件用

4、精簡的表達(dá)式予以表示，需要的布線變量和式子大大減少，因此顯著降低了內(nèi)存需求，提高了擴(kuò)展性。但是，PB-SAT算法在布線速度上仍然慢于傳統(tǒng)的幾何查找算法。為了吸收幾何布線算法和偽布爾布線算法的優(yōu)點(diǎn)，本文又提出了一種新型的混合算法(P-PB-SAT)。下面歸納本文的主要研究工作和結(jié)論。
　　 ·介紹了FPGA的特點(diǎn)，并與專用集成電路(ASIC)進(jìn)行了比較；分析了常見的FPGA編程工藝、架構(gòu)及特點(diǎn)；在此基礎(chǔ)上確定了采用Xilinx的島

5、狀FPGA架構(gòu)作為研究的布線對象。
　　 ·詳細(xì)介紹和比較了三種幾何算法，即Lee迷宮算法、A*算法和基于協(xié)商的性能驅(qū)動的布線算法Pathfinder；分析了兩種基于布爾SAT的詳細(xì)布線算法，即基于軌線的詳細(xì)布線SAT算法(T-SDR)和基于路線的詳細(xì)布線SAT算法(R-SDR)。實(shí)驗(yàn)結(jié)果表明，在總布線時間和穩(wěn)定性方面上R-SDR略弱于Pathfinder，分別為Patfinder的117.9%、0.901倍。然而在不可布線的電

6、路布局基準(zhǔn)上，R-SDR能夠準(zhǔn)確判定可布線性，而Pathfinder則不能。
　　 ·研究了最新的PB-SAT布線算法，并在約束表示方面和布爾SAT算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，PB-SAT算法在布線時間和穩(wěn)定性方面的表現(xiàn)處于R-SDR和Pathfinder之間:PB-SAT算法在總時間上分別是R-SDR的89.5%和Pathfinder的105.5%；在總體穩(wěn)定性方面，PB-SAT分別為R-SDR的1.042倍和Pathfin

7、der的0.939倍；PB-SAT判定不可布線的總時間為R-SDR的91.9%。
　　 ·最后，基于PB-SAT和幾何算法的結(jié)合，提出了P-PB-SAT新型混合算法。實(shí)驗(yàn)結(jié)果表明，P-PB-SAT算法在時間和穩(wěn)定性上都優(yōu)于Pathfinder、R-SDR、PB-SAT。在總布線時間上，P-PB-SAT分別為Pathfinder、R-SDR和PB-SAT的55.3%、47.4%、52.5%；在穩(wěn)定性方面，分別為三者的1.65、1.