OpenPARF: 基于深度學(xué)習(xí)工具包的大規(guī)模異構(gòu)FPGA開源布局布線框架

麥 景 王嘉睿 邸志雄 林亦波(北京大學(xué)計算機(jī)學(xué)院 北京 100871)

②(北京大學(xué)集成電路學(xué)院 北京 100871)

③(西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 成都 611756)

1 引言

FPGA因其可編程性、高并行性以及低功耗得到了廣泛應(yīng)用[1]。然而，隨著現(xiàn)代FPGA規(guī)模的逐漸增大，F(xiàn)PGA設(shè)計工程師必須依靠FPGA計算機(jī)輔助設(shè)計(Computer Aided Design, CAD)工具來完成FPGA的設(shè)計。FPGA CAD的主要流程包括設(shè)計描述、邏輯綜合、工藝映射、物理實現(xiàn)和比特流生成[2]。其中，物理實現(xiàn)主要包括布局和布線等步驟，決定邏輯單元在FPGA上的位置以及連線之間的延遲。物理實現(xiàn)中的布線部分是FPGA CAD流程中用時最長的部分，占到整個流程的41%～86%[3]。因此，物理實現(xiàn)是決定最終電路性能的關(guān)鍵步驟，其質(zhì)量和效率直接影響FPGA CAD工具的競爭力。

工業(yè)界主流的FPGA廠商，如Xilinx和Intel，采用自研的Vivado和Quartus FPGA CAD工具。這些工具均與FPGA廠商的硬件架構(gòu)強(qiáng)綁定，難以遷移到其他FPGA架構(gòu)。相較之下，開源FPGA CAD工具因其算法透明，方便2次開發(fā)，成為FPGA設(shè)計工程師的另一個選擇。當(dāng)前學(xué)術(shù)界知名的開源FPGA CAD工具 VTR(Verilog-To-Routing)[4]能夠從Verilog網(wǎng)表生成FPGA布局布線的結(jié)果。然而，VTR使用的布局布線算法較為陳舊，仍然在采用基于模擬退火的算法，導(dǎo)致性能和效率無法滿足大規(guī)模FPGA設(shè)計的需求。此外，VTR簡化了布線架構(gòu)，沒有考慮FPGA邏輯單元輸入輸出引腳的邏輯不等價性，無法適用于越來越復(fù)雜的FPGA架構(gòu)。

本文提出一個開源的FPGA布局布線框架Open-PARF (Open-source Placement And Routing Framework)。OpenPARF支持在工業(yè)級FPGA架構(gòu)下讀入電路網(wǎng)表，生成布局布線結(jié)果。該框架基于深度學(xué)習(xí)工具包PyTorch實現(xiàn)，通過底層C++/CUDA算子結(jié)合上層Python接口的方式，支持CPU平臺運(yùn)行和GPU加速，兼具Python的靈活性與C++/CUDA的高效性。在布局算法方面，本文采用了一種新型非對稱多靜電場系統(tǒng)和多層拉格朗日松弛方法，以處理FPGA布局問題中的復(fù)雜約束。在布線算法方面，本文面向現(xiàn)代FPGA的復(fù)雜布線架構(gòu)，采用兩階段布線算法，支持FPGA邏輯單元各引腳邏輯不等價等靈活場景，可實現(xiàn)邏輯單元級別的布線。本文的主要貢獻(xiàn)總結(jié)如下：

(1) 提出開源的FPGA布局布線框架Open-PARF。本框架支持在工業(yè)級FPGA架構(gòu)下讀入FPGA網(wǎng)表，并生成布局布線后的FPGA結(jié)果。

(2) 提出一種基于新型非對稱多靜電場系統(tǒng)的FPGA布局算法，并通過多層拉格朗日松弛方法處理FPGA布局問題中的復(fù)雜約束。

(3) 提出一種邏輯單元級別的FPGA布線算法，通過對FPGA布線資源的詳細(xì)建模和全局/詳細(xì)兩階段布線，支持邏輯單元引腳邏輯不等價等靈活場景，有效減少布線擁塞。

(4) 與學(xué)術(shù)界最先進(jìn)的布局布線工具相比，Open-PARF可減少0.4%～12.7%的布線線長，并實現(xiàn)兩倍以上的布局效率提升。

本文的組織結(jié)構(gòu)如下：第2節(jié)介紹FPGA的布局布線架構(gòu)和挑戰(zhàn)；第3節(jié)回顧現(xiàn)有FPGA布局布線算法的優(yōu)劣；第4節(jié)詳細(xì)介紹OpenPARF算法框架；第5節(jié)通過實驗驗證框架的性能和效率；第6節(jié)對本文進(jìn)行總結(jié)，并展望未來的研究方向。

2 研究背景

2.1 FPGA架構(gòu)簡介

FPGA是一種可編程邏輯芯片，其邏輯電路結(jié)構(gòu)可以被動態(tài)配置，從而在實現(xiàn)不同的功能或應(yīng)用時提供更大的靈活性和可定制性。不同廠商制造的FPGA芯片架構(gòu)大體相同，局部硬件配置上有少許差異。圖1抽象出了FPGA的布局布線架構(gòu)的統(tǒng)一視角。FPGA布局布線架構(gòu)包括時鐘區(qū)域(Clock Region)、片(Tile)、片上位置(Site)以及基礎(chǔ)邏輯單元(Basic Element of Logic, BEL)。

(1)BEL。BEL是FPGA架構(gòu)中基本組成單元。BEL可分為邏輯BEL和布線BEL兩種類型。邏輯BEL是表示FPGA邏輯功能的最小單元，如查找表(LookUp Table, LUT)和觸發(fā)器(Flip-Flop, FF)等。布線BEL是一種可編程的布線多選器，用于B E L 之間的連線布線。布線階段將由F P G A CAD工具配置布線BEL。

(2)Site。Site的組成元素包括：(a) 一組關(guān)聯(lián)的BELs；(b) Site與外部的輸入輸出引腳(Site Pin)；(c) Site內(nèi)部的BELs與Site Pins之間的連線。Site的主要類型包括CLB、數(shù)字信號處理單元(Digital Signal Processing, DSP)、塊存儲單元(Block RAM, BRAM)和用于接口的輸入/輸出塊(Input/Output block, IO)等。Site在FPGA版圖上呈2維排布，且同類型的Site成列分布。

