基于深度學習的FPGA快速布局算法

劉 偉，王伶俐，周 灝

(復旦大學 專用集成與系統(tǒng)電路國家重點實驗室，上海 201203)

現(xiàn)今，現(xiàn)場可編程門陣列(Field Programmable Gate Array, FPGA)作為一個可重構平臺得到越來越廣泛的應用.為滿足實際的需要，Xilinx和Intel公司最新的芯片包含近百萬個邏輯單元塊.隨著電路規(guī)模和復雜度的提升，在FPGA的整個計算機輔助設計流程中，布局占據(jù)近49%[1]的運行時間，這直接影響到FPGA的使用效率.

FPGA布局是NP(Non-deterministic Polynomial)完全的組合優(yōu)化問題[2]，對于一塊給定的FPGA芯片，對打包流程之后的電路網(wǎng)表中的每一個邏輯單元塊進行位置選擇，以實現(xiàn)最終關鍵路徑延時最小和線長的最優(yōu).總體來說，布局算法有3類： 第1類為啟發(fā)式算法，典型的代表就是VPR(Versatile Place Route)[3]中使用的模擬退火算法，它基于交換的方式實現(xiàn)對線長和關鍵路徑的優(yōu)化.雖然這一類方法能夠得到比較理想的布局結果，但是處理大規(guī)模電路布局時，需要非常長的運行時間；第2類是基于劃分的布局算法，如PPFF[4]，它將一個大的電路布局問題分解為更多的子問題，從而降低了電路計算的復雜度，但是該算法在性能上會帶來非常大的關鍵路徑延時損失；第3類是解析法，如QPF[5]，CAPRI[6]，StarPlace[7]，這也是目前Xilinx商業(yè)計算機輔助設計軟件中使用的布局算法.解析法是目前綜合表現(xiàn)最優(yōu)的算法，在接近于VPR布局結果的情況下通常能夠實現(xiàn)布局速度3～8倍的提升.

針對基于模擬退火的VPR布局算法的優(yōu)化主要分為3類.第1類是提供更精確的目標函數(shù)，如采用基于路徑的時序分析模型或者引入擁擠度矩陣為每一次交換提供更高質(zhì)量的結果.但是在大規(guī)模電路指數(shù)級增長的交換次數(shù)前提下，VPR布局階段使用的半周長線網(wǎng)框模型和最小延時時序矩陣是相對理想的選擇.第2類則是尋找更高效的策略如初始化布局、自適應退火表、交換邏輯單元的選擇以及交換的目標區(qū)域選擇等.模擬退火算法交換過程中隨著溫度的降低交換范圍逐漸縮小，RBSA[8]采用線網(wǎng)中心而不是邏輯單元塊的中心指定交換范圍產(chǎn)生交換策略，在不損失關鍵路徑延時的情況下運行速度提升一倍.第3類是采用并行策略對模擬退火算法進行加速，文獻[9]中在小規(guī)模電路中實現(xiàn)64線程下運行加速提升34倍，線長損失平均為1.7%，關鍵路徑延時損失為0.6%，但是該并行策略并沒有在大規(guī)模電路中有效地實現(xiàn).所以目前對于基于模擬退火的FPGA布局算法，在處理大規(guī)模電路時難以得到一個快速而且比較理想的布局結果.

深度學習[10]與傳統(tǒng)的機器學習方法不同，在模型深度上擴展，分層地進行學習并將上層學習到的特征作為下層的輸入，實現(xiàn)由低階到高階的特征提取.深度學習已經(jīng)廣泛應用于視覺，文本識別、機器人、人工駕駛、游戲、醫(yī)療等諸多領域.文獻[11]使用機器學習算法對FPGA布局結果進行布線擁擠度的預測，相較于傳統(tǒng)的VPR中使用的擁擠度預測方法，在近乎準確的擁擠度預測情況下實現(xiàn)了291倍的運行速度提升.本文基于深度學習處理FPGA布局這樣的NP完全組合優(yōu)化問題，實現(xiàn)了布局速度的極大提升.

1 模型思想

