惠 鋒，謝尚鑾

（無錫中微億芯有限公司，江蘇無錫 214072）

1 引言

布線是現(xiàn)場可編程門陣列（FPGA）編譯流程中的關(guān)鍵模塊，占用整個編譯工具大量的運行時間，且布線質(zhì)量直接影響芯片的最終性能。因此提升布線器性能、減少布線時間是FPGA 編譯流程中的關(guān)鍵問題[1]。

布線是在滿足用戶設(shè)計約束的前提下，利用器件布線資源連接布局后的邏輯單元。由于器件布線資源有限，擁塞在布線過程中不可避免。擁塞協(xié)商算法[2]的思想是引入對歷史成本的需求，通過迭代“拆線-重布”操作來協(xié)商解決布線擁塞問題。目前幾乎所有FPGA 廠商的布線器均以擁塞協(xié)商算法為基礎(chǔ)，擁塞協(xié)商算法在該領(lǐng)域占主導(dǎo)地位，學(xué)術(shù)界廣泛使用的FPGA 架構(gòu)設(shè)計和分析工具VPR 也是由此改進(jìn)而來。為了提升布線器性能，研究人員提出了諸多優(yōu)化策略。工業(yè)界主流廠商的優(yōu)化細(xì)節(jié)不公開，學(xué)術(shù)界則主要有并行計算[3-4]和宏模塊[5]等優(yōu)化策略。并行計算策略通過對線網(wǎng)的任務(wù)劃分與分配來實現(xiàn)算法的并行化，并采用互斥鎖的方式解決布線資源競爭問題。但隨著用戶設(shè)計規(guī)模變大，高扇出線網(wǎng)邊界會逐漸覆蓋整個芯片，算法效率變低。宏模塊策略通過將電路模塊封裝為宏單元進(jìn)行布線來減少時間開銷，由于宏單元內(nèi)部結(jié)構(gòu)在實際布線時無法更改，因此解的質(zhì)量不佳。文獻(xiàn)[6]針對復(fù)位信號等高扇出線網(wǎng)利用FPGA 專用時鐘資源進(jìn)行布線，有效避開與普通線網(wǎng)的資源競爭，達(dá)到提升布線效率的目的。

在沒有新算法引入或改進(jìn)算法存在缺陷的情況下，利用FPGA 結(jié)構(gòu)定制優(yōu)化策略也是一種提升編譯工具效率的方法。本文基于自主研發(fā)的FPGA 器件布線資源結(jié)構(gòu)，通過重構(gòu)布局網(wǎng)表執(zhí)行預(yù)布線，為布線算法提供優(yōu)質(zhì)的初始解，從而實現(xiàn)解的快速收斂，達(dá)到提升布線性能的目的。

2 FPGA 結(jié)構(gòu)

自主研發(fā)的FPGA 芯片簡化結(jié)構(gòu)如圖1 所示，其中主要包括可編程輸入輸出塊（IO）、可編程邏輯簇（CLC）、可編程互連資源和異構(gòu)集成的存儲器等硬件?？删幊袒ミB資源是FPGA 各模塊實現(xiàn)信號傳遞的橋梁，由開關(guān)盒（SWB）、連接盒（CB）和布線通道組成，其中SWB 位于水平布線通道和垂直布線通道的交匯處，實現(xiàn)布線方向和不同布線類型間的切換；CB 則分布于CLC 的四周，通過內(nèi)部開關(guān)或多路選擇器將CLC 的輸入和輸出連接到任意縱橫的布線通道上，每個CLC 與關(guān)聯(lián)的CB 與SWB 組成了一個邏輯塊。

圖1 FPGA 的簡化結(jié)構(gòu)

一個CLC 由2 個邏輯片（dice）組成，每個邏輯片中有4 個6 輸入查找表（LUT），其中每個LUT 輸入端口上的引腳邏輯等價，各引腳可以隨意交換與LUT 輸入端口的連接順序，而不影響電路邏輯功能，在交換后修正LUT 配置信息即可[7]，本文將該操作稱為引腳的重構(gòu)。為了提升布通率，在邏輯塊內(nèi)集成了SWB 到LUT 的48 組特定布線資源，邏輯片內(nèi)的連接關(guān)系見表1，其中IN0~IN47 為SWB 的輸出端口，并以字母A~D 與數(shù)字1~6 的組合區(qū)分dice 中不同LUT 的不同輸入端口。