(3)Tile。Tile由Site以及交換框(Switch Box)組成。Switch Box在FPGA上呈陣列分布，是FPGA上最重要的布線中繼點(diǎn)。Swich Box的連線包括Tile內(nèi)部的Site與Switch Box之間連線和不同Tile的Switch Box之間的連線。CLB, DSP, BRAM等Site首先連接到同一個Tile中臨近的Switch Box，再通過橫向和縱向的互聯(lián)軌道連接到另一個Site。這些互聯(lián)軌道不僅可以連接相鄰的Tile，也可以跨Tile連接(跨Tile連接的互聯(lián)軌道稱為倍線)。

(4)Clock Region。FPGA版圖被切分成若干個時鐘區(qū)域。每個時鐘區(qū)域進(jìn)一步被切分成時鐘半列(Half Column)。時鐘區(qū)域和時鐘半列內(nèi)的Tile共享一組有限的時鐘布線資源，如時鐘信號的種類不能超過一定數(shù)量。

以上描述闡述了FPGA布局布線的層次結(jié)構(gòu)。在不同Site類型當(dāng)中，CLB數(shù)量最多、分布最廣。CLB可以按照配置邏輯分為SLICEL和SLICEM兩種異構(gòu)類型。以SLICEL為例，圖1右下角展示了Xilinx Ultrascale+系列[5]的簡化內(nèi)部構(gòu)造圖，其包括8個LUT, 16個FF, 2個時鐘信號(CLK0-CLK1)，4個時鐘使能信號(CE0-CE3)以及2個置位-復(fù)位信號(SR0-SR1)等。根據(jù)BEL和時鐘控制信號的組合關(guān)系，C L B 進(jìn)一步被劃分成8 組B E L 的組合(Group)，每組包括1個LUT以及2個相鄰的FF，組合{0,1,2,3}與組合{4,5,6,7}分別被稱為半CLB。SLICEM在SLICEL的基礎(chǔ)上，增加了額外的邏輯信號，因此除了可被配置為具有邏輯功能的LUT邏輯單元外，還能被配置為具有存儲功能的分布存儲單元(Distributed RAM, DiRAM)和移位寄存器(SHIFT register, SHIFT)。

圖1右下角以UltraScale VU095為例描述了CLB內(nèi)的信號線。具體而言，(1)半CLB中FF的CLK信號和SR信號相同；(2)半CLB中FF0的CE信號相同，同時半CLB中FF1的CE信號也相同；(3)如果網(wǎng)表內(nèi)有LUT邏輯單元的輸出信號直接連接到FF上，那么LUT邏輯單元和FF打包在同一個組合內(nèi)，可以有效減少路由線長。

2.2 FPGA布局布線挑戰(zhàn)

FPGA高度異構(gòu)的芯片架構(gòu)極大增加了FPGA布局布線的難度。從上述FPGA的芯片架構(gòu)層次劃分可以總結(jié)出以下FPGA布局布線挑戰(zhàn)。

邏輯單元打包(Packing)規(guī)則復(fù)雜。打包指的是依次將LUT和FF打包為組合、半CLB和CLB，從而最大化可用的物理資源，減少邏輯單元之間的延遲。邏輯單元打包需要遵守組合內(nèi)、半CLB和CLB內(nèi)的信號線連接約束[6]。例如，能否將LUT和FF打包到一個CLB取決于LUT和FF之間的連接關(guān)系，以及時鐘控制信號與FF的連接關(guān)系。

資源異構(gòu)性高。FPGA Site具有多種類型，包括CLB, DSP, BRAM和IO等。這些類型在FPGA的版圖上分布不均，在空間上離散，導(dǎo)致在芯片設(shè)計階段期望的邏輯單元空間分布在物理實現(xiàn)時難以保證。例如，深度學(xué)習(xí)加速器中常用的脈動陣列是一個由處理單元組成的2維陣列，每個處理單元一般需要使用DSP資源。然而，由于DSP資源在FPGA上成列分布，在實現(xiàn)時難以對齊設(shè)計的空間需求[7]。

布局布線資源有限。FPGA的物理實現(xiàn)受限于有限的布局資源容量、布線資源容量和時鐘布線資源容量。局部過高的布局密度不僅會造成邏輯資源緊張，更會導(dǎo)致布線擁塞[6,8]。對于布線算法本身而言，F(xiàn)PGA Switch Box之間存在倍線連接，導(dǎo)致連線在空間上存在跳躍的情況，增加了擁塞評估的難度。有限的時鐘布線資源對FPGA的布局布線提出了離散度更高的優(yōu)化約束條件。時鐘區(qū)域和時鐘半列對都經(jīng)過其中的時鐘信號的數(shù)量和種類有著嚴(yán)格限制[9]，極大增加了布局布線的難度。

3 相關(guān)工作

為解決上述挑戰(zhàn)，在最近幾年關(guān)于FPGA布局算法的研究中，除了通?？紤]的線長，可布線性等主要優(yōu)化目標(biāo)，在布局階段還加入了時鐘信號布線等優(yōu)化指標(biāo)，把后續(xù)流程的優(yōu)化目標(biāo)提前到布局階段，從而減輕后續(xù)優(yōu)化流程的難度。在關(guān)于FPGA布線算法的工作中，提出了加速迭代收斂的布線算法來求解大規(guī)模布線資源圖上的布線問題。隨著布局布線問題規(guī)模的不斷擴(kuò)大，也出現(xiàn)了利用異構(gòu)計算和機(jī)器學(xué)習(xí)[10]來提高FPGA布局布線算法運(yùn)行效率的研究工作，極大加速了FPGA設(shè)計流程的迭代流程和設(shè)計周期。

3.1 FPGA布局相關(guān)工作簡述

目前工業(yè)界和學(xué)術(shù)界使用的布局算法主要使用解析式優(yōu)化算法，包括比較成熟的基于力學(xué)模型的2次規(guī)劃方法[11]和非線性優(yōu)化算法[12]?；?次規(guī)劃的算法運(yùn)行迭代次數(shù)更少，求解速度更快；相比于非線性優(yōu)化算法，非線性模型能夠?qū)?yōu)化目標(biāo)函數(shù)進(jìn)行更加平滑的近似，布局結(jié)果質(zhì)量相對較優(yōu)，但是也引入了更高的復(fù)雜度。

