劉耿耿 許文霖 周茹平 徐 寧

①(福州大學(xué)計算機(jī)與大數(shù)據(jù)學(xué)院 福州 350116)

②(福建省網(wǎng)絡(luò)計算與智能信息處理重點實驗室 福州 350116)

③(武漢理工大學(xué)信息工程學(xué)院 武漢 430070)

1 引言

近年來，現(xiàn)場可編程門陣列(Field Programmable Gate Array, FPGA)廣泛應(yīng)用于各個領(lǐng)域，如深度學(xué)習(xí)[1]、云計算[2]和芯片設(shè)計的驗證問題[3]。復(fù)雜的專用集成電路(Application Specific Integrated Circuit, ASIC)芯片設(shè)計需要通過多種驗證方法保證設(shè)計的正確性。驗證的主要方法有軟件仿真、形式化驗證和硬件仿真。隨著芯片設(shè)計越來越復(fù)雜，軟件仿真需要花費大量的運(yùn)行時間仿真每個邏輯電路，形式化驗證難以適用于大型ASIC設(shè)計的驗證問題，同時傳統(tǒng)的硬件仿真方法需要花費大量的成本來實現(xiàn)驗證。而基于FPGA原型驗證的硬件仿真方法可以解決大型ASIC設(shè)計的驗證問題，并且能夠在成本和運(yùn)行時間之間做到平衡。因此，許多先進(jìn)的微處理器制造商在其驗證過程中使用了基于FPGA原型驗證的硬件仿真方法。

ASIC設(shè)計隨著規(guī)模的不斷擴(kuò)大，越來越難在單個FPGA上實現(xiàn)邏輯驗證[4,5]。因此，大型的ASIC設(shè)計將根據(jù)設(shè)計需求被劃分到多個FPGA內(nèi)。與單FPGA系統(tǒng)相比，多FPGA系統(tǒng)邏輯復(fù)雜性更高，設(shè)計能力更強(qiáng)。高速收發(fā)器被運(yùn)用于FPGA系統(tǒng)中，可以提高FPGA間的數(shù)據(jù)交換速度。隨著FPGA內(nèi)部構(gòu)造越發(fā)復(fù)雜，F(xiàn)PGA間信號數(shù)量會遠(yuǎn)遠(yuǎn)超過I/O引腳數(shù)量。而時分復(fù)用(Time-Division Multiplexing, TDM)技術(shù)被廣泛運(yùn)用于解決I/O引腳數(shù)量不足的問題。然而，TDM技術(shù)會造成FPGA間的信號延遲，導(dǎo)致系統(tǒng)時延的增加。因此，減少TDM技術(shù)所導(dǎo)致的系統(tǒng)時延是十分重要的問題。

時分復(fù)用比率是用來衡量系統(tǒng)時鐘周期使用情況的數(shù)值。在多FPGA原型系統(tǒng)的設(shè)計流程中，TDM比率通常是在FPGA布線后確定的。文獻(xiàn)[6]提出了同時進(jìn)行信號分割和分組的方法，可以優(yōu)化分區(qū)和TDM比率。為了解決FPGA間的布線問題，文獻(xiàn)[7]和文獻(xiàn)[8]使用Pathfinder迭代地優(yōu)化FPGA間的布線問題。然而，這兩類工作都未考慮線網(wǎng)組的概念。文獻(xiàn)[9]通過減少線長優(yōu)化FPGA間的布線結(jié)果。然而，多FPGA系統(tǒng)的優(yōu)化目標(biāo)不僅僅是線長，TDM的比率分配也非常重要，因為系統(tǒng)性能很大程度上受到FPGA間線網(wǎng)的延遲影響。為了優(yōu)化TDM比率，文獻(xiàn)[10]提出了一種基于整數(shù)線性規(guī)劃(Integer Linear Programming, ILP)的優(yōu)化算法，但I(xiàn)LP只適合解決較小尺寸的問題。此外，以往工作中的TDM比率通常是任意整數(shù)，并不符合實際情況。