表1 邏輯片內(nèi)的互連資源表

3 基于初始解優(yōu)化的FPGA 布線方法設(shè)計

本文提出一種有效的布線優(yōu)化策略，在加載網(wǎng)表文件后，根據(jù)邏輯片的特定布線結(jié)構(gòu)對邏輯單元引腳進(jìn)行重構(gòu)，進(jìn)而實現(xiàn)片內(nèi)布線資源的有序分配，為擁塞協(xié)商布線算法提供優(yōu)質(zhì)的初始解，提高其求解效率。

3.1 收益分析

在FPGA 設(shè)計流程中，裝箱通常使用聚類及最小割等算法[8-9]，將關(guān)聯(lián)度大的邏輯單元組裝到同一個CLC 中，以減少信號與外部的連接，縮小裝箱面積。

已知1 個源端為Q 的線網(wǎng)，其漏端數(shù)為2 且位于相同邏輯片中，位置分別為D1 與A4。布線器在布線資源充足時的最優(yōu)解是用布線開關(guān)M 引腳的過渡將A4 與Q 連通，最優(yōu)布線解見圖2，圖中SWB 內(nèi)部的虛線為布線開關(guān)，SWB 間的實線為布線通道，該結(jié)果產(chǎn)生4 個布線開關(guān)和1 條布線通道的開銷。

圖2 最優(yōu)布線解示意圖

然而在實際布線過程中擁塞問題是無法避免的，布線器通過懲罰沖突資源來增加其布通成本，協(xié)商解決擁塞問題，因此隨著布線資源競爭的加劇將導(dǎo)致較差的布線解，圖3 為其中的1 種情況，布線器需消耗4個SWB 開關(guān)和2 條布線通道資源才能將Q 與A4、D1連接，從而增加了布線擁塞發(fā)生的幾率，增大了布線資源的擴(kuò)展范圍和運行時間。

圖3 不佳布線解示意圖

若利用LUT 輸入端口各引腳的邏輯等價性，將D1 上的漏端引腳重構(gòu)至D2，這樣布線器只需2 個SWB 開關(guān)和1 條布線通道就可以將Q 與該漏端連通，與圖2 的結(jié)果相比可節(jié)省2 個SWB 開關(guān)，該解的示意圖見圖4。

圖4 優(yōu)化的布線解示意圖

基于上述分析，在布線前通過對線網(wǎng)邏輯單元引腳重構(gòu)可以實現(xiàn)布線資源的有序利用，有助于改善布線資源的競爭問題，減少布線擁塞數(shù)量。

3.2 初始解生成

對于任意兩個線網(wǎng)漏端，若其所對應(yīng)源端不同或?qū)?yīng)引腳邏輯等價，則稱其是互斥的。本研究遍歷布線網(wǎng)表，通過將其中每個CLC 內(nèi)的線網(wǎng)漏端基于互斥性高效分組并加以引腳重構(gòu)來獲得初始解，其示意圖見圖5，具體步驟為：

圖5 初始解生成示意圖

1)創(chuàng)建集合X，令變量i=0，獲取網(wǎng)表內(nèi)的k 個CLC{m0,m1,...,mk-1}；

2)對于mi，將其中邏輯單元引腳對應(yīng)的線網(wǎng)漏端均存入X，令變量j=0；

3) 若X 為空集，進(jìn)入步驟4；否則，創(chuàng)建漏端組Yj，依次讀取X 中保存的漏端s，若Yj為空或s 與Yj中的漏端均不互斥，將s 從X 中移出至Yj。當(dāng)前X 的遍歷結(jié)束后，令j=j+1，重復(fù)該步驟；

4)將mi內(nèi)的漏端劃分為j 組，將其按照內(nèi)部元素數(shù)量降序排序，重標(biāo)記為{Z0,Z1,...,Zj-1}，令變量h=0；

5)查找SWB 的空閑IN 端口（節(jié)點），確定與其連接的LUT 端口列表F，將Zh中的漏端從當(dāng)前連接的端口交換到F 中同一LUT 的端口，更新端口映射表。若h

