一種快速預(yù)判FPGA布線失敗的方法

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

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

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

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

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

1 FPGA互連模塊介紹

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

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

互連開關(guān)矩陣由不同長度的導(dǎo)線和多個布線開關(guān)組成。圖1 為簡化的互連開關(guān)矩陣內(nèi)部結(jié)構(gòu)，由2 個二輸入多路選擇器組成。其中I0 ～I(xiàn)3 為輸入端口，O0 ～O2 為輸出端口。

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

表1：開關(guān)矩陣內(nèi)部連線關(guān)系

表2：開關(guān)矩陣間連線關(guān)系

圖1：互連開關(guān)矩陣內(nèi)部結(jié)構(gòu)

圖2：互連模塊之間管腳連接關(guān)系模型

2 布線查找表的構(gòu)造

已知FPGA 中所有的布線資源都是預(yù)先定制的，也就是說FPGA 中互連開關(guān)矩陣間的連接情況和互連開關(guān)矩陣內(nèi)部的走線是可以確定的。又因為FPGA 中的互連矩陣結(jié)構(gòu)相同，故可以根據(jù)互連矩陣間的連接方式，內(nèi)部結(jié)構(gòu)的走線規(guī)律得到任意INT 的任意輸入端口可到達(dá)的所有INT 的輸出端口。由此可快速判斷給定線網(wǎng)從源端到漏端是否存在可連通的路徑。

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

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

根據(jù)表1 和表2 遍歷INT，得到INT 的輸入端口通過跳轉(zhuǎn)能夠到達(dá)的所有INT 的輸出端口，從而構(gòu)建布線查找表。假設(shè)當(dāng)前INT的坐標(biāo)為(p,q)，其當(dāng)前輸入端口名為Ii，詳細(xì)步驟如下：

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

（2）判斷Temp 是否為空，若是則退出循環(huán)；否則進(jìn)入下一步；

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

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

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

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

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

如果有一個線網(wǎng)Nt布線失敗，則預(yù)判整個布線過程無法完成，就不再進(jìn)行布線操作，從而節(jié)約布線時間。

表3：布線查找表

3 結(jié)論

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