根據(jù)實際應(yīng)用中的設(shè)計，本文提出一種用于時分復(fù)用技術(shù)的多階段協(xié)同優(yōu)化FPGA布線(Multi-Stage Co-optimization FPGA Routing, MSCOFRouting)方法，旨在滿足TDM比率約束的前提下，布線拓?fù)渖呻A段、TDM比率分配階段和TDM比率優(yōu)化階段3個階段協(xié)同優(yōu)化FPGA間的可布線性和TDM比率。本文的主要貢獻(xiàn)如下：

(1) 提出一種自適應(yīng)布線算法，以避免布線擁塞，解決FPGA間布線優(yōu)化問題，有力減少系統(tǒng)時延。

(2) 提出一種基于拉格朗日松弛(Lagrangian Relaxation, LR)的TDM比率分配算法，使小規(guī)模線網(wǎng)組獲得較大TDM比率，大規(guī)模線網(wǎng)組獲得較小TDM比率，有效解決TDM比率分配問題。

(3) 提出了一種TDM比率優(yōu)化算法，縮減線網(wǎng)組和FPGA連接對的TDM比率。

(4) 將多線程并行化方法運(yùn)用到上述3個算法，進(jìn)一步提高M(jìn)SCOFRouter的運(yùn)行效率。

(5) 實驗結(jié)果表明，本文算法不僅能滿足TDM約束條件，而且可以獲得比同類工作更好的解決方案。

后文組織如下：第2節(jié)介紹了時分復(fù)用技術(shù)和問題模型；第3節(jié)闡述了MSCOFRouting的整體框架。第4節(jié)給出本文相關(guān)策略的有效性驗證及實驗結(jié)果的比較分析。第5節(jié)總結(jié)全文。

2 問題模型

2.1 時分復(fù)用技術(shù)

使用時分復(fù)用技術(shù)可以有效地解決I/O引腳數(shù)量不足的問題，使得多個信號可以在不同時間段共用一個I/O引腳。然而，使用時分復(fù)用技術(shù)會造成系統(tǒng)時延的增加。TDM比率是用來衡量系統(tǒng)時鐘周期使用情況的數(shù)值，可以作為衡量系統(tǒng)時延的指標(biāo)。系統(tǒng)時延與TDM比率呈單調(diào)遞增關(guān)系。因此，通過降低TDM比率可以有效減少系統(tǒng)時延。FPGA連接對p上邊e的時分復(fù)用比率如式(1)所示。

其中，DN(p), Cap(p)和TR(e)分別代表通過FPGA連接對p的信號數(shù)、FPGA連接對p的容量和邊e的TDM比率。由于一個FPGA連接對間只有一根物理導(dǎo)線，所以FPGA連接對的容量固定為1。

圖1是時分復(fù)用技術(shù)的示意圖。圖中的長方形、正方形和圓形分別表示轉(zhuǎn)換器、實例和分區(qū)。紅色箭頭、藍(lán)色箭頭和綠色箭頭分別表示3種不同的信號，兩個FPGA中間的黑色箭頭表示兩個FPGA之間唯一的物理導(dǎo)線。在未使用時分復(fù)用技術(shù)的情況下，一個系統(tǒng)時鐘周期內(nèi)，一條物理導(dǎo)線只能傳輸一種信號。這會導(dǎo)致FPGA系統(tǒng)運(yùn)行效率的下降。為了提升FPGA系統(tǒng)的運(yùn)行效率，時分復(fù)用技術(shù)被運(yùn)用在FPGA系統(tǒng)中，使得在一個系統(tǒng)時鐘周期內(nèi)可以傳輸3種不同的信號。

2.2 FPGA間的布線問題

2019年ICCAD比賽[11,12]提出的FPGA間布線問題將FPGA系統(tǒng)中的FPGA抽象為節(jié)點，忽略了一些FPGA的特殊性，著重解決FPGA間的布線問題。本文常用的符號如表1所示。

表1 常用符號

本節(jié)通過圖2和表2的例子介紹FPGA間的布線問題。給定一組線網(wǎng)N和一組線網(wǎng)組NG。線網(wǎng)組是根據(jù)設(shè)計目的給定的。例如，具有相似屬性或相同功耗的線網(wǎng)將在同一個線網(wǎng)組中。同時，給定一個無向圖G，其中包括了多個由F表示的FPGA和多個由P表示的FPGA連接對。問題目標(biāo)是根據(jù)無向圖G對所有線網(wǎng)進(jìn)行布線，并且為每條邊分配合理的TDM比率，以最小化線網(wǎng)組的最大TDM比率。