本文模型有別于基于傳統(tǒng)的3類布局算法，由底層到頂層的方式逐步進行布局.在每一次邏輯單元塊的選擇和邏輯單元塊位置確定的過程中，需要動態(tài)地提取當前布局階段的狀態(tài)信息，為下一次決策做準備.采用訓練好的深度學習網(wǎng)絡，將對應的狀態(tài)信息作為網(wǎng)絡輸入，實現(xiàn)對下一個邏輯單元塊的位置確定，最后使用基于交換的快速詳細布局算法進行優(yōu)化.狀態(tài)信息的提取和網(wǎng)絡模型的訓練在模型實現(xiàn)中詳細介紹.

2 模型實現(xiàn)

2.1 FPGA結構

深度學習模型的訓練針對是VPR中一種通用的FPGA芯片描述k4_n4_v7_bidir.xml，芯片的核心部分由可配置邏輯塊陣列(Configurable Logic Block, CLB)和全局布線資源組成.如圖1所示，每個可配置邏輯單元由4個基礎邏輯單元(Basic Logic Element, BLE)組成，每個BLE包含一個4輸入查找表(Look-Up Table, LUT)和可配置D觸發(fā)器.FPGA全局布線資源中線長為4，CLB通過連接盒與全局布線資源連接.

2.2 電路網(wǎng)表解析

圖1 可配置邏輯塊結構Fig.1 Architecture of CLB

電路網(wǎng)表的解析用于邏輯單元塊的選擇和邏輯單元塊的位置確定.打包之后的電路網(wǎng)表中的結點不僅包括可配置邏輯塊等邏輯單元塊的輸入輸出端口的信號結點(外部結點)，也包含可配置邏輯塊內(nèi)部如LUT4和D觸發(fā)器輸出端口的信號結點(內(nèi)部結點).初始化時，不考慮結點之間的延時，對電路網(wǎng)表中的所有結點進行拓撲排序，對所有結點進行遍歷之后，可以確定決定每一個結點最長路徑的輸入結點.在對網(wǎng)表進行解析的過程中保留確定所有結點最長路徑的路徑，超圖的連接由此解析為所有結點組成的森林，每個結點都在森林中的一棵樹中.布局過程中，采用VPR中的布局階段延時模型對已布局電路的結點延時和路徑延時進行分析，樹中父子結點的關系由延時模型計算得到的最大延時確定，所以在周期性的更新過程中，動態(tài)的布局過程也伴隨電路網(wǎng)表解析森林中父子結點連接關系的變化.

圖2所示即是經(jīng)過拓撲排序之后的一個電路網(wǎng)表.圖中實線和虛線都是網(wǎng)表中不同結點的連接，實線為確定該線輸出端點最長路徑的路徑，從圖中可以看出拓撲排序之后的網(wǎng)表形成了由3棵樹組成的森林，每棵樹由橢圓內(nèi)的結點和實線連接組成.

在算法的動態(tài)的布局過程中，動態(tài)的網(wǎng)表解析過程如表1所示.首先在布局開始之前進行拓撲排序，排序之后保留確定每個網(wǎng)表中結點最長路徑的路徑，從而將電路解析為森林.隨后布局的實現(xiàn)過程中，在每次布局單個邏輯單元塊之后對當前電路中已布局的部分網(wǎng)表進行時序更新，如圖3描述的是布局的中間過程，此時已經(jīng)處理到網(wǎng)表中的A，B，C，D，E，G，J結點，與之前分析不同的是每條路徑對應有相應延時計算值，此時結點J的最長路徑延時由CJ之間的路徑確定.受運行時間的影響，時序更新之后，網(wǎng)表的動態(tài)解析條件由第10行確定，在本文具體實現(xiàn)中Every_Iteration_times取值0.01，Threshold_time_update取值1.10.

圖2 初始化網(wǎng)表解析Fig.2 Initialization of netlist parser

圖3 動態(tài)網(wǎng)表解析Fig.3 Dynamic netlist parser

