幾種用于FPGA的新型有效混合布線算法.pdf

1、采用現(xiàn)場可編程門陣列(FPGA)可以快速實現(xiàn)數(shù)字電路，但是用于生成FPGA編程的比特流文件的CAD工具在編制大規(guī)模電路時常常需要數(shù)小時的時間，以至于許多設計者甚至通過在給定FPGA上采用更多的資源，或者以犧牲電路速度為代價來提高編制速度。電路編制過程中大部分時間花費在布線階段，因此有效的布線算法能極大地減少布線時間。 許多布線算法已經被開發(fā)并獲得應用，其中布爾可滿足性(SAT)布線算法及幾何查找布線算法是當前最為流行的兩種。然而

2、它們各有缺點：基于SAT的布線算法在可擴展性上有很大缺陷；幾何查找布線算法雖然具有廣泛的拆線重布線能力，但當實際問題具有嚴格的布線約束條件時，它在布線方案的收斂方面存在很大困難?；诖?，本文致力于探索一種能有效解決以上問題的新型算法，具體研究工作和結果可歸納如下。 1、在全面調查FPGA結構的最新研究動態(tài)的基礎上，確定了一種FPGA布線結構模型，即一個基于SRAM的對稱陣列(島狀)FPGA結構作為研究對象，該模型僅需3個適合的參

3、數(shù)即能表示布線結構。為使所有布線算法可在相同平臺上運行，選擇了美國北卡羅來納州微電子中心的20個大規(guī)模電路作為基準，并在布線前采用VPR399對每個電路都生成30個布局，從而使所有的布線算法都能夠直接在這些預制電路上運行。 2、詳細研究了四種幾何查找布線算法，即一種基本迷宮布線算法Lee，一種基于協(xié)商的性能驅動的布線算法PathFinder，一種快速的時延驅動的布線算法VPR430和一種協(xié)商A<'*>布線算法Frontier，并

4、且在相同的大規(guī)?；鶞孰娐飞蠈@四種算法進行評估。對比實驗表明：一方面，相比Lee，PathFinder的布線時間要少得多，且大大減少了布線時間的標準誤差；另一方面，相比PathFinder，VPR430及Frontier可分別減少59.7％及86.9％的布線時間，且在穩(wěn)定性上分別提高了41.0％及81.3％。從布線速度及穩(wěn)定性上看，四種算法的優(yōu)劣順序是：Frontier、VPR430、PathFinder、Lee。 3、研究了一

5、種通用的基于布爾的布線概念及把它用于FPGA詳細布線的方法。對兩種典型的基于SAT的詳細布線公式，即基于軌線公式(T-SDR)和基于路線公式(R-SDR)進行了分析對比。T-SDR具有同步嵌入網線、可布線性判定(或評估)及靈活的公式化能力的優(yōu)點；但是，對于一些大規(guī)?；鶞孰娐罚驗樵诓季€方案空間的可選擇性過大往往會造成布線時間過長。與T-SDR相比，R-SDR能夠有效地將排他性布線約束條件僅僅通過2-文字的CNF子句表示，產生更加緊致的S

6、AT實例，因而顯得更加有效。對比實驗的結果表明T-SDR的布線時間及布線時間標準誤差分別為R-SDR的31.4倍及36.8倍，因此R-SDR比T-SDR更加穩(wěn)定而有效。 4、將R-SDR與傳統(tǒng)幾何查找布線算法PathFinder、VPR430、Frontier進行了比較研究。實驗結果表明：R-SDR的布線時間及布線時間標準誤差分別為PathFinder的1.2倍及1.1倍。從布線速度及穩(wěn)定性上看，R-SDR次于幾何查找布線算法。

7、這一現(xiàn)象的主要原因是R-SDR是一種詳細布線算法，受由不考慮其特性的全局布線法提供的單一全局布線配置所約束。 5、提出了將基于布爾函數(shù)的布線法R-SDR與目前最高水平的常規(guī)FPGA布線算法PathFinder、VPR430及Frontier相結合的三種混合算法，即P-R-SDR、V-R-SDR和F-R-SDR?；旌纤惴ú粌H克服了基于布爾函數(shù)的FPGA布線算法的主要缺點，即可擴展性問題，而且補償了傳統(tǒng)布線法的典型缺陷，即布線順序依

8、賴性及不能證明不可布線性。 實驗結果表明，與單純的幾何查找布線法PathFinder、VPR430、Frontier相比，P-R-SDR、V-R-SDR、F-R-SDR分別節(jié)省了CPU時間32.0％、28.9％、25.0％，并在穩(wěn)定性上分別提高了24.1％、25.0％、29.1％。另外，還對P-R-SDR，V-R-SDR，F(xiàn)-R-SDR進行了相互比較，發(fā)現(xiàn)F-R-SDR、V-R-SDR、P-R-SDR的優(yōu)劣順序與Frontier

9、、VPR430、PathFinder相似。 6、針對SAT方法不支持局部方案的缺陷，給出了一種用于“子集可滿足性”的布爾SAT公式(sub-SAT)，即將一個具有N個變量的“嚴格”的SAT問題變換成一個新的“松弛”的SAT問題，僅當在原始問題中的變量有不超過k(k<