表2 線網(wǎng)組信息

圖2 TDM比率分配示意圖

表2給出了線網(wǎng)N和線網(wǎng)組NG的信息，其中，不同的線網(wǎng)用不同顏色表示。圖2(a)是一個結(jié)構(gòu)圖。fi代表第i個FPGA，pk代表第k個FPGA連接對。圖2(b)是表1基于圖2(a)所生成的布線結(jié)果。ej,k代表線網(wǎng)nj經(jīng)過連接對pk所布的邊。連接對pk間邊的數(shù)量就是通過連接對pk的信號數(shù)量。為了分析系統(tǒng)時延，每條邊ej,k應(yīng)該被分配一個TDM比率。一個FPGA連接對應(yīng)該滿足TDM比率約束，如式(2)所示。

其中，etrj,k表示ej,k的TDM比率。如圖1所示，由于所有的信號必須在半個周期內(nèi)完成1次傳輸，故etrj,k的值必須是偶數(shù)。每條邊的TDM比率分配結(jié)果如圖2(c)所示，對于p1, e2,1, e3,1, e4,1和e5,1的TDM比率分別是4, 6, 6和10。由于1/4+1/6+1/6+1/10<1，所以p1滿足TDM比率約束。

線網(wǎng)nj的TDM比率和線網(wǎng)組ngj的TDM比率定義為

其中，ntrj和gtrj分別表示nj的TDM比率和ngi的TDM比率。如圖2(c)所示，線網(wǎng)n2上的邊有e2,1=4和e2,3=2，所以ntr2=etr2,1+etr2,3=2+4=6。線網(wǎng)組ng2的包括n3和n4，所以gtr2是12。

本文的優(yōu)化目標(biāo)是最小化TDM比率最大線網(wǎng)組的TDM比率，從而優(yōu)化系統(tǒng)時延，具體如式(6)所示。

其中，gmt代表了TDM比率最大的線網(wǎng)組的TDM比率。如圖2(c)所示，gmt是12。

3 總體框架

用于時分復(fù)用技術(shù)的多階段協(xié)同優(yōu)化FPGA布線方法的總體框架如圖3所示，分別為布線拓?fù)渖呻A段、TDM比率分配階段和TDM比率優(yōu)化階段3個階段。具體地，第1階段根據(jù)問題定義的線網(wǎng)和線網(wǎng)組進(jìn)行布線，得到未分配TDM比率的布線結(jié)果。第2階段使用拉格朗日松弛的方法為FPGA連接對的每條邊分配初始的TDM比率。第3階段通過松弛TDM比率較小的線網(wǎng)組，減小TDM比率倒數(shù)之和相對較小的FPGA連接對的最大TDM比率來優(yōu)化TDM比率比較大的線網(wǎng)組。MSCOFRouting通過上述3個階段協(xié)同優(yōu)化FPGA的可布線性和TDM比率分配結(jié)果。

圖3 MSCOFRouting總體流程圖

3.1 布線拓?fù)渖?/h3>

布線拓?fù)渖呻A段的目標(biāo)是根據(jù)給定的線網(wǎng)和線網(wǎng)組定義將每個線網(wǎng)的FPGA連接在一起。布線生成的Steiner樹的質(zhì)量會影響后續(xù)的TDM比率分配。由于Dijkstra算法可以有效構(gòu)建Steiner樹[13,14]，因此本文使用基于Dijkstra算法的FPGA間布線算法連接所有線網(wǎng)，解決FPGA間的布線優(yōu)化問題，使可布線性得到優(yōu)化。算法中各變量的定義如下，fs代表從Fn中選擇的第1個FPGA、Fn表示線網(wǎng)nj必須連接的目標(biāo)FPGA、d表示兩個FPGA間的布線代價、Fall表示所有FPGA、fu表示與fs布線代價最小的FPGA，fv表示fu的每個鄰居FPGA,spv表示該線網(wǎng)的Steiner樹。