6)若i

圖6 線網(wǎng)漏端處理

3.3 布線算法的改進(jìn)

為了提升布線效率，本研究對現(xiàn)有布線流程進(jìn)行改進(jìn)，在布線實現(xiàn)階段采用節(jié)點與漏端相結(jié)合的策略進(jìn)行布線，具體的改進(jìn)布線算法流程如圖7 所示，其中SLACK 為關(guān)鍵路徑時序裕量。首先在全局布線階段基于重構(gòu)后的初始解完成源端與節(jié)點之間的布線。然后在詳細(xì)布線階段，根據(jù)時序分析結(jié)果對擁塞線網(wǎng)的漏端逐一分析，組內(nèi)漏端時序違規(guī)處理見圖6（b），移出時序不合法的漏端進(jìn)行單獨布線，其余漏端仍以源端到節(jié)點的形式進(jìn)行拆線-重布，每個節(jié)點仍對應(yīng)1個漏端組，布通該線網(wǎng)后更新路徑上節(jié)點的當(dāng)前擁擠度；每次布線迭代完成后更新布線樹節(jié)點占用的歷史成本，并調(diào)用時序分析引擎更新漏端關(guān)鍵度，直到無布線資源被重用后算法結(jié)束[10]。

圖7 改進(jìn)布線算法流程

4 試驗結(jié)果與分析

本研究針對自主FPGA 芯片，提出初始解優(yōu)化策略以提升布線效率，并利用典型的布線測試?yán)M(jìn)行驗證。試驗在CPU 為3.4 GHz Intel core I7-6700、內(nèi)存為32 GB、操作系統(tǒng)為Windows 7 的PC 上進(jìn)行，采用經(jīng)典的擁塞協(xié)商布線算法進(jìn)行求解，記錄算法加入初始解優(yōu)化策略前后的運行數(shù)據(jù)，其結(jié)果如表2 所示，其中“全局沖突”為全局布線階段的沖突資源數(shù)量；“迭代”為詳細(xì)布線階段“拆線-重布”操作的迭代數(shù)，“詳細(xì)沖突”為迭代過程累計的沖突資源數(shù)量；“時間”為算法實現(xiàn)設(shè)計收斂所需的CPU 運行時間；“裕量”為關(guān)鍵路徑時序裕量；“平均值”為各測試?yán)辉囼瀰?shù)的平均值。

表2 試驗數(shù)據(jù)

本文通過重構(gòu)網(wǎng)表中的邏輯單元引腳來實現(xiàn)邏輯片內(nèi)布線資源的高效分配，得到布線擁擠度低的初始解，并采用節(jié)點與漏端相結(jié)合的布線策略快速實現(xiàn)了設(shè)計收斂。試驗數(shù)據(jù)表明，采用初始解后的布線算法與原始算法相比可在全局布線階段減少16.6%的沖突資源數(shù)，在詳細(xì)布線階段減少12.4%的迭代次數(shù)與9.8%的累計沖突資源數(shù)。布線問題是一個復(fù)雜的非確定性多項式難題，布線擁塞數(shù)量直接影響算法的求解時間，因此本文也實現(xiàn)了7.8%的CPU 運行時間優(yōu)化，17.2%的關(guān)鍵路徑時序裕量優(yōu)化。

5 結(jié)論

本文通過邏輯片內(nèi)高效預(yù)布線為擁塞協(xié)商布線算法提供了布線擁擠度低的初始解，并在布線過程中采用節(jié)點與漏端相結(jié)合的布線策略來提升布線效率。試驗數(shù)據(jù)表明所提方法可有效改善布線資源競爭現(xiàn)象，加速算法收斂，并實現(xiàn)關(guān)鍵路徑時序裕量優(yōu)化。由于裝箱與布局的結(jié)果都將影響布線器的質(zhì)量，因此后續(xù)研究的方向是為自主研發(fā)的FPGA 器件結(jié)構(gòu)提供一個有效的擁塞預(yù)測模型來指導(dǎo)裝箱和布局算法的求解，為布線器提供更優(yōu)質(zhì)的輸入，同時也能為FPGA器件結(jié)構(gòu)的優(yōu)化提供設(shè)計參考。