劉耿耿 許文霖 周茹平 徐 寧

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

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

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

1 引言

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

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

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

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

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

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

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

(4) 將多線程并行化方法運用到上述3個算法，進一步提高MSCOFRouter的運行效率。

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

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

2 問題模型

2.1 時分復用技術

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

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

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

2.2 FPGA間的布線問題

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

表1 常用符號

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

表2 線網組信息

圖2 TDM比率分配示意圖

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

其中，etrj,k表示ej,k的TDM比率。如圖1所示，由于所有的信號必須在半個周期內完成1次傳輸，故etrj,k的值必須是偶數(shù)。每條邊的TDM比率分配結果如圖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比率約束。

線網nj的TDM比率和線網組ngj的TDM比率定義為

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

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

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

3 總體框架

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

圖3 MSCOFRouting總體流程圖

3.1 布線拓撲生成

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

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

對所有的線網進行迭代布線的具體步驟如下。首先，從Fn中選擇一個FPGA賦值給fs。其次，初始化Fn中各FPGA與fs的距離。然后，集合Fall等于集合F。最后，通過Dijkstra算法構造Steiner樹。Dijkstra算法首先找到與Fall中與fs代價最小的FPGA fu，然后更新集合Fall，最后更新fu的所有鄰居節(jié)點的布線代價dv。當找到所有目標FPGA后，Steiner樹被構造出來，把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；當兩個FPGA間有3條邊時，每條邊分配的TDM比率分別是2, 4, 4。當兩個FPGA間有4條邊時，每條邊分配的TDM比率分別是4, 4, 4, 4。最大TDM比率都是4。由此可以得出結論：設i為奇數(shù)，當兩個FPGA間有i條邊時，布下1條邊之后，最大TDM比率不變，為i+1；當兩個FPGA間有i+1條邊時，布下1條邊之后，最大TDM比率值增加2，為i+3。所以布線代價更新式(7)可以減少兩個FPGA間奇數(shù)條邊的情況，優(yōu)化布線結果，減少最大的T D M 比率。

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

3.2 TDM比率分配

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

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

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

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

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

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

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

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

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

TDM比率分配算法如下所示。首先，計算邊ej,k的所在FPGA連接對邊的數(shù)量。接著，計算線網組ngi的λi。然后，根據(jù)λ集合計算線網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比率較小的線網組邊的TDM比率以減少TDM比率較大的線網組邊的TDM比率，并可以針對具體連接對進行優(yōu)化系統(tǒng)時延，從而使TDM比率最大的線網組的TDM比率最小化。

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

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

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

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

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

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

如果在縮減步驟中，當mngj> str，減少的部分都向下取偶數(shù)會使得當前FPGA連接對的TDM倒數(shù)和更小，更有利于第3步FPGA連接對中最大TDM比率的減小。比如，當有3個線網組的TDM比率為4, 14和24，優(yōu)化的目標值為8。如果不論mngj是否大于str，變化值都向上取偶數(shù)，經過縮減階段得出的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在布線器的各個階段集成多線程并行化方法。編譯器通過識別編譯制導語句自動創(chuàng)建線程進行并行化，從而有效提高算法的效率。在布線拓撲生成階段，各線網的布線操作可以并行執(zhí)行。在TDM比率分配階段，每個線網的TDM比率分配都是完全獨立的。因此，這個階段可以對不同線網進行并行化操作。在系統(tǒng)時延優(yōu)化階段，每個線網的縮減操作都是并行的。合法化操作和針對性優(yōu)化中不同F(xiàn)PGA連接對可以并行處理。但是，由于不同線網之間存在資源沖突，自適應布線算法的記錄spx操作和TDM比率優(yōu)化算法的更新nglj中各線網組的TDM比率操作應該加鎖。通過對上述3個階段使用多線程并行化方法可以有效減少算法運行時間。

4 實驗結果

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

表3 測試用例信息

4.1 與ALIFRouter及MSFRoute的實驗比較

本節(jié)參考ICCAD2019比賽[12]的計算評估分數(shù)公式將MSCOFRouting與ALIFRouter[11]及MSFRoute[18]進行比較。為了強調運行時間的影響，計算評估分數(shù)時考慮了運行時間。評估分數(shù)sco計算公式為

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

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

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

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

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

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

4.3 自適應布線算法有效性驗證

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

表5 自適應布線算法有效性驗證

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

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

本節(jié)將TDM比率分配算法和TDM比率優(yōu)化算法運用到當前最先進的FPGA布線器ALIFRouter中進行比較。表6為LR分配算法和多層次的TDM比率優(yōu)化算法的實驗結果，并與ALIFRouter的實驗數(shù)據(jù)進行對比。數(shù)據(jù)都是從同一環(huán)境中由8個線程運行的程序中獲得的。表格中△TR的優(yōu)化率是由MSFRoute在各測試用例上得到的線網組的最大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 結束語

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