自適應(yīng)布線算法如下所示。由于線網(wǎng)所在的線網(wǎng)組中的線網(wǎng)數(shù)量和線網(wǎng)需要連接的FPGA數(shù)量對于線網(wǎng)的布線方案有重要的影響。所以所有線網(wǎng)都按照這兩個指標(biāo)進(jìn)行排序。然后，初始化布線圖，每個FPGA連接對的初始布線代價為1。最后，對所有的線網(wǎng)進(jìn)行迭代布線。

對所有的線網(wǎng)進(jìn)行迭代布線的具體步驟如下。首先，從Fn中選擇一個FPGA賦值給fs。其次，初始化Fn中各FPGA與fs的距離。然后，集合Fall等于集合F。最后，通過Dijkstra算法構(gòu)造Steiner樹。Dijkstra算法首先找到與Fall中與fs代價最小的FPGA fu，然后更新集合Fall，最后更新fu的所有鄰居節(jié)點的布線代價dv。當(dāng)找到所有目標(biāo)FPGA后，Steiner樹被構(gòu)造出來，把spx記錄下來。Steiner樹所使用的FPGA連接對的布線代價更新公式為

其中，Tpk代表FPGA連接對的布線代價，Npk代表FPGA連接對上已布線的邊數(shù)，te和to分別表示FPGA連接對上已布線的邊數(shù)為偶數(shù)和奇數(shù)的更新代價。實驗得出te, to分別取0.81和1.19時優(yōu)化效果最好。

圖4只考慮兩個FPGA間的布線情況。兩個FPGA間有1條或者2條邊時，每條邊分配的TDM比率都是2，最大TDM比率都是2；當(dāng)兩個FPGA間有3條邊時，每條邊分配的TDM比率分別是2, 4, 4。當(dāng)兩個FPGA間有4條邊時，每條邊分配的TDM比率分別是4, 4, 4, 4。最大TDM比率都是4。由此可以得出結(jié)論：設(shè)i為奇數(shù)，當(dāng)兩個FPGA間有i條邊時，布下1條邊之后，最大TDM比率不變，為i+1；當(dāng)兩個FPGA間有i+1條邊時，布下1條邊之后，最大TDM比率值增加2，為i+3。所以布線代價更新式(7)可以減少兩個FPGA間奇數(shù)條邊的情況，優(yōu)化布線結(jié)果，減少最大的T D M 比率。

圖4 FPGA之間不同布線情況示意圖

3.2 TDM比率分配

TDM比率分配階段需要為每條邊分配滿足約束的TDM比率并且使TDM比率最大的線網(wǎng)組的TDM比率最小化。在這一階段，本文提出了一種基于拉格朗日松弛算法的TDM比率分配方法。

由于優(yōu)化目標(biāo)是將線網(wǎng)組中最大的TDM比率最小化，所以問題模型可以寫成

其中，gmt是布線圖中TDM比率最大的線網(wǎng)組的TDM比率，tren是線網(wǎng)n中邊e的TDM比率。本文將此公式稱為主問題(Primal Problem, PP)。為了解決這個NP難問題，算法松弛第1個約束并引入非負(fù)拉格朗日乘數(shù)λ。λ作為違反約束的懲罰值。式(8)引入λ后可以得到

對于給定的拉格朗日乘數(shù)，拉格朗日乘數(shù)子問題LRS(λ)如式(10)所示。

通過應(yīng)用Karush-Kuhn-Tucker (KKT)條件以獲得最優(yōu)解，LRS(λ)問題可以簡化為

拉格朗日對偶問題(Lagrangian Dual Problem,LDP)可以定義為

對給定λ集合，求解LDP就是求解下界的最大值。LDP的主要目的是找到合適的λ集合懲罰PP中違反的約束。拉格朗日乘子根據(jù)時序弧的時序臨界性更新，以滿足KKT條件[15–17]。更新公式為

其中，TDMi,g為第i次迭代線網(wǎng)組g與最大線網(wǎng)組的TDM比率之比，Ki,g為第i次迭代的加速因子。加速因子越大，收斂速度越快，但是收斂效果越差。λ越接近目標(biāo)值，加速因子應(yīng)該越小。Ki,g的更新公式為