在最近幾年提出的非線性優(yōu)化算法中，文獻(xiàn)[13–16]提出了基于靜電場系統(tǒng)的近似全局密度估計函數(shù)和基于Nestrov的非線性梯度優(yōu)化算法，在公開測試數(shù)據(jù)上獲得普遍較好的布局結(jié)果?；陟o電場系統(tǒng)的布局算法把網(wǎng)表中的邏輯單元建模成帶電體，邏輯單元受到彼此之間的斥力作用從而使得邏輯單元密度受到約束；并且目標(biāo)函數(shù)中的密度項對應(yīng)于靜電場系統(tǒng)整體的電勢能，邏輯單元受到電場力影響朝著電勢能減少的方向移動，等價于在對目標(biāo)函數(shù)進(jìn)行優(yōu)化。另外，基于梯度的優(yōu)化算法能通過并行化算法處理百萬級別的網(wǎng)表規(guī)模，可以充分使用CPU多線程或者GPU進(jìn)行并行加速[17–20]。

布線擁塞驅(qū)動的FPGA布局算法。 隨著設(shè)計復(fù)雜程度的提升，在布局階段單純考慮優(yōu)化線長可能會導(dǎo)致在后續(xù)的布線階段出現(xiàn)布線擁塞的情況。因此部分研究考慮在布局階段加入對可布線性的考慮來減輕后續(xù)布線階段的壓力。文獻(xiàn)[21]和文獻(xiàn)[18]提出在布局階段提前做布線資源使用情況估計，并對處于布線擁塞區(qū)域的邏輯單元進(jìn)行面積膨脹，膨脹后的面積將反映在密度估計函數(shù)上，從而減少該區(qū)域的布線擁塞程度。文獻(xiàn)[22]提出在打包階段和詳細(xì)布局階段使用膨脹后面積來進(jìn)行匹配從而減少擁塞程度。文獻(xiàn)[23]考慮到FPGA相比于專用集成電路 (Application Specific Integrated Circuit, ASIC)布局資源分布不均衡的問題在全局布局的初始階段進(jìn)行考慮到布線資源分布的網(wǎng)表分割，并在布線資源估計時加入引腳數(shù)量作為權(quán)重進(jìn)行估計。除了基于面積膨脹的算法，文獻(xiàn)[24]提出在引腳密度估計中使用基于概率分布的布線擁塞估計算法。對布線擁塞程度進(jìn)行估計一直是FPGA布局問題中的難點(diǎn)，一個問題是目前主要的布線擁塞的解決算法以靜態(tài)位置為主，但是在動態(tài)調(diào)整cell位置的過程中可能會引入了新的布線擁塞區(qū)域。

考慮時鐘布線的FPGA布局算法。由于FPGA特殊的時鐘布線結(jié)構(gòu)，近年來也有一些工作把布局算法的優(yōu)化方向放在時鐘布線的優(yōu)化上。當(dāng)前學(xué)術(shù)界主流算法[23–28]主要對每個時鐘信號求出可放置的一組時鐘區(qū)域，然后通過合法化或者以平滑化方式消除關(guān)于粗粒度的時鐘區(qū)域布線限制，然后在合法化和詳細(xì)布局階段完成細(xì)粒度的時鐘半列限制。文獻(xiàn)[26,27]分別提出通過“收縮-擴(kuò)張”算法和最大流匹配算法求出每個時鐘信號可放置的一組構(gòu)成矩形的時鐘區(qū)域，文獻(xiàn)[17,25,29]則提出在獲得每個時鐘信號可放置的時鐘區(qū)域后，通過2次罰函數(shù)法把時鐘布線加入優(yōu)化問題的目標(biāo)函數(shù)中，這種算法能以更加平滑化的方式優(yōu)化時鐘布線并獲得更好的布局質(zhì)量。除此以外，文獻(xiàn)[28]進(jìn)行了更加細(xì)粒度的初始時鐘布線，每個時鐘信號可以放置的時鐘區(qū)域構(gòu)成聯(lián)通的多邊形，因此該算法更加精細(xì)地擴(kuò)大了時鐘布線的可行解空間并能獲得更好的布局質(zhì)量。由于時鐘布線限制的高度離散性，當(dāng)前主要做法為在連續(xù)優(yōu)化過程中加入對時鐘信號可行區(qū)域的合法化過程，這種使用靜態(tài)限制的方法壓縮了可行解空間。

FPGA布局中的打包算法。打包算法可以分為直接打包、層次打包和非顯式打包3類。直接打包首先根據(jù)邏輯互連確定打包方案，然后依次進(jìn)行布局和合法化，以產(chǎn)生合法布局結(jié)果。然而，直接打包算法[30,31]在算法決策流程中缺乏邏輯單元的空間信息，因此結(jié)果質(zhì)量較差。層次打包算法[11,22,23]首先生成初始布局結(jié)果，然后結(jié)合邏輯單元的初始布局信息完成打包，并接著將打包后的邏輯單元視為整體繼續(xù)進(jìn)行布局。打包具有組合級、半CLB級和CLB級等層次，可以與布局算法交替進(jìn)行。層次打包在最終布局和合法化前可以結(jié)合邏輯互連和位置信息。非顯式打包算法[32]則直接在初始布局結(jié)果上完成打包和合法化，非顯式打包可以減少初始布局結(jié)果和最終布局結(jié)果之間的差異。最近，也有部分工作提出使用圖神經(jīng)網(wǎng)絡(luò)預(yù)測邏輯單元的打包概率[33]。

目前，基于非線性優(yōu)化算法的布局算法普遍能夠取得較好的布局效果，并且在可布線性、時鐘布線性等下游優(yōu)化任務(wù)以及使用異構(gòu)計算加速優(yōu)化算法上也已取得一定進(jìn)展。然而，仍然存在一些尚待解決的問題。在可布線性優(yōu)化方面，動態(tài)布線擁塞程度仍然是一個難點(diǎn)；由于時鐘布線約束的高度離散性，基于連續(xù)優(yōu)化算法的求解空間受到限制，這給求解優(yōu)化問題帶來更大的難度。

3.2 FPGA布線相關(guān)工作簡述

