基于初始解優(yōu)化的FPGA 布線方法

惠 鋒，謝尚鑾

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

1 引言

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

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

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

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

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

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

一個(gè)CLC 由2 個(gè)邏輯片（dice）組成，每個(gè)邏輯片中有4 個(gè)6 輸入查找表（LUT），其中每個(gè)LUT 輸入端口上的引腳邏輯等價(jià)，各引腳可以隨意交換與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è)計(jì)

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

3.1 收益分析

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

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

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

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

圖3 不佳布線解示意圖

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

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

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

3.2 初始解生成

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

圖5 初始解生成示意圖

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

2)對(duì)于mi，將其中邏輯單元引腳對(duì)應(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)部元素?cái)?shù)量降序排序，重標(biāo)記為{Z0,Z1,...,Zj-1}，令變量h=0；

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

6)若i

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

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

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

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

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

本研究針對(duì)自主FPGA 芯片，提出初始解優(yōu)化策略以提升布線效率，并利用典型的布線測(cè)試?yán)M(jìn)行驗(yàn)證。試驗(yà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)化策略前后的運(yùn)行數(shù)據(jù)，其結(jié)果如表2 所示，其中“全局沖突”為全局布線階段的沖突資源數(shù)量；“迭代”為詳細(xì)布線階段“拆線-重布”操作的迭代數(shù)，“詳細(xì)沖突”為迭代過程累計(jì)的沖突資源數(shù)量；“時(shí)間”為算法實(shí)現(xiàn)設(shè)計(jì)收斂所需的CPU 運(yùn)行時(shí)間；“裕量”為關(guān)鍵路徑時(shí)序裕量；“平均值”為各測(cè)試?yán)辉囼?yàn)參數(shù)的平均值。

表2 試驗(yàn)數(shù)據(jù)

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

5 結(jié)論

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