其中，str是由用戶定義的gmt的優(yōu)化目標(biāo)。

TDM比率分配算法如下所示。首先，計算邊ej,k的所在FPGA連接對邊的數(shù)量。接著，計算線網(wǎng)組ngi的λi。然后，根據(jù)λ集合計算線網(wǎng)ni的snλi值，計算分配給每條邊的TDM比率，再更新λ集合。最后，根據(jù)式(13)更新λi并根據(jù)式(14)更新Ki,g。

3.3 TDM比率優(yōu)化

在TDM比率分配階段，通過拉格朗日松弛算法得到的初始TDM比率并非最優(yōu)解，還存在優(yōu)化空間。因此，TDM比率優(yōu)化階段可以通過增加TDM比率較小的線網(wǎng)組邊的TDM比率以減少TDM比率較大的線網(wǎng)組邊的TDM比率，并可以針對具體連接對進(jìn)行優(yōu)化系統(tǒng)時延，從而使TDM比率最大的線網(wǎng)組的TDM比率最小化。

TDM比率優(yōu)化算法包括3個步驟。第1步是縮減操作。具體是增加TDM比率較小的線網(wǎng)組的TDM比率，減少TDM比率較大的線網(wǎng)組的TDM比率。第2步是合法化操作。經(jīng)過縮減步驟后，TDM比率增加的FPGA連接對可能會違反TDM比率約束。因此，違反約束的FPGA連接對需要進(jìn)行合法化操作。第3步是針對性優(yōu)化操作。經(jīng)過上述步驟后，所有FPGA連接對的TDM比率的倒數(shù)和與最大值1還有一定距離。通過減少連接對中TDM比率最大的etrj,k的方式，使得每個FPGA連接對的TDM比率倒數(shù)和更接近1，從而使TDM比率最大的線網(wǎng)組的TDM比率更小。

縮減操作的具體步驟如下所示。首先，所有線網(wǎng)按其所在線網(wǎng)組的最大TDM比率從大到小排序。然后，線網(wǎng)nj中每條邊的TDM比率e t根據(jù)以下公式更新。

線網(wǎng)nj的TDM比率減少后，更新nglj中各線網(wǎng)組的TDM比率，有利于后續(xù)的縮減。

第2步是對FPGA連接對進(jìn)行合法化操作。經(jīng)過縮減步驟，TDM比率增加的邊ej,k可以直接使用新的TDM比率e tr；對于TDM比率減小的邊ej,k，如果pk滿足TDM比率約束，則用e tr替換對應(yīng)的pk中的每條邊的etrj,k。然而，如果pk不滿足TDM比率約束，應(yīng)由式(16)合法化。

算法第3步是減小具體FPGA連接對的最大TDM比率。經(jīng)過前兩個階段后，當(dāng)FPGA連接對邊的TDM比率倒數(shù)和resk小于0.95時，這個FPGA連接對的最大TDM比率由式(17)進(jìn)行更新。

其中，resk是FPGA連接對pk上TDM比率倒數(shù)和，eltk,max是FPGA連接對pk上最大的TDM比率。

如果在縮減步驟中，當(dāng)mngj> str，減少的部分都向下取偶數(shù)會使得當(dāng)前FPGA連接對的TDM倒數(shù)和更小，更有利于第3步FPGA連接對中最大TDM比率的減小。比如，當(dāng)有3個線網(wǎng)組的TDM比率為4, 14和24，優(yōu)化的目標(biāo)值為8。如果不論mngj是否大于str，變化值都向上取偶數(shù)，經(jīng)過縮減階段得出的TDM比率是6, 10和16，TDM倒數(shù)和為0.329；如果按照式(15)優(yōu)化TDM比率，得到的TDM比率是6, 12和16，TDM倒數(shù)和為0.25。后者TDM比率倒數(shù)和小于前者，更有利于第3步FPGA連接對最大TDM比率的減小。所以選擇式(15)的縮減方式。

3.4 多線程并行化