目前學(xué)術(shù)界現(xiàn)有的FPGA布線工具主要采用的是協(xié)商式的路徑搜索算法，其中具有代表性的算法為PathFinder算法[34]。對于每個線網(wǎng)，該算法會為該線網(wǎng)的每個扇出依次尋找一條從扇入到該扇出的布線路徑。在尋找到一個扇出的布線路徑時，該算法會將該扇出所屬線網(wǎng)的已有布線結(jié)果全部加入一個優(yōu)先隊列中，然后使用Dijkstra算法或A*算法等常用的路徑搜索算法來尋找路徑。在這樣得到的布線結(jié)果中，不同的線網(wǎng)的布線結(jié)果之間可能產(chǎn)生擁塞，因而該算法會對擁塞線網(wǎng)迭代地進(jìn)行拆線(ripup)和重布線(reroute)。在每次迭代開始時，該算法會檢查現(xiàn)有的布線結(jié)果中是否存在擁塞。對于存在擁塞的線網(wǎng)，該算法會將其布線結(jié)果刪除，也即相當(dāng)于將已有的布線結(jié)果“拆線”。然后，該算法會提高存在擁塞的布線資源的布線開銷，并對存在擁塞的線網(wǎng)進(jìn)行重布。

縮小搜索范圍。在拆線－重布過程中，AIR[35]和CRoute[36]都采用了只對具有擁塞的扇出引腳進(jìn)行重布的策略，縮小了布線搜索范圍，從而提高了布線效率。Zha等人[37]提出了一種重定義的布線開銷計算策略，從而減少在特定情況下布線擁塞產(chǎn)生的概率，減少了重布線的次數(shù)。AIR[35]中對于扇出較多的線網(wǎng)，會在對一個扇出布線時只將其周圍的布線結(jié)果加入優(yōu)先隊列中以減少搜索范圍。

并行加速布線。不少研究采用并行計算方法加速布線。文獻(xiàn)[38]使用GPU等異構(gòu)并行計算工具對單個線網(wǎng)進(jìn)行布線。文獻(xiàn)[39]對FPGA版圖進(jìn)行特定的劃分以同時布線多個線網(wǎng)。一般情況下，并行布線會以降低布線結(jié)果質(zhì)量為代價，換取布線時間的減少。

4 算法描述

OpenPARF的總體算法框架如圖2所示。該算法以電路網(wǎng)表和FPGA布局布線架構(gòu)信息為輸入，能夠自動輸出完整的布局布線結(jié)果。整個流程包括布局階段和布線階段兩個階段，具備SLICELSLICEM建模、布線擁塞預(yù)測和時鐘布線優(yōu)化的功能。OpenPARF可以支持工業(yè)級FPGA設(shè)計中常用的邏輯單元庫，包括LUT, FF, DSP, BRAM, IO以及具有SLICEL-SLICEM異構(gòu)性質(zhì)的DiRAM和SHIFT?？紤]到IO在FPGA芯片上的位置通常已經(jīng)固定，因此在布局階段只需考慮剩下的邏輯單元類型S={LUT, FF, DSP, BRAM, DiRAM, SHIFT}。在接下來的章節(jié)中，將對OpenPARF布局布線框架的主要功能進(jìn)行詳細(xì)介紹。

圖2 OpenPARF 總體算法框架圖

4.1 布局階段

根據(jù)FPGA的布局架構(gòu)和電路網(wǎng)表，本文提出一個基于非對稱多靜電場系統(tǒng)的FPGA布局器。在布局問題中，電路網(wǎng)表可以用超圖H=(V,E)表示，其中V表示所有邏輯單元組成的集合，E表示所有線網(wǎng)組成的集合，所有邏輯單元的橫縱坐標(biāo)用向量x和y表示。首先，布局器通過全局布局步驟同時優(yōu)化非線性目標(biāo)函數(shù)中的線長、非線性密度分布、布線擁塞以及時鐘布線等多個目標(biāo)。然后，合法化步驟生成符合時鐘布線約束和FPGA設(shè)計規(guī)則的合法布局結(jié)果。最后，OpenPARF在詳細(xì)布局階段微調(diào)邏輯單元的位置，以進(jìn)一步優(yōu)化線長。

4.1.1 基于多層拉格朗日松弛方法的全局布局算法

OpenPARF類似文獻(xiàn)[17,18]使用了非線性全局布局算法，同時考慮了線長、邏輯單元的分布密度、布線擁塞程度和時鐘可布線性等因素。具體而言，OpenPARF將全局布局問題建模為如式(1)的帶約束優(yōu)化問題

其中，OpenPARF采用了線長優(yōu)化目標(biāo)W(x;y)來優(yōu)化電路布線結(jié)果。線長優(yōu)化目標(biāo)被定義為所有線網(wǎng)的半周長線長(Half-Parimeter WireLength,HPWL)[40]之和。HPWL提供了路由線長的估計下限，在布局階段被廣泛用于估計路由線長。具體而言，線網(wǎng)的HPWL是由其所有引腳垂直/水平坐標(biāo)的最大值和最小值之差決定的。OpenPARF采用了WA(Weighted Average)模型[40]得到線長優(yōu)化目標(biāo)中的最大值和最小值函數(shù)的近似可導(dǎo)形式。這種近似可導(dǎo)形式的最大值和最小值函數(shù)使得目標(biāo)函數(shù)的導(dǎo)數(shù)可以使用標(biāo)準(zhǔn)的數(shù)值優(yōu)化方法來計算，從而加速了優(yōu)化過程。

在OpenPARF中，Φt(x;y;At)表示靜電場系統(tǒng)t(t ∈T) 的 電勢能，其定義類似于文獻(xiàn)[17]，T集合包括靜電場系統(tǒng)的所有類型。本文使用了非對稱的多電場模型來建模SLICEL-SLICEM的異構(gòu)性(見4.1.2節(jié))。靜電場系統(tǒng)將邏輯單元建模為帶電體，邏輯單元的重疊會導(dǎo)致靜電場的電勢能增加。優(yōu)化目標(biāo)是要盡可能降低電勢能，以減少邏輯單元之間的重疊程度，避免布線過于擁擠。通過最小化靜電場系統(tǒng)的電勢能，可以有效地避免邏輯單元之間的重疊，從而改善電路布線的質(zhì)量。

Γ(x;y)表示時鐘布線約束懲罰項(見4.1.3節(jié))。當(dāng)沒有違反時鐘布線限制時，懲罰項的值為零。當(dāng)違反時鐘布線限制時，懲罰項的值會增加。優(yōu)化目標(biāo)是盡可能減少懲罰項，將邏輯單元導(dǎo)向合法區(qū)域，并最終消除時鐘布線違規(guī)的情況。

