一種快速預判FPGA布線失敗的方法

向明艷 白利瓊 劉乙力 鞠瑜華

（成都華微電子科技有限公司 四川省成都市 610000）

隨著半導體工藝尺寸進入納米范疇，FPGA 器件的邏輯容量和復雜程度大幅度上升，對FPGA 電子設計自動化（Electronics Design Automation,簡稱EDA）軟件的要求也越來越高。在FPGAEDA 軟件中，將高層次的算法級行為描述編譯為用于配置FPGA 可編程開關狀態的編程下載文件需要經過綜合、映射、打包、布局、布線、位流生成和編程下載等過程。其中布線階段通常要占據整個流程的近30%的時間[3]，且布線資源占用了整個芯片50%～60%的信號延時[1]。因此布線速度的改進對于提高FPGA EDA 軟件的性能至關重要。

FPGA 布線是在布局的基礎上，按電路需求打通合適的可編程開關以連通邏輯單元塊的輸入和輸出引腳，使得最后的總線長盡可能地短，同時兼顧面積和時序。布線策略的選取很大程度上決定了布線結果。目前主流的布線算法主要是基于擁擠度協商的路徑搜索算法，該方法在解決擁塞問題的同時也能優化時序[2]，但該算法應用于千萬門級FPGA 電路時，隨著搜索空間的增大，布線所需時間也隨之增大。[3]中提出了一種偽布爾滿足性布線算法，該方法同時對所有的線網進行布線，可準確判斷線網可布通性，改進了傳統布爾可滿足性算法需要大量的變量和約束條件的問題，但偽布爾可滿足性在布線階段轉換成本過大，不適用于大規模布線基準。

本文提出了一種新穎的在布線之前預判布線失敗的方法，主要根據FPGA 中預先定制的布線資源，將互連端口間的連接關系用布線查找表表示，根據布線查找表中“1”的分布情況判定線網是否布線失敗，一旦預判該網表布線會失敗，就不再進行布線操作，從而節約布線時間。該方法操作簡單、計算量小、準確性高。目前未見類似方法的公開報道，該方法屬于首次提出。

1 FPGA互連模塊介紹

目前主流的SRAM 型FPGA 主要由可配置邏輯模塊（CLB,Configurable Logic Block）、可編程輸入/輸出單元（IOB,Input Output Block）、可編程互連資源等部分組成，也可通過嵌入DSP（Digital Signal Processor）、RAM(Random Access Memory)等異構單元來提高FPGA 的處理能力。

FPGA 中有著豐富的可編程互連資源，主要包括互連線和互連開關矩陣。CLB 與互連開關矩陣組成Tile 塊以陣列的形式有序地排列在FPGA 中，開關矩陣主要由傳輸管、多路選擇器和三態緩沖器等器件組成，用于實現相應的水平和垂直布線通道中互連線間的連接以及互連線與邏輯資源管腳間的連接。布線通道中存在多種互連線資源，其中全局時鐘連線資源為FPGA 中的邏輯單元塊傳送時鐘信號，普通可編程連線資源用于實現重復單元的連接，主要有單倍線、多倍線和長連線，多樣的連線資源可以實現不同跨度的連接，從而降低路徑的延時，提高電路的性能。

互連開關矩陣由不同長度的導線和多個布線開關組成。圖1 為簡化的互連開關矩陣內部結構，由2 個二輸入多路選擇器組成。其中I0 ～I3 為輸入端口，O0 ～O2 為輸出端口。

互連開關矩陣管腳間的簡化連接模型如圖2所示，其中CLB為邏輯模塊，INT 表示互連矩陣模塊，以最左邊的INT 所在位置為坐標原點可實現對各INT 的坐標編號。INT 中的I4、O3 端口為互連模塊與邏輯模塊相連的輸入輸出端口。通過對互連開關矩陣中多路選擇器的通斷可實現對不同邏輯資源間的連接，進而實現電路功能。

表1：開關矩陣內部連線關系

表2：開關矩陣間連線關系

圖1：互連開關矩陣內部結構

圖2：互連模塊之間管腳連接關系模型

2 布線查找表的構造

已知FPGA 中所有的布線資源都是預先定制的，也就是說FPGA 中互連開關矩陣間的連接情況和互連開關矩陣內部的走線是可以確定的。又因為FPGA 中的互連矩陣結構相同，故可以根據互連矩陣間的連接方式，內部結構的走線規律得到任意INT 的任意輸入端口可到達的所有INT 的輸出端口。由此可快速判斷給定線網從源端到漏端是否存在可連通的路徑。