輸入: 電路網(wǎng)表Netlist,P為網(wǎng)表邏輯單元塊數(shù)量輸出: 電路網(wǎng)表解析數(shù)據(jù)結構對網(wǎng)表Netlist中結點進行拓撲排序保留確定每個網(wǎng)表中結點最長路徑的路徑∥布局過程中動態(tài)更新網(wǎng)表解析過程,Last_Update用于記錄上次動態(tài)更新網(wǎng)表解析到當前階段布置邏輯單元塊的數(shù)目∥Last_Critical_Time用于記錄上次動態(tài)更新網(wǎng)表解析時最長路徑的延時,Critical_Time為當前階段最長路徑延時For j←P to 0 do 調(diào)用訓練好的深度模型進行布局 更新已布局部分網(wǎng)表中結點和路徑延時,結點中最大延時值為Critical_Time if(Last_Update>Every_Iteration_times×P) or (Critical_Time/Last_Critical_Time)>Threshold_time_update 更新確定每個網(wǎng)表中結點最長路徑的路徑 Last_Update=0,Last_Critical_Time=Critical_Time else Last_Update=Last_Update+1 End ifEnd For

2.3 深度學習模型

訓練模型的建立主要包括數(shù)據(jù)的提取、深度學習網(wǎng)絡結構的確定、特征的選取3部分.

2.3.1 數(shù)據(jù)的提取

數(shù)據(jù)由兩類電路網(wǎng)表產(chǎn)生： 一部分數(shù)據(jù)由基于PEKO[12]的最優(yōu)線長電路生成器產(chǎn)生，該電路生成器中每個邏輯單元塊的位置都是線長最優(yōu)的；另一部分數(shù)據(jù)是由隨機化電路生成器產(chǎn)生.由于VPR采用的模擬退火算法通常能夠得到較好的布局結果，所以對于隨機化電路網(wǎng)表將模擬退火算法布局得到的邏輯單元塊的位置作為深度學習模型訓練的理想標簽.

最優(yōu)線長電路是普通電路的一種特例，也是一種理想情況.根據(jù)VPR中線網(wǎng)框計算方法，對于有N個端點的線網(wǎng)，將其所連接的N個邏輯單元塊限定在包含該邏輯單元塊的最小的矩陣框范圍內(nèi)能夠實現(xiàn)周長最小的線網(wǎng)框，從而得到最小線長.對于所有的線網(wǎng)都找到最小的線網(wǎng)框從而得到最優(yōu)線長的布局結果[13].雖然與通常的基準電路不同，最優(yōu)線長電路網(wǎng)表中邏輯單元塊之間簡單的連接，以及最優(yōu)位置的確定更有利于深度學習模型的訓練.PEKO算法確定的是邏輯單元塊之間的外部線網(wǎng)，以達到線長最優(yōu).最優(yōu)線長電路網(wǎng)表生成器在PEKO基礎上產(chǎn)生適用于FPGA芯片描述k4_n4_v7_bidir.xml的電路網(wǎng)表.表2(見第690頁)為最優(yōu)線長電路網(wǎng)表生成器的偽代碼，P為網(wǎng)表邏輯單元數(shù)量，Archclb為邏輯單元塊結構.如表中所示，為產(chǎn)生不同的電路網(wǎng)表，一方面需要根據(jù)結構產(chǎn)生不同的電路網(wǎng)表參數(shù)如Inave,Outave,Dffave，Distri以及對應于每個邏輯單元塊的Lutnum和Dffnum，另一方面需要在合法連接的前提下實現(xiàn)全局互連以及邏輯單元內(nèi)部互連的隨機性.隨機化電路網(wǎng)表生成器不同之處在于： 在選擇每一條線網(wǎng)所連接的邏輯單元塊時，不是根據(jù)半周長線網(wǎng)框模型選擇包含該線網(wǎng)所連接邏輯單元塊的最小矩陣，而是隨機性的選擇任意大小和任意位置的線網(wǎng)框，并最終在該線網(wǎng)框選擇確定數(shù)量的任意邏輯單元塊.

表2 最優(yōu)線長電路網(wǎng)表生成器偽代碼

2.3.2 深度學習的網(wǎng)絡結構

深度學習采用的是殘差網(wǎng)絡，實驗中證明，在深度網(wǎng)絡的訓練中，殘差塊能夠加速收斂并提高訓練效果.整個網(wǎng)絡結構由輸入層、20個中間層(殘差塊)和輸出層組成.中間層(殘差塊)及參數(shù)如圖4所示，殘差塊的第一層的輸入被加入到最后一層的輸出中，其內(nèi)部包含由批歸一化和激活函數(shù)隔離的卷積層.輸入層同樣使用類似殘差塊結構，如圖5所示，卷積核的大小分別為[5,5]與[1,1]，卷積層之后的輸出進行相加.輸出層卷積層中卷積核大小為[3,3]，輸出層的大小為[100,100，1]，輸出層經(jīng)過softmax層后得到的是邏輯單元塊位于資源陣列中各個位置的概率分布.