上述約束條件體現(xiàn)了FPGA布局的物理限制，包括電路板的大小和形狀、標(biāo)準(zhǔn)單元之間的間距、布線擁塞程度和可時鐘路線性等因素。通過對目標(biāo)函數(shù)的優(yōu)化，OpenPARF可以同時考慮這些因素，從而得到更優(yōu)的布線結(jié)果。為了求解上述帶約束優(yōu)化問題，OpenPARF引入了無約束增廣拉格朗日函數(shù)L(x,y;λ,A,η)，其具體形式為

其中，Dt表 示類型t靜電場系統(tǒng)的拉格朗日項，包括其電勢能Φt的 1階項和2階項；ct用 于平衡Φt的1階項和2階項的大?。沪藅表示Dt的拉格朗日密度乘子；η表示拉格朗日時鐘乘子。

如式(3)和圖2所示，OpenPARF采用多層拉格朗日松弛方法求解拉格朗日函數(shù)的最優(yōu)化問題。該優(yōu)化框架從外向里依次優(yōu)化時鐘布線、布線擁塞、分布密度和線長。從整個優(yōu)化過程來看，這3個約束在嵌套的優(yōu)化迭代中逐漸增強(qiáng)。當(dāng)優(yōu)化過程完全收斂時，全局布局階段結(jié)束。對于時鐘和分布密度約束，OpenPARF引入了對應(yīng)的拉格朗日乘子η和λ，增加它們的值可以分別加強(qiáng)時鐘布線和密度限制

具體而言，在該多層拉格朗日松弛方法的優(yōu)化框架中，

(P1)首先，OpenPARF判斷是否滿足時鐘布線約束。如果未滿足時鐘布線約束，則更新時鐘乘子。OpenPARF利用時鐘布線分配算法更新時鐘罰函數(shù)項，同時增大時鐘乘子，增強(qiáng)時鐘布線約束限制，以使其符合布局布線架構(gòu)的要求。

(P2)其次，OpenPARF判斷是否存在布線擁塞問題。如果存在布線擁塞，則采用類似于文獻(xiàn)[20]的方法緩解路由擁塞。OpenPARF通過邏輯單元密度和RUDY算法[41]估計布線擁塞程度。如果當(dāng)前布線擁塞程度超過閾值，則調(diào)整邏輯單元面積(等效于調(diào)整電場模型中邏輯單元所帶的電荷量)，緩解布線擁塞問題，并增強(qiáng)可布線性限制。

(P3)接著，OpenPARF判斷邏輯單元密度是否小于給定的閾值。如果邏輯單元密度大于閾值，則增大密度乘子，增強(qiáng)對密度分布約束的限制，分散邏輯單元。

(P4)經(jīng)過上述步驟，時鐘可布線性、路由擁塞和邏輯單元重疊等問題都得到了良好的解決。Open-PARF使用內(nèi)思特羅夫動量法優(yōu)化線長，直到優(yōu)化問題完全收斂。最終，OpenPARF得到滿足時鐘布線約束、路由擁塞程度以及器件分布密度優(yōu)化的全局布局結(jié)果。

4.1.2 SLICEL-SCLIEM異構(gòu)性非對稱多電場模型

2.1節(jié)討論了SLCEL中的LUT資源可以被配置為LUT邏輯單元，SLICEM中的LUT資源可以分為LUT, DiRAM和SHIFT邏輯單元。由于SLICEL和SCLIEM具有不同的布局布線規(guī)則，在布局中要同時考慮這兩種Site之間的相互作用。OpenPARF采用了類似于文獻(xiàn)[17]的非對稱多電場模型，在多電場系統(tǒng)中引入了LUTL和LUTM-AL兩組靜電場系統(tǒng)。這兩組靜電場系統(tǒng)的設(shè)置目的是避免DiRAM或SHIFT邏輯單元被映射到SLCEL上，同時允許LUT邏輯單元放置到SLCEL和SLICEM上。

LUTL靜電場系統(tǒng)模擬SLCEL和SLICEM中提供的邏輯LUT資源，而LUTM-AL模擬SLICEM上提供的與存儲功能相關(guān)且在SLICEL上不存在的邏輯資源。與此對應(yīng)，邏輯單元LUT只占用LUTL靜電場系統(tǒng)中的資源，而邏輯單元DiRAM和SHIFT則同時占用LUTL和LUTM-AL靜電場系統(tǒng)中的資源。

圖3以LUT和SHIFT邏輯單元為例，分析了4個場景下兩者的位置關(guān)系。DiRAM邏輯單元的布局規(guī)則與SHIFT邏輯單元類似。由于SLCEL不包含LUTM-AL的資源，其初始LUTM-AL密度設(shè)置為1，表示它已被占用；LUTL的初始密度設(shè)置為0，表示在SLCEL上LUTL資源還沒有被占用。同樣地，由于SLICEM同時擁有LUTL和LUTM-AL資源，因此它們的初始密度都設(shè)置為0。在場景I和II中，LUT邏輯單元分別放置在SLICEL和SLICEM上，兩個靜電場系統(tǒng)中都沒有發(fā)生密度溢出，這意味著電勢能達(dá)到了最小值。場景III和IV中，SHIFT邏輯單元放置在SLICEL上，LUTM-AL靜電場系統(tǒng)發(fā)生密度溢出，表示靜電場系統(tǒng)的電勢能較高。優(yōu)化器通過最小化勢能來避免發(fā)生這樣的情況。這樣，這兩個靜電場系統(tǒng)可以自然引導(dǎo)LUT和DiRAM/SHIFT邏輯單元放置到合法的Site中。

圖3 4 種情景下的 LUT 和 SHIFT 的位置關(guān)系下 LUTL 和 LUTM-AL 靜電場系統(tǒng)的電荷密度和電勢能

4.1.3 2次罰函數(shù)時鐘懲罰項模型

OpenPARF采用文獻(xiàn)[27]中的算法來生成邏輯單元到可用時鐘區(qū)域的映射。這種方法保證了生成的映射不僅符合時鐘布線限制，還可以降低線長擾動。這些映射被用來確定邏輯單元與可用時鐘區(qū)域之間的關(guān)系。在該映射的基礎(chǔ)上，OpenPARF定義了增廣拉格朗日函數(shù)中的時鐘布線約束懲罰項Γ(x,y)，該懲罰項的值等于所有邏輯單元時鐘布線約束懲罰項之和。假設(shè)邏輯單元i可用的時鐘區(qū)域集合為wt， 且wt的邊界框的左部、右部、底部和頂部邊界坐標(biāo)分別為： loxi,h ixi,l oxi和h iyi。邏輯單元i的時鐘布線約束懲罰項等于x軸方向和y軸方向的懲罰項之和