為了提高布線器的效率，使用并行編程模型OpenMp在布線器的各個階段集成多線程并行化方法。編譯器通過識別編譯制導(dǎo)語句自動創(chuàng)建線程進(jìn)行并行化，從而有效提高算法的效率。在布線拓?fù)渖呻A段，各線網(wǎng)的布線操作可以并行執(zhí)行。在TDM比率分配階段，每個線網(wǎng)的TDM比率分配都是完全獨立的。因此，這個階段可以對不同線網(wǎng)進(jìn)行并行化操作。在系統(tǒng)時延優(yōu)化階段，每個線網(wǎng)的縮減操作都是并行的。合法化操作和針對性優(yōu)化中不同F(xiàn)PGA連接對可以并行處理。但是，由于不同線網(wǎng)之間存在資源沖突，自適應(yīng)布線算法的記錄spx操作和TDM比率優(yōu)化算法的更新nglj中各線網(wǎng)組的TDM比率操作應(yīng)該加鎖。通過對上述3個階段使用多線程并行化方法可以有效減少算法運(yùn)行時間。

4 實驗結(jié)果

所提出的優(yōu)化框架采用C/C++語言實現(xiàn)，并在Intel Xeon Linux服務(wù)器上運(yùn)行。本文在2019年的ICCAD競賽[12]發(fā)布測試用例上展開實驗。該測試用例將FPGA系統(tǒng)中的FPGA抽象為節(jié)點，忽略了一些FPGA的特殊性，著重解決FPGA間的布線問題。所以本文算法可以解決不同F(xiàn)PGA的布線問題，具有普適性。表3為測試用例具體信息，其中#FPGA表示FPGA數(shù)量，#Net表示線網(wǎng)數(shù)量，#NG表示線網(wǎng)組數(shù)量，#Edge表示FPGA連接對數(shù)量。

表3 測試用例信息

4.1 與ALIFRouter及MSFRoute的實驗比較

本節(jié)參考ICCAD2019比賽[12]的計算評估分?jǐn)?shù)公式將MSCOFRouting與ALIFRouter[11]及MSFRoute[18]進(jìn)行比較。為了強(qiáng)調(diào)運(yùn)行時間的影響，計算評估分?jǐn)?shù)時考慮了運(yùn)行時間。評估分?jǐn)?shù)sco計算公式為

其中，TR為TDM最大的線網(wǎng)組的TDM比率，RT為運(yùn)行時間，MRT為3個布線器運(yùn)行時間的中位數(shù)。sum為所有測試用例的sco之和。布線器的sum越小表示它的優(yōu)化效果越好。

如表4所示，MSCOFRouting獲得了最好的sum，并且達(dá)到了最好的TDM比率和運(yùn)行時間。與MSFRoute和ALIFRouter相比，MSCOFRouting的TDM比率分別降低了4.57%和1.05%，運(yùn)行時間分別縮短了20.8%和0.44%。由于每個標(biāo)準(zhǔn)測試用例涉及多個線網(wǎng)組，總的布線邊數(shù)量非常多，因此時鐘周期數(shù)的基數(shù)很大，TDM比率數(shù)值很大。雖然TDM比率的優(yōu)化率較小，但是TDM比率優(yōu)化值較大，系統(tǒng)時延的優(yōu)化效果較好，所以實驗結(jié)果表明MSCOFRouting可以有效優(yōu)化系統(tǒng)時延。

表4 本文算法與ALIFRouter及MSFRoute的實驗比較(TR為TDM Ratio)

4.2 多線程并行化方法的有效性驗證

MSCOFRouting在不同線程數(shù)下的運(yùn)行時間如圖5所示。不同的線段表示不同測試用例的運(yùn)行時間。本節(jié)在具有典型性的中等規(guī)模測試用例S3, S4和H2上展開實驗。通過使用8個線程、16個線程、24個線程和多線程并行化方法，MSCOFRouting分別可以得到3.11倍、3.82倍和4.08倍的加速。各線網(wǎng)間存在共用同一變量的情況。為了避免多個線程同時修改變量而導(dǎo)致數(shù)據(jù)錯誤，則需要對共享變量進(jìn)行加鎖操作。如果同時運(yùn)行中的線程需要用到已使用的共享變量，則需要等待正在使用該資源的線程運(yùn)行結(jié)束。所以隨著線程數(shù)的增多，等待共享變量的時間逐漸增加，運(yùn)行時間的優(yōu)化率逐漸減少。