圖4 殘差塊Fig.4 Residual block

圖5 殘差輸入層Fig.5 Residual input layer

2.3.3 特征提取

布局過程中已經(jīng)被選擇并且確定位置的邏輯單元塊稱為已布邏輯單元塊，被選出來并且即將由訓練好的深度學習模型進行位置預測的邏輯單元塊稱為待布邏輯單元塊，目前未被選擇的邏輯單元塊稱為未布邏輯單元塊.特征提取的思想是在動態(tài)布局過程中，統(tǒng)計FPGA資源陣列中每個坐標位置可供使用的邏輯單元塊資源(總的邏輯單元塊資源與已布邏輯單元塊資源之差)和每個坐標位置附近需求的邏輯單元塊資源，并根據(jù)提取的時序和線長信息對待布邏輯單元塊進行位置的確定.

特征一(f1)： FPGA資源陣列.該特征記錄FPGA芯片的總邏輯資源，包含F(xiàn)PGA芯片映射的FPGA資源陣列以及每個坐標位置所包含的邏輯單元塊數(shù)量.

特征二(f2)： 已布邏輯單元塊占用資源.該特征動態(tài)記錄FPGA資源陣列中每個坐標位置上已布的邏輯單元塊數(shù)目.最大值為特征一中對應坐標位置的值.特征二與特征一的差值即是每個坐標位置可供使用的邏輯單元塊資源數(shù)目.

特征三(f3)： 線網(wǎng)連接數(shù)量.線網(wǎng)連接記錄坐標位置已布邏輯單元塊與待布邏輯單元塊線網(wǎng)連接的數(shù)量，線網(wǎng)的統(tǒng)計包含了直接相連和跨一級相連(在一條路徑中，隔一個中間結點實現(xiàn)相連).

特征四(f4)： 線長代價.根據(jù)半周長線網(wǎng)框的線長計算方法，對于待布邏輯單元塊中輸入輸出端線網(wǎng)(線網(wǎng)已出現(xiàn)在已布邏輯單元塊或該待布邏輯單元塊中)，提取待布邏輯單元塊位于不同位置時對線長的影響.

(1)

特征六(f6)： 時序信息特征.時序部分特征包含多個子特征.時序優(yōu)化作為VPR中時序驅動模擬退火算法的主要目標，是決定布局結果的關鍵.本文中時序部分信息的提取采用了VPR布局中的延時模型.

1) 結點時序最大值.結點時序最大值表示FPGA資源陣列的坐標位置上已布邏輯單元塊的所有結點中最長延時的最大值.

圖6 源結點需求的邏輯單元塊數(shù)量Fig.6 Source node’s demand of logic elements

2) 輸入端線網(wǎng)源端時序值.該特征提取待布邏輯單元塊輸入端線網(wǎng)源端結點的最長延時，與結點時序最大值特征考慮全局時序信息不同的是，該特征考慮局部與待布邏輯單元塊輸入端直接相連的時序信息.

3)輸出端線網(wǎng)漏端時序值.該特征提取待布邏輯單元塊輸出端線網(wǎng)漏端結點的最長延時.

在FPGA資源陣列的每個特征中，無效或者沒有實際值的坐標位置都取值為0，當FPGA資源陣列的坐標位置包含多個邏輯單元塊時，各個特征在該坐標位置的取值為與各個邏輯單元塊對應特征值的平均值.

2.4 待布邏輯單元塊的選擇

表3 FPGA的簇映射