其中，x軸方向上懲罰項Γ(xi,yi)x為

xi和yi為 器件i的橫縱坐標(biāo)，y軸方向上的時鐘懲罰定義類似。邏輯單元i的時鐘布線約束懲罰項是一個以合法區(qū)域為中心的2次勢阱函數(shù)。當(dāng)邏輯單元在合法區(qū)域中時，懲罰項為零。否則，懲罰項的值會增加，并在梯度更新過程中將邏輯單元導(dǎo)向合法區(qū)域，這樣就可以消除時鐘布線違規(guī)的情況。

4.1.4 考慮時鐘布線的合法化與詳細(xì)布局

在全局布局階段后，OpenPARF對全局布局結(jié)果執(zhí)行合法化步驟來獲得一個沒有標(biāo)準(zhǔn)單元重疊、滿足FPGA布局布線架構(gòu)規(guī)則且路由擁塞程度得到優(yōu)化的布局結(jié)果，并在此步驟中盡可能減少對全局布局結(jié)果的擾動。在這個步驟中，OpenPARF類似于文獻(xiàn)[32]進(jìn)行初步合法化，接著采用并行college-student Admission策略更新邏輯單元的組合關(guān)系，最后得到合法的布局結(jié)果。

最后，在詳細(xì)布局階段，OpenPARF采用基于最大獨(dú)立集的匹配算法[32]，在合法化的結(jié)果基礎(chǔ)上微調(diào)邏輯單元的位置，以進(jìn)一步優(yōu)化線長。在這個階段中，布局器會生成遵守FPGA布局布線架構(gòu)規(guī)則和時鐘布線約束的詳細(xì)布局結(jié)果。

4.2 布線階段

在布線階段，OpenPARF提出了一個BEL級別的兩階段布線器[39]。布線器以布局階段的結(jié)果和FPGA布線架構(gòu)作為輸入，生成最終的布線結(jié)果。該布線器主要包含全局布線和詳細(xì)布線兩個階段。在全局布線階段，布線器生成跨Tile級別的粗粒度布線結(jié)果，用于指導(dǎo)詳細(xì)布線。在詳細(xì)布線階段，布線器以粗粒度布線結(jié)果作為布線區(qū)域引導(dǎo)，生成BEL級別的最終布線結(jié)果。

在進(jìn)行全局布線和詳細(xì)布線的過程中，布線器借助布線資源圖(Routing Resourse Graph, RRG)建模FPGA的布線架構(gòu)。RRG是一幅有向圖G(V,E)。 其中結(jié)點(diǎn)v∈V表示FPGA中的一個布線資源，并且在全局布線階段和詳細(xì)布線階段分別表示不同粒度的布線資源；有向邊(u,v)∈E表示FPGA中的路由通道，表示邏輯信號可以從布線資源u傳輸?shù)讲季€資源v。

布線器的核心是基于協(xié)商式的PathFinder算法[34]。算法迭代應(yīng)用A*路徑搜索算法，得到合法的布線結(jié)果。在每次迭代開始時，布線器檢查上一次迭代的布線結(jié)果。對存在擁塞的布線資源，布線器提高其布線開銷，同時拆除占用該布線資源的線網(wǎng)布線結(jié)果。在全局布線階段和詳細(xì)布線階段，Open-PARF采用了不同的開銷評估函數(shù)來評估布線資源的布線開銷。

4.2.1 全局布線

在全局布線階段，布線器的目標(biāo)是生成跨Tile級別的粗粒度布線結(jié)果，用于指導(dǎo)詳細(xì)布線。大部分來自學(xué)術(shù)界的FPGA布線器直接生成詳細(xì)布線結(jié)果。相較而言，OpenPARF加入了全局布線的步驟，以減少在詳細(xì)布線中可能出現(xiàn)的擁塞問題。在沒有全局布線結(jié)果的指導(dǎo)下進(jìn)行詳細(xì)布線會導(dǎo)致大量的擁塞，進(jìn)而降低了布線器在求解時的效率。隨著FPGA布線架構(gòu)復(fù)雜度的提升，這種情況尤其顯著。

全局布線中開銷評估函數(shù)的優(yōu)化目標(biāo)是引導(dǎo)線網(wǎng)的走線避開擁塞區(qū)域，并為詳細(xì)布線預(yù)留充足的布線資源。OpenPARF將FPGA布線架構(gòu)建模為一個RRG格點(diǎn)圖。在RRG格點(diǎn)圖中，結(jié)點(diǎn)代表FPGA架構(gòu)中的Tile；邊代表Tile之間的互聯(lián)軌道，邊容量為對應(yīng)的軌道寬度。邊布線開銷的初始值為Tile之間的曼哈頓距離。在此RRG格點(diǎn)圖中，線網(wǎng)的扇入扇出為其所在的Tile。

在RRG格點(diǎn)圖構(gòu)建完成后，全局布線器使用PathFinder算法來對跨Tile線網(wǎng)進(jìn)行布線。在路徑搜索過程中，全局布線器采用如下的開銷評估函數(shù)來計算從結(jié)點(diǎn)u擴(kuò)展到結(jié)點(diǎn)v的布線開銷

其中，p rev(v)表 示已搜索路徑的總布線開銷；pred(v)表示當(dāng)前線網(wǎng)從待擴(kuò)展結(jié)點(diǎn)到扇出結(jié)點(diǎn)的預(yù)測布線開銷，其值等于待擴(kuò)展結(jié)點(diǎn)到扇出結(jié)點(diǎn)的曼哈頓距離。隨著布線的進(jìn)行，邊容量會隨著線網(wǎng)對布線資源的占用而逐漸下降。為了避免造成詳細(xì)布線階段的擁塞，全局布線器會隨著邊容量的下降逐步提高邊的布線開銷。

4.2.2 詳細(xì)布線