令互連矩陣輸入端口為I={I0,I1,…,Ii,…,In}，輸出端口為O={O0,O1,…,Oj,…,Om}，其中n 為互連矩陣的輸入端口數，m 為互連矩陣的輸出端口數。根據圖1 可知n=3，m=2，可得到互連開關矩陣輸入端口Ii 可連接的所有輸出端口Oj。例如輸入端口I0 可到達的輸出端口為：O0，輸入端口I3 可到達的輸出端口為：O1、O2，具體對應關系如表1所示。

假設互連矩陣INT 的行數為R，列數為C，第p 行q 列的互連矩陣坐標為(p,q)，其中p=0,1,2,…,R，q=0,1,2,…,C。(p,q)_Oj 表示坐標為(p,q)的INT 的輸出端口Oj。根據圖2 可得到一個互連模塊的輸出端口到另一互連模塊的輸入端口的對應關系如表2所示。例如INT(0,0)的輸出端口O0 可到達INT(2,0)的I0 端口。

根據表1 和表2 遍歷INT，得到INT 的輸入端口通過跳轉能夠到達的所有INT 的輸出端口，從而構建布線查找表。假設當前INT的坐標為(p,q)，其當前輸入端口名為Ii，詳細步驟如下：

（1）根據表1 將與當前INT 的端口(p,q)_Ii 可達的輸出端口(p,q)_Oi 加入到臨時集合Temp 中；

（2）判斷Temp 是否為空，若是則退出循環；否則進入下一步；

（3）選取Temp 中第一個元素加入到集合O 中，并獲取相應的INT 坐標(p,q)和輸出端口Oi，通過表2 和表1 獲取通過端口Oi跳轉可達到的其它INT 的輸出端口集合，與集合O 去重后加入到Temp 中，刪除Temp[0]。跳轉到（2）。

由此可得到(p,q)_Ii 所能到達的所有輸出端口的集合O。得到所有輸入端口的可達輸出端口后，將所得的結果轉換為C*R*(n+1)行C*R*(m+1)列的布線查找表，初始化查找表為全0，遍歷集合O 設置相應位置為1。例如輸入端口為(p,q)_Ii，其可達輸出端口為(p’,q')_Oj，則設置布線查找表第(p*C+q)*N+i 行(p'*C+q')*M+j 列為1。表3 為最終的布線查找表。

該查找表能夠準確的表達INT 的輸入端口到達其他輸出端口是否存在相應的路徑。通過該查找表能夠快速準確預判一個線網是否布線失敗。根據布局結果獲得需要布線的線網Nt，t∈N*，針對任意布線需求Nt，有(x,y)_Ok →(x',y')_Ik'，表示坐標為(x,y)的功能模塊的輸出端口k 需要連接到坐標為(x',y')的功能模塊輸入端口k'。遍歷線網，參照布線查找表判斷是否存在線網布線失敗的情況。預判Nt是否存在布線通路的具體步驟如下：

（1）根據器件模型獲得(x,y)_Ok 對應的INT 端口(p,q)_Ii，同理獲得(x',y')_Ik'對應的INT 端口(p’,q' )_Oj；

（2）將查詢位置為(p,q)的INT 端口Ii 和位置為(p’,q')的INT 端口Oj 是否有路徑轉換為查詢布線查找表中第(p*C+q)*N+i行(p'*C+q')*M+j 列是否為1。若為1 則線網Nt中存在布線通路，否則布線失敗。

如果有一個線網Nt布線失敗，則預判整個布線過程無法完成，就不再進行布線操作，從而節約布線時間。

表3：布線查找表

3 結論

本文提出了在布線之前預判布線失敗的方法，主要根據FPGA中預先定制的布線資源，將互連端口間的連接關系用布線查找表表示。對布線需求的線網進行遍歷，得到源端和漏端，根據布線查找表中“1”的分布情況判定線網是否布線失敗。一旦預判該網表布線會失敗，就不再進行布線操作，從而節約布線時間。該方法操作簡單、計算量小、準確性高。此外，該方法對于布局和綜合階段也具有重要意義，可通過對擁擠度的情況改善布局結果，將時延的預估加入物理綜合。