隨著布局過程的進行需要動態(tài)選擇下一個待布的邏輯單元塊.根據(jù)PEKO思想，一個好的布局結果，傾向于將線網(wǎng)連接的邏輯單元塊布局緊湊[9,13]，所以將在FPGA資源陣列中坐標位置靠近的多組邏輯單元塊集合為一個邏輯單元簇.如表3所示為FPGA有效資源陣列參數(shù)n大小與選取的邏輯單元簇大小的對應關系，確定了邏輯單元簇大小之后，F(xiàn)PGA資源陣列映射后得到的FPGA簇陣列的陣列規(guī)模也如表中所示.對FPGA簇陣列中每個坐標位置計算未布邏輯單元塊中與對應邏輯單元簇范圍內(nèi)已布邏輯單元塊親密度加權和最大的邏輯單元塊.每次選擇所有簇中與簇內(nèi)邏輯單元塊親密度最大的邏輯單元塊作為待布邏輯單元塊.

待布邏輯單元塊的選擇分為兩次篩選過程： 首先選出與邏輯單元簇中邏輯單元塊線網(wǎng)連接的數(shù)量之和最大的未布邏輯單元塊.然后在其基礎上選出與邏輯單元簇中邏輯單元塊親密度加權和最大的未布邏輯單元塊.兩個邏輯單元塊clb1，clb2之間的親密度Correlation(clb1,clb2)由式(2)，(3)可得，Basicval稱為邏輯單元塊的基礎價值，在動態(tài)電路網(wǎng)表解析后，如圖1輸出端線網(wǎng)源結點Node C，Totnode為解析后網(wǎng)表中Node C所在樹的總結點數(shù)目，Rmnode為Node C為根結點的子樹的總結點數(shù)目，Curlen為Node C結點的深度，Totlen為該結點所在樹的最大深度.α為經(jīng)驗參數(shù)，這里取值為0.25.Connection(clb1,clb2)即為2個邏輯單元塊線網(wǎng)連接數(shù)量特征的值.式(5)中Correlation(clb1,cluster)為clb1與邏輯單元簇cluster中邏輯單元塊的親密度加權和.其中：Xave和Yave認為是clb1與邏輯單元簇親密度計算下的重心位置；Xave由式(4)計算得到；Xclb2為clb2在該邏輯單元簇中的相對位置，Yave同理.

(2)

Correlation(clb1,clb2)=Basicval(clb1)+Basicval(clb2)+Connection(clb1,clb2).

(3)

(4)

(5)

2.5 快速詳細布局

FPGA資源陣列中可能包含一個或者多個邏輯單元塊，在處理其布局流程時略有不同，主要為： 一，處理各個特征時，對應各個坐標位置的取值為與各個邏輯單元塊對應特征值的平均值；二，由于預測位置得到的是在FPGA資源陣列中的位置，處理大規(guī)模電路布局過程中，位置坐標中包含多個邏輯單元塊時，預測的位置往往不是精確映射回FPGA芯片陣列.為了處理上述問題，并且進一步優(yōu)化時序，可以對模型訓練之后的布局結果進行詳細布局.采用基于交換的詳細布局方法，為實現(xiàn)更有效交換從而加快詳細布局速度，對需要交換的邏輯單元塊和其進行交換的區(qū)間進行約束.待交換的邏輯單元塊是與延時裕量(slack)最低15%路徑關聯(lián)的邏輯單元塊[13]，交換區(qū)間的選擇基于可行區(qū)域[14]進行優(yōu)化，經(jīng)過多次迭代得到最終的布局結果.

優(yōu)化策略上，首先使用最小延時時序矩陣對可行區(qū)域進行進一步提取，其中最小延時時序矩陣F(x,y)是VPR布局階段使用全局布線資源的延時分析矩陣，記錄位置坐標相差(x,y)的2個結點之間的全局布線之間的最小延時，雖然不能準確估算布線之后的路徑延時，但是可以在布局階段給出合理的參考.如圖7所示，假設CLB1中Net1，Net2，Net3分別是網(wǎng)表中slack最低15%的線網(wǎng)路徑，以Net1為例，(x1,y1)和(x2,y2)是決定線網(wǎng)輸入端(xs,ys)最大延時的結點，可行區(qū)域如圖中A、B、C、D所示.經(jīng)過最小延時時序矩陣計算，保留可行區(qū)域中使得(x1,y1),(x2,y2)到(xt,yt)延時更小的部分區(qū)間.其次，對于連接到多條時序上高關鍵度路徑的邏輯單元塊，分別對每條路徑的可行區(qū)域進行評估，并優(yōu)先使用區(qū)間重疊區(qū)域進行交換.假設圖8為圖7中線網(wǎng)Net1,Net2,Net3分別對應的3個可行區(qū)域的交疊情況，區(qū)域1為3個可行區(qū)域重疊的區(qū)域，在進行位置選擇時具有最高的優(yōu)先級，其次是區(qū)域2，再是區(qū)域3.