在全局布線結(jié)果的指導(dǎo)下，詳細(xì)布線器的目標(biāo)是生成BEL級別的布線結(jié)果。與全局布線器相比，詳細(xì)布線器更加關(guān)注跨Tile級別的擁塞。在詳細(xì)布線階段，OpenPARF將布線架構(gòu)建模成細(xì)粒度的RRG。在該RRG中，結(jié)點(diǎn)代表邏輯引腳；邊代表邏輯引腳之間的連接關(guān)系。通常情況下，每個邏輯引腳只能用于布線一個線網(wǎng)，因此大多數(shù)結(jié)點(diǎn)和邊的容量都為1。同時由于每個線網(wǎng)的扇入和扇出都是一個邏輯引腳，因此可以很容易地在RRG中找到對應(yīng)的結(jié)點(diǎn)。

詳細(xì)布線器的目標(biāo)是為每個線網(wǎng)找到一條從扇入結(jié)點(diǎn)到扇出結(jié)點(diǎn)的布線路徑，并避免擁塞情況的發(fā)生。詳細(xì)布線器與全局布線器均基于PathFinder算法，但由于詳細(xì)布線階段的RRG規(guī)模更大、連接關(guān)系更復(fù)雜，OpenPARF采用(1)擁塞驅(qū)動布線開銷計算、(2)引腳融合與交換、(3)搜索空間大小控制和(4)擁塞驅(qū)動布線排序策略來優(yōu)化詳細(xì)布線器。

擁塞驅(qū)動布線開銷計算。詳細(xì)布線器采用以下?lián)砣?qū)動的開銷評估函數(shù)來計算從結(jié)點(diǎn)u擴(kuò)展到結(jié)點(diǎn)v的布線開銷

其中，參數(shù)p在每次迭代都會乘以預(yù)先設(shè)定好的參數(shù)pc。參數(shù)p越大，詳細(xì)布線器就會更專注于解決布線時產(chǎn)生的擁塞。

o(v)表 示當(dāng)前結(jié)點(diǎn)v被使用后，其容量會超出多少。

b(v)代 表結(jié)點(diǎn)v的基礎(chǔ)布線開銷。對于大多數(shù)結(jié)點(diǎn)來說，它們的基礎(chǔ)開銷是相同的。但是，在構(gòu)造RRG時，對于一些可能產(chǎn)生擁塞的結(jié)點(diǎn)，詳細(xì)布線器會提高其基礎(chǔ)開銷以在一定程度上避免擁塞的發(fā)生。

h(v)代表結(jié)點(diǎn)的歷史擁塞開銷。在迭代拆線過程中，詳細(xì)布線器根據(jù)結(jié)點(diǎn)的歷史擁塞情況提高其歷史擁塞開銷。

w(u,v)代表邊布線開銷，其由邊類型決定。Tile內(nèi)部的邊布線開銷在構(gòu)造RRG時會被固定初始化；跨Tile的邊布線開銷初始化為Tile之間的曼哈頓距離。

引腳融合與交換。LUT是FPGA架構(gòu)中最常見的邏輯單元。LUT通常是多輸入/輸出引腳的，然而這些引腳是邏輯不等價，因此連接到這些引腳的互聯(lián)軌道也是不等價的，這會使得布線器更難找到合法的布線結(jié)果。OpenPARF采取了“融合-交換”策略來處理該問題。具體而言，在布線時，Open-PARF將這些引腳合并為一個容量更大的節(jié)點(diǎn)，然后在引腳融合后的RRG上進(jìn)行詳細(xì)布線。然而，這樣做可能會改變線網(wǎng)信號連接的引腳，導(dǎo)致邏輯功能不正確。因此在完成詳細(xì)布線后，Open-PARF再進(jìn)行CLB級別的引腳交換(等價于重新設(shè)計LUT的真值表)來修正邏輯功能，從而確保了LUT邏輯功能的正確性。

搜索空間大小控制。OpenPARF基本上以全局布線結(jié)果為指導(dǎo)進(jìn)行搜索，在搜索線網(wǎng)路徑時只會搜索處于全局布線結(jié)果范圍內(nèi)的結(jié)點(diǎn)。這種方法可以有效控制搜索空間，加速布線進(jìn)程。但是，僅在全局布線結(jié)果范圍內(nèi)的搜索可能無法消除局部擁塞。因此，每經(jīng)過若干輪迭代，詳細(xì)布線器在拆解擁塞結(jié)點(diǎn)所在的布線路徑時，將該擁塞結(jié)點(diǎn)周圍的Tile添加到搜索空間中。通過適度增加搜索空間，詳細(xì)布線器可以更快地找到合法的布線路徑。

布線順序。在每次迭代開始之前，詳細(xì)布線器需要確定線網(wǎng)的布線順序。OpenPARF優(yōu)先對覆蓋面積大且在之前布線過程中產(chǎn)生了大量擁塞的線網(wǎng)進(jìn)行布線，從而更快地消除布線擁塞。

5 實驗設(shè)置與結(jié)果分析

OpenPARF基于pybind11實現(xiàn)C++/Python混合開發(fā)，結(jié)合了Python的靈活性和C++的高效性。在深度學(xué)習(xí)框架PyTorch的基礎(chǔ)上，Open-PARF對全局布局的梯度計算進(jìn)行了GPU加速[17]。在實現(xiàn)過程中，本文基于PyTorch的GPU張量管理功能實現(xiàn)了GPU內(nèi)存管理、快速張量運(yùn)算和自定義運(yùn)算算子。此外，本文還利用PyTorch的自動求導(dǎo)功能實現(xiàn)了GPU加速的梯度計算。關(guān)于線長和密度模型的具體計算和實現(xiàn)細(xì)節(jié)請參考文獻(xiàn)[17, 20]。本文在一臺配備Intel Xeon Gold 6230 CPU(頻率2.10 GHz, 40核)、512 GB內(nèi)存和一塊NVIDIA RTX 2080Ti GPU的Linux服務(wù)器上進(jìn)行了實驗，并在3個數(shù)據(jù)集上進(jìn)行了驗證，包括ISPD 2016 FPGA可布線性驅(qū)動FPGA布局?jǐn)?shù)據(jù)集[6]、ISPD 2017時鐘布線驅(qū)動FPGA布局?jǐn)?shù)據(jù)集[9]和工業(yè)標(biāo)準(zhǔn)級FPGA數(shù)據(jù)集。其中，工業(yè)標(biāo)準(zhǔn)級FPGA數(shù)據(jù)集由工業(yè)界的合作方提供，并在其指導(dǎo)下，補(bǔ)全了前兩個ISPD競賽數(shù)據(jù)集的布線架構(gòu)。表1和表2詳細(xì)介紹了這3個數(shù)據(jù)集的邏輯單元庫和電路網(wǎng)表的規(guī)模。數(shù)據(jù)集包括21k～1 100k的不同規(guī)模的實例數(shù)量和網(wǎng)表大小。