圖5 并行化方法有效性折線圖

4.3 自適應(yīng)布線算法有效性驗證

為了驗證自適應(yīng)布線算法的有效性，本節(jié)將采用不同更新代價的自適應(yīng)布線算法與未采用自適應(yīng)布線算法的最大TDM比率進(jìn)行比較。表5為采用不同權(quán)重值的自適應(yīng)布線算法的實驗結(jié)果。數(shù)據(jù)都是從同一環(huán)境中由8個線程運(yùn)行的程序中獲得的。表5中△TR的優(yōu)化率的計算公式為

表5 自適應(yīng)布線算法有效性驗證

不同的更新代價分別將△TR比率的優(yōu)化率增加4.26%, 11.63%, 4.88%和10.93%。根據(jù)實驗結(jié)果可知，當(dāng)te=0.19, to=1.81時，自適應(yīng)布線算法效果最好。由于較好的布線結(jié)果較少出現(xiàn)布線擁塞的情況，從而減少最大TDM比率。因此通過這些△TR的優(yōu)化率可以得出自適應(yīng)布線算法可以有效避免布線擁塞的情況出現(xiàn)，解決FPGA間的布線優(yōu)化問題，優(yōu)化布線結(jié)果，有效地減少系統(tǒng)時延。

4.4 LR分配算法和TDM比率優(yōu)化算法有效性驗證

本節(jié)將TDM比率分配算法和TDM比率優(yōu)化算法運(yùn)用到當(dāng)前最先進(jìn)的FPGA布線器ALIFRouter中進(jìn)行比較。表6為LR分配算法和多層次的TDM比率優(yōu)化算法的實驗結(jié)果，并與ALIFRouter的實驗數(shù)據(jù)進(jìn)行對比。數(shù)據(jù)都是從同一環(huán)境中由8個線程運(yùn)行的程序中獲得的。表格中△TR的優(yōu)化率是由MSFRoute在各測試用例上得到的線網(wǎng)組的最大TDM比率減去使用ALIFRouter、使用TDM比率分配算法和使用TDM比率優(yōu)化算法后獲得的最大TDM比率計算得到的。與ALIFRouter相比，兩種算法可分別將ΔTR比率的優(yōu)化率增加8.85%和10.39%。這些ΔTR的優(yōu)化率表明LR分配算法和TDM比率優(yōu)化算法可以有效地降低系統(tǒng)時延。

表6 LR分配算法(即TDM比率分配算法)和TDM比率優(yōu)化算法有效性驗證

5 結(jié)束語

針對FPGA系統(tǒng)中運(yùn)用TDM技術(shù)后導(dǎo)致系統(tǒng)時延增加的問題，本文提出了一種用于時分復(fù)用技術(shù)的多階段協(xié)同優(yōu)化FPGA布線方法，通過布線拓?fù)渖呻A段、TDM比率分配階段和TDM比率優(yōu)化階段3個階段協(xié)同優(yōu)化FPGA的可布線性和TDM比率分配結(jié)果。首先，為了生成高質(zhì)量的布線拓?fù)?，避免布線擁塞，解決FPGA間的布線優(yōu)化問題，提出了自適應(yīng)布線算法。其次，使用基于拉格朗日松弛的TDM比率分配算法，為布線圖的邊分配系統(tǒng)時延更小的初始TDM比率。然后，為了進(jìn)一步減小最大線網(wǎng)組的TDM比率，通過一種多層次的TDM比率優(yōu)化算法，同時縮減線網(wǎng)組和FPGA連接對的TDM比率。并且，為了提高M(jìn)SCOFRouting的運(yùn)行效率，在上述3個算法中使用多線程并行化方法，降低算法的運(yùn)行時間。實驗結(jié)果表明，與同類布線器相比，本文提出的MSCOFRouting能夠獲得最佳的系統(tǒng)時延優(yōu)化質(zhì)量。未來的工作中，將擴(kuò)展本文算法應(yīng)用到考慮帶高速收發(fā)器的FPGA系統(tǒng)的TDM比率優(yōu)化問題。