圖7 基于線網(wǎng)Net1的可行區(qū)域Fig.7 Feasible range of Net1

圖8 CLB1可行區(qū)域的分級Fig.8 Classification of feasible range of CLB1

3 模型訓練與特征工程

表4 不同特征組合和對應的預測精確度

注： “*”表示為模型序號中包含的特征;“—”則表示該模型序號中沒有使用的特征.

為了訓練用于確定待布邏輯單元塊位置的深度學習模型，采用隨機電路網(wǎng)表生成器和最優(yōu)線長電路網(wǎng)表生成器生成的網(wǎng)表產(chǎn)生模型訓練數(shù)據(jù)，分別為270萬和30萬數(shù)據(jù).訓練環(huán)境為Linux系統(tǒng)下Keras 2.1.0(基于Tensorflow 1.4.0)，Xeon E5-2620處理器，4塊TITAN-V和3塊TITAN-X GPU，在初始學習率0.003下經(jīng)過20 epoches訓練得到最終的模型.在過濾掉無效和不合法數(shù)據(jù)之后提取top5模型預測準確度(標簽位置在預測位置概率分布中top5的精確度).并針對多組特征進行分別訓練，分析不同特征對模型訓練的影響.

表4為不同特征組合進行模型訓練得到的結果，f1～f5分別為特征一到特征五，f6-1,f6-2,f6-3分別為特征六的3個子特征，總共進行了DL1～DL99組對照分析.可以看到不同特征對模型的影響差別各異，同時采用6個完整特征時得到最高的模型預測準確度，預測達到41.3%的top5準確度.

4 實驗結果

注： 1)平均值.

實驗采用深度學習特征組合DL9訓練得到的模型進行測試，調(diào)用模型進行位置預測后進行快速詳細布局優(yōu)化.在與模型訓練的相同運行環(huán)境下使用MCNC基準電路[15]與VPR 8.0中使用的模擬退火布局算法進行對比.使用的FPGA為通用島形結構k4_n4_v7_bidir.xml，實驗結果如表5所示.從表5可以看出，盡管在布線后關鍵路徑延時上，基于深度學習的布局算法與VPR相比關鍵路徑延時相差大致為9.8%，但是從運行時間上看，基于深度學習的布局算法能夠明顯提升運行速度，提升在1.59到78.5倍，平均上看運行速度提升在24.54倍，其中接近十萬量級的大規(guī)模電路實現(xiàn)近似64.9倍的運行速度提升.分析數(shù)據(jù)可以看出，布局的加速效果受電路規(guī)模影響很大，這是由于基于交換的模擬退火算法交換空間隨著電路規(guī)模的增大成指數(shù)級增長，因而模擬退火算法在處理類似mcml,arm_core等規(guī)模大的電路交換次數(shù)達到數(shù)億次，而基于深度學習的布局算法布局的次數(shù)與可交換邏輯單元塊數(shù)量相同，快速詳細布局部分只有少量的時序優(yōu)化交換次數(shù)，總的來說，在處理大規(guī)模電路時該算法的運行速度能夠得到非常大的提升，這也適應于實際應用.

5 結 語

本文基于FPGA芯片描述k4_n4_v7_bidir.xml將布局過程轉化為逐步進行待布邏輯單元塊的選擇和邏輯單元塊位置確定的過程.利用殘差網(wǎng)絡對數(shù)據(jù)進行訓練，得到在6組特征下41.3%的top5預測精確度.該算法對MCNC基準電路與VPR相比在平均9.8%的關鍵路徑延時損失下實現(xiàn)了平均運行速度24.54倍的提升，在處理大規(guī)模電路時有明顯的時間優(yōu)勢.實際上本文中的算法可以支持復雜的可配置邏輯塊的結構，也體現(xiàn)深度學習工具在處理FPGA這樣的NP問題時有實際的意義.