表1 ISPD2016 和 ISPD2017 benchmark 的實例數(shù)量和網(wǎng)表數(shù)量

表2 在工業(yè)標(biāo)準(zhǔn)級 FPGA 數(shù)據(jù)集上的布局時間 (s)、布線時間(min)以及布線線長 (×103)

5.1 ISPD競賽數(shù)據(jù)集實驗結(jié)果

表3和表4展示了OpenPARF與其他布局算法RippleFPGA[23]和DREAMPlaceFPGA[19]的對比結(jié)果。其中，RippleFPGA和DREAMPlaceFPGA1)DREAMPlaceFPGA包括文獻(xiàn)[18,19]兩個工作，其中文獻(xiàn)[19]在文獻(xiàn)[18]的基礎(chǔ)上使用GPU加速合法化算法。本文實驗部分中DREAMPlaceFPGA的布局時間摘取自文獻(xiàn)[19]。分別代表了基于二次規(guī)劃和非凸優(yōu)化模型的效果最好的解析式布局算法。本文將其他布局算法的布局結(jié)果導(dǎo)入OpenPARF的布線器中進(jìn)行布線，并比較了布線后線長和運(yùn)行時間。

表4 在ISPD 2017 benchmark上的布局時間 (s) 、布線時間 (min)以及布線線長 (×104 )的比較

ISPD 2016上的實驗結(jié)果表明，OpenPARF相較于其他布局算法，分別減少了12.7%和0.4%的線長，并獲得了2.771倍的加速。DREAMPlaceFPGA對合法化進(jìn)行了GPU加速優(yōu)化。與DREAMPlace-FPGA相比，OpenPARF慢了21.4%。本文認(rèn)為，OpenPARF未來可以通過探索使用異構(gòu)并行加速合法化和詳細(xì)布局來進(jìn)一步提高性能。

在ISPD2017數(shù)據(jù)集上，本文對比了RippleFPGA與OpenPARF的布局布線時間和布線線長。由于DREAMPlaceFPGA目前不支持ISPD2017的時鐘布線約束，因此無法在該數(shù)據(jù)集上比較結(jié)果。實驗結(jié)果表明，相比RippleFPGA, OpenPARF減少了12.5%的布線線長，并獲得了2.251倍的加速。該實驗進(jìn)一步證明本框架在復(fù)雜約束下仍能實現(xiàn)更優(yōu)秀的布線結(jié)果。

本文進(jìn)一步在ISPD2016和ISPD2017數(shù)據(jù)集上比較使用CPU多線程加速2)本文實驗中線程數(shù)為8(OpenPARF(CPU))和GPU加速(OpenPARF(GPU))的實驗結(jié)果。在ISPD2016和ISPD2017數(shù)據(jù)集上，OpenPARF(CPU)和OpenPARF(GPU)均得到相近的路由線長。但與此同時，OpenPARF(CPU)的布局時間大于使用CPU的RippleFPGA。這主要是因為，Open-PARF使用基于非線性優(yōu)化算法的布局算法，其計算量大于使用基于2次規(guī)劃算法的RippleFPGA。

本文進(jìn)一步比較了各工作布局結(jié)果的布線時間，以衡量布局結(jié)果的布線擁塞程度。表3和表4的實驗結(jié)果表明， OpenPARF在ISPD2016和ISPD-2017數(shù)據(jù)集上的布線時間分別比RippleFPGA減少了12.7%和3.7%，并且布線時間與DREAMPlace-FPGA相當(dāng)。這說明OpenPARF在獲得更優(yōu)布線線長的同時，布線擁塞程度遠(yuǎn)小于RippleFPGA，并與學(xué)術(shù)界領(lǐng)先的布局算法DREAMPlaceFPGA持平。這一結(jié)果證明了OpenPARF在可布線性優(yōu)化能力方面的卓越表現(xiàn)。

5.2 工業(yè)級FPGA數(shù)據(jù)集實驗結(jié)果

表2展示了OpenPARF在工業(yè)標(biāo)準(zhǔn)級FPGA數(shù)據(jù)集上的布局布線時間和布線線長。工業(yè)標(biāo)準(zhǔn)級FPGA數(shù)據(jù)集包括具有SLICEL-SLICEM異構(gòu)性質(zhì)的DiRAM和SHIFT邏輯單元。實驗結(jié)果表明，OpenPARF在處理SLICEL-SLICEM約束時表現(xiàn)出優(yōu)秀的性能和效率。SLICEL和SLICEM作為FPGA中兩種不同的Site，由于其具有不同的物理結(jié)構(gòu)和電學(xué)性質(zhì)，在設(shè)計中要同時考慮這兩種Site之間的相互作用。OpenPARF通過非對稱多電場系統(tǒng)建模處理該問題，取得了積極的成效。

6 結(jié)束語

本文提出一個面向大規(guī)模FPGA的開源布局布線框架OpenPARF。本框架基于深度學(xué)習(xí)工具包PyTorch實現(xiàn)，支持CPU平臺運(yùn)行和GPU加速。本框架在布局和布線算法方面采用了新型非對稱多電場系統(tǒng)和多階段優(yōu)化策略，以應(yīng)對FPGA復(fù)雜的布局布線架構(gòu)和邏輯單元引腳不等價等場景。在布局階段，OpenPARF將時鐘布線、可布線性、密度分布和線長優(yōu)化統(tǒng)一建模為拉格朗日優(yōu)化問題，并使用內(nèi)斯特羅夫動量法求解。在布線階段，框架提出了全局布線和詳細(xì)布線兩階段策略，并采用了多種優(yōu)化方法提升布線器效率，從而實現(xiàn)邏輯單元級別的布線。OpenPARF為下一代高性能FPGA布局布線算法的探索和開發(fā)提供了一個重要的基準(zhǔn)。未來，將進(jìn)一步考慮優(yōu)化布局布線過程中的擁塞和時序性能，并針對FPGA的規(guī)整布局布線結(jié)構(gòu)研究更加準(zhǔn)確的線長估計方法。