面向FPGA的布局與布線技術(shù)研究綜述

田春生，陳 雷，王 源，王 碩，周 婧，張瑤偉，龐永江，周 沖，馬筱婧，杜 忠，薛 鈺

（1.北京大學(xué)信息科學(xué)技術(shù)學(xué)院微納電子學(xué)系，北京 100871；2.北京微電子技術(shù)研究所，北京 100076）

1 引言

1984 年，Xilinx 公司首次提出現(xiàn)場(chǎng)可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）的概念，作為一種半定制電路，F(xiàn)PGA 憑借其設(shè)計(jì)成本低、速度快、異構(gòu)邏輯資源豐富等優(yōu)勢(shì)，一經(jīng)面世便廣泛應(yīng)用于現(xiàn)代數(shù)字系統(tǒng)的設(shè)計(jì)中［1，2］.隨著各種新興技術(shù)的不斷涌現(xiàn)，F(xiàn)PGA 的應(yīng)用范圍也在逐步從普通的消費(fèi)電子向物聯(lián)網(wǎng)（Internet of Things，IoTs）［3］、高性能運(yùn)算［4］、云計(jì)算［5］、人工智能［6，7］等領(lǐng)域不斷拓展.FPGA 的集成度也在不斷增大，從最初只含有64 個(gè)邏輯單元發(fā)展到迄今為止的超過(guò)900萬(wàn)個(gè)邏輯單元以及350億個(gè)晶體管.集成度的不斷提升使得FPGA 能夠被用于設(shè)計(jì)更加復(fù)雜的電路系統(tǒng)，但同時(shí)也對(duì)FPGA 電子設(shè)計(jì)自動(dòng)化（Electronic Design Automation，EDA）軟件工具造成了負(fù)擔(dān)［8］.FPGA 的研發(fā)離不開EDA 工具的支持，以硬件描述語(yǔ)言（Hardware Description Language，HDL）設(shè)計(jì)的電路，通過(guò)FPGA EDA 工具會(huì)被編譯為二進(jìn)制的碼流文件，通過(guò)該碼流文件能夠完成對(duì)FPGA 芯片的配置最終實(shí)現(xiàn)所需的電路功能［9］.但隨著FPGA芯片集成度以及電路規(guī)模的不斷提高，F(xiàn)PGA EDA 工具將電路描述文件編譯為二進(jìn)制格式的文件所需花費(fèi)的時(shí)間也越來(lái)越長(zhǎng)，這將直接降低FPGA 在設(shè)計(jì)階段的開發(fā)效率、增加時(shí)間成本，制約FPGA芯片的健康發(fā)展［10，11］.

FPGA EDA 工具的設(shè)計(jì)流程主要包括設(shè)計(jì)輸入、行為綜合、邏輯映射、打包、布局、布線以及二進(jìn)制碼流生成.其中，布局與布線作為FPGA EDA 工具設(shè)計(jì)流程中至關(guān)重要的環(huán)節(jié)，其最終結(jié)果直接決定了所設(shè)計(jì)的電路在FPGA 芯片上實(shí)現(xiàn)后的性能.因此，布局和布線技術(shù)的研究對(duì)于FPGA 的健康可持續(xù)發(fā)展具有重大的意義.本文全面綜述了FPGA 布局、布線問(wèn)題的研究現(xiàn)狀與進(jìn)展，完成了相關(guān)理論成果和技術(shù)方法的梳理，對(duì)FPGA 布局和布線的關(guān)鍵技術(shù)進(jìn)行了詳細(xì)闡述，最后對(duì)FPGA布局、布線技術(shù)未來(lái)的發(fā)展趨勢(shì)進(jìn)行了展望.

2 FPGA布局關(guān)鍵技術(shù)

使用HDL 語(yǔ)言設(shè)計(jì)的電路在經(jīng)過(guò)行為綜合、邏輯映射和打包等操作后，會(huì)被轉(zhuǎn)化為一個(gè)電路網(wǎng)表，F(xiàn)PGA 布局就是指根據(jù)線長(zhǎng)、時(shí)延、功耗以及面積等約束條件，將電路網(wǎng)表中的異構(gòu)邏輯單元與實(shí)際FPGA 芯片中的物理位置建立一一映射的過(guò)程［12］.現(xiàn)有的FPGA布局技術(shù)主要包括基于劃分的布局技術(shù)、基于啟發(fā)式的布局技術(shù)以及基于解析式的布局技術(shù).

2.1 基于劃分的布局技術(shù)

基于劃分的布局技術(shù)是指根據(jù)已知的布局約束關(guān)系，在最原始的布局實(shí)例的基礎(chǔ)上，通過(guò)遞歸迭代對(duì)布局實(shí)例進(jìn)行劃分，直至所有布局實(shí)例均小于事先設(shè)定的閾值為止［13］.SimPL布局方法便是基于劃分的布局技術(shù)中的一種典型的代表［14］，該方法以線長(zhǎng)為約束條件，首先分別計(jì)算線長(zhǎng)的下界和上界，接下來(lái)通過(guò)采用一種基于自頂向下的幾何分割和非線性縮放的前向合法化方法不斷迭代，最終能夠使邏輯單元收斂到合法的位置.隨著圖論以及超圖劃分理論方法的不斷演進(jìn)［15～19］，最小割布局方法也得到了研究學(xué)者們的廣泛關(guān)注.基于劃分的布局技術(shù)的優(yōu)點(diǎn)在于通過(guò)對(duì)較大規(guī)模的電路執(zhí)行遞歸劃分操作，將原始布局問(wèn)題轉(zhuǎn)化為相互正交的不同的子問(wèn)題，收斂到最終布局結(jié)果的速度較快，但通過(guò)使用基于劃分的布局技術(shù)得到的布局結(jié)果，不能保證布局解的最優(yōu)性，容易陷入到局部最優(yōu)解當(dāng)中.

2.2 基于啟發(fā)式的布局技術(shù)

基于啟發(fā)式的布局技術(shù)以現(xiàn)有科學(xué)領(lǐng)域中的一些自然現(xiàn)象為設(shè)計(jì)原理，對(duì)FPGA 邏輯單元的布局過(guò)程進(jìn)行建模.典型的包括遺傳算法［20，21］、蟻群算法［22～24］和模擬退火算法［25］等，其中又以模擬退火算法的研究最為廣泛.1953 年，Metropolis 等最早提出了模擬退火算法理論［26］，模擬退火算法是一種基于Monte-Carlo 求解方式的隨機(jī)搜索算法，其原理是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性.1988年，Carl 等［27］首次將模擬退火算法的思想引入到超大規(guī)模集成電路（Very Large Scale Integration，VLSI）布局領(lǐng)域.隨后，越來(lái)越多的研究學(xué)者開始關(guān)注模擬退火算法在VLSI、FPGA 等布局領(lǐng)域的應(yīng)用.學(xué)術(shù)界較為流行的FPGA 通用布局布線（Versatile Placement and Routing，VPR）工具，其布局器的基礎(chǔ)框架正是基于模擬退火算法.

使用傳統(tǒng)的模擬退火算法對(duì)FPGA 執(zhí)行布局操作時(shí)，首先會(huì)得到一個(gè)初始的布局狀態(tài)，初始布局狀態(tài)是布局器隨機(jī)生成的，隨后布局器會(huì)通過(guò)執(zhí)行邏輯單元的交換或是移動(dòng)等操作對(duì)當(dāng)前的布局解進(jìn)行擾動(dòng)，進(jìn)一步得到新的布局解并計(jì)算得到初始溫度.布局器的主體包含內(nèi)外兩層循環(huán)，內(nèi)層循環(huán)控制交換的邏輯單元，外層循環(huán)執(zhí)行溫度的更新以及邏輯單元交換半徑的計(jì)算等操作.內(nèi)層循環(huán)每次選擇一個(gè)邏輯單元，隨后依據(jù)交換半徑在FPGA 芯上選擇一個(gè)位置，若該位置為空則直接將所選擇的邏輯單元移動(dòng)到該位置上，若該位置上已放置有邏輯單元?jiǎng)t執(zhí)行兩個(gè)邏輯單元的位置交換操作［28］.以ΔC表示邏輯單元交換前后成本函數(shù)的差值，如果ΔC＜0，表示新的布局解要優(yōu)于原始的布局解，則接受本次的移動(dòng)或是交換過(guò)程；如果ΔC＞0，則以的概率接受新的布局解，其中T表示當(dāng)前溫度.這樣做的好處在于能夠使布局器具備一定的爬坡能力.當(dāng)內(nèi)層循環(huán)的迭代次數(shù)達(dá)到上限后，退出內(nèi)層循環(huán)進(jìn)入外層循環(huán)，外層循環(huán)會(huì)依據(jù)當(dāng)前的布局狀態(tài)對(duì)邏輯單元的交換半徑以及溫度進(jìn)行更新.當(dāng)溫度小于特定閾值時(shí)跳出外層循環(huán)，結(jié)束布局過(guò)程.模擬退火算法的本質(zhì)還是一種基于概率的算法，能夠在一個(gè)很大的空間內(nèi)尋找近似最優(yōu)解，在時(shí)間允許的情形下，能夠得到全局最優(yōu)解，并且能夠有效避免陷入到局部最優(yōu)陷阱.其缺陷在于當(dāng)電路規(guī)模較大時(shí)，算法收斂的時(shí)間較長(zhǎng)，因此對(duì)模擬退火算法的收斂時(shí)間進(jìn)行優(yōu)化研究顯得至關(guān)重要［29］.

利用多個(gè)中央處理器進(jìn)行加速是減少FPGA布局運(yùn)行時(shí)間的有效手段，2010 年，Brik 等［30］利用事務(wù)性內(nèi)存（Transactional Memory，TM）對(duì)模擬退火算法進(jìn)行并行加速，在布局質(zhì)量幾乎沒(méi)有任何下降的前提下，能夠獲得可觀的加速比.2011年，Altera 公司（現(xiàn)Intel公司）研究人員［31］提出了一種確定性的FPGA 并行布局算法，能夠?qū)﹃P(guān)鍵路徑進(jìn)行優(yōu)化，在整個(gè)退火的過(guò)程中最高能夠?qū)崿F(xiàn)高達(dá)3.7倍的加速比.2014年，An等［32］以VPR工具為基礎(chǔ)，探索了基于模擬退火機(jī)制的FPGA 并行布局方法如何能夠在保證布局質(zhì)量的同時(shí)，確保布局結(jié)果的確定性.實(shí)驗(yàn)結(jié)果表明，在保證布局質(zhì)量以及確定性的情況下，能夠獲得5.9倍的加速比.2018年，Hu等［33］使用多線程同時(shí)處理邏輯單元的移動(dòng)過(guò)程，避免了數(shù)據(jù)流的沖突，實(shí)現(xiàn)了FPGA布局過(guò)程的加速.

通過(guò)對(duì)模擬退火方法中邏輯單元的移動(dòng)過(guò)程進(jìn)行優(yōu)化，從而加速FPGA 布局過(guò)程的收斂同樣是一個(gè)非常有意義的研究方向［34～37］.2009 年，Vorwerk 等［34］提出了多種策略來(lái)創(chuàng)建邏輯單元的移動(dòng)過(guò)程，通過(guò)計(jì)算每一種移動(dòng)過(guò)程的有效性，以此有效性為指標(biāo)決定布局器選取每一種移動(dòng)過(guò)程的概率，以便更有效的在FPGA 布局空間中搜索最優(yōu)的解決方案，能夠獲得更好的線長(zhǎng)以及時(shí)序上的實(shí)現(xiàn)效果.Intel 公司的Quartus II 布局器中便采用了多達(dá)10 余種的直接移動(dòng)（Directed Moves，DM）過(guò)程，但在布局時(shí)DM 過(guò)程的選擇機(jī)制卻從未對(duì)外披露［31］.2017年，Yuan等［38］以線長(zhǎng)為指標(biāo)，提出了基于區(qū)域范圍的移動(dòng)過(guò)程，將邏輯單元的移動(dòng)操作限制在某一特定的區(qū)域內(nèi)，同時(shí)通過(guò)設(shè)置優(yōu)先級(jí)的方法，優(yōu)先對(duì)那些性能較差的線網(wǎng)執(zhí)行布局操作.2019 年，Yuan 等［39］對(duì)此項(xiàng)工作做了進(jìn)一步拓展，在布局的過(guò)程中加入了時(shí)序優(yōu)化.此外，隨著機(jī)器學(xué)習(xí)、人工智能等技術(shù)的發(fā)展，越來(lái)越多的研究學(xué)者利用機(jī)器學(xué)習(xí)類方法來(lái)優(yōu)化基于模擬退火算法的FPGA 布局過(guò)程［40］.2019 年，Murray等［41］使用單狀態(tài)強(qiáng)化學(xué)習(xí)策略提出了一種自適應(yīng)的FPGA 布局方法，在每一次布局的過(guò)程中能夠自動(dòng)地選取需要交換的邏輯單元，節(jié)省了布局所需要的時(shí)間，與VPR 工具相比較，在獲得同等性能參數(shù)的前提下，能夠獲得2倍以上的加速比.在此項(xiàng)工作基礎(chǔ)上，2020年，Elgammal等［42］做了進(jìn)一步探索，使用多狀態(tài)強(qiáng)化學(xué)習(xí)策略以優(yōu)化DM過(guò)程的選取過(guò)程，基于模擬退火方法的FPGA布局器的性能得到了進(jìn)一步優(yōu)化.

2.3 基于解析式的布局技術(shù)

基于解析式的布局技術(shù)將FPGA 布局問(wèn)題建模為一個(gè)連續(xù)優(yōu)化問(wèn)題，通過(guò)梯度下降的方法得到布局問(wèn)題的最優(yōu)解.根據(jù)目標(biāo)函數(shù)的不同，可以分為二次方布局技術(shù)［43～46］以及非線性布局技術(shù)［47，48］.二次方布局技術(shù)是指通過(guò)二次函數(shù)來(lái)逼近最終的布局解，而非線性布局技術(shù)是指利用更加具有表現(xiàn)力的高階方法來(lái)完成對(duì)布局結(jié)果的近似.

二次方布局技術(shù)通常以線長(zhǎng)為優(yōu)化目標(biāo)完成對(duì)目標(biāo)函數(shù)的建模，隨后通過(guò)Krylov子空間方法將上述優(yōu)化問(wèn)題轉(zhuǎn)化為對(duì)稱與正定（Symmetric and Positive-Definite，SPD）線性系統(tǒng)的求解問(wèn)題，最終得到優(yōu)化問(wèn)題的解［49］.但純粹以線長(zhǎng)為優(yōu)化目標(biāo)，最終的布局結(jié)果將導(dǎo)致越來(lái)越多的邏輯單元重疊在一起，因此需要采用合適的方法對(duì)二次方布局技術(shù)進(jìn)行優(yōu)化，以減少各邏輯單元間的重疊.其中，力導(dǎo)向法得到了廣泛的關(guān)注.在每一次布局迭代的過(guò)程中，力導(dǎo)向法能夠使邏輯單元均勻的分散開，這些邏輯單元的位置將被作為錨節(jié)點(diǎn)，隨后，將指向這些邏輯單元的額外的拓展力應(yīng)用于下一次迭代中，以輔助邏輯單元的布局，不斷重復(fù)上述過(guò)程，最終能夠得到一個(gè)所有邏輯單元的位置均互不重疊的布局解決方案［50，51］.與二次方布局技術(shù)不同，非線性布局技術(shù)使用不可微分的非線性函數(shù)來(lái)表示非重疊的約束條件，并將其與線長(zhǎng)一起在統(tǒng)一的目標(biāo)函數(shù)中進(jìn)行求解.由于高階非線性函數(shù)比二次函數(shù)更具有表現(xiàn)力，因此，通過(guò)非線性布局技術(shù)得到的布局解的質(zhì)量要優(yōu)于二次方布局技術(shù)，但這種布局質(zhì)量的改進(jìn)需要犧牲更多的系統(tǒng)運(yùn)行時(shí)間［52］.

基于解析式的布局技術(shù)其布局結(jié)果的可接受度以及系統(tǒng)運(yùn)行時(shí)間要優(yōu)于基于劃分的布局技術(shù)與基于啟發(fā)式的布局技術(shù).然而，為了更加高效地利用FPGA 芯片資源，基于解析式的布局技術(shù)在一些具體的布局細(xì)節(jié)方面仍需進(jìn)一步優(yōu)化，這些具體的布局細(xì)節(jié)通常以低溫模擬退火方法或是一些基于貪婪思想的啟發(fā)式方法來(lái)實(shí)現(xiàn)［53，54］.

本文總結(jié)了基于劃分的布局技術(shù)、基于啟發(fā)式的布局技術(shù)與基于解析式的布局技術(shù)的優(yōu)勢(shì)與不足，具體如表1所示.

表1 FPGA布局技術(shù)總結(jié)

3 FPGA布線關(guān)鍵技術(shù)

FPGA 布線問(wèn)題是指通過(guò)對(duì)芯片中的可編程互連開關(guān)進(jìn)行配置，從而完成對(duì)電路邏輯單元間的連接，同時(shí)需要保證所有的互連資源都不能被重復(fù)使用.在布線時(shí)，F(xiàn)PGA 芯片內(nèi)的硬件資源會(huì)被抽象為有向的布線資源圖（Routing Resource Graph，RRG）G=（V，E），其中，V表示RRG 中頂點(diǎn)的集合，每一個(gè)頂點(diǎn)v，?v∈V表示FPGA 芯片內(nèi)的互連線資源或是邏輯單元的引腳.E表示RRG 中邊的集合，每一條邊ei，j，?ei，j∈E表示邏輯資源引腳與互連線資源或是互連線資源間的可編程互連開關(guān)［55］.RRG 作為布線算法與FPGA 硬件間的紐帶，能夠?qū)PGA 布線問(wèn)題轉(zhuǎn)化為圖論中最短路徑的求解問(wèn)題，布線算法直接在RRG 上對(duì)電路線網(wǎng)執(zhí)行布線操作即可.每個(gè)電路線網(wǎng)Ni由一個(gè)源端si，?si∈V與一個(gè)或多個(gè)漏端ti，j，?ti，j∈V組成.有了RRG的概念，線網(wǎng)Ni的布線問(wèn)題被轉(zhuǎn)化為能否在RRG 中找到合法的路徑連接si與ti，j，這些路徑共同組成線網(wǎng)Ni的布線樹（Routing Tree，RT）RT(Ni) ?G.

1995 年，McMurchie 等［56］首次提出了基于擁塞協(xié)商思想的FPGA 布線方法PathFinder，它允許FPGA 中互連資源被重復(fù)使用的情況下執(zhí)行線網(wǎng)的布線操作，迭代地對(duì)電路中的線網(wǎng)進(jìn)行“拆線-重布”，每次迭代時(shí)PathFinder 會(huì)以協(xié)商的方式確定各線網(wǎng)間互連資源的分配.隨著迭代次數(shù)的增加，PathFinder 會(huì)逐漸增加對(duì)重復(fù)使用的互連資源的懲罰力度，以此來(lái)逐步消除互連資源的重復(fù)使用.

PathFinder 方法的實(shí)現(xiàn)是一個(gè)內(nèi)外三層循環(huán)的嵌套結(jié)構(gòu)，最外層的循環(huán)被稱為全局布線器，在每一次迭代時(shí)會(huì)調(diào)用第二層循環(huán)中的線網(wǎng)布線器，對(duì)電路中的線網(wǎng)逐一執(zhí)行布線操作.全局布線器在所有線網(wǎng)完成布線迭代后，會(huì)將布線資源的歷史擁擠度進(jìn)行更新，并根據(jù)布線迭代的結(jié)果對(duì)線網(wǎng)執(zhí)行時(shí)序分析的操作.檢查是否有布線資源被重復(fù)使用，若所有布線資源均沒(méi)有被重復(fù)占用，則結(jié)束布線流程；否則，此次布線迭代過(guò)程非法，繼續(xù)執(zhí)行下一次布線迭代操作.當(dāng)線網(wǎng)布線器對(duì)電路中的第i個(gè)線網(wǎng)Ni執(zhí)行布線操作時(shí)，線網(wǎng)布線器會(huì)釋放線網(wǎng)Ni所對(duì)應(yīng)的RT（Ni）上的資源，并對(duì)節(jié)點(diǎn)的當(dāng)前擁擠度進(jìn)行更新，隨后根據(jù)連接的關(guān)鍵度信息對(duì)線網(wǎng)Ni中所有的漏端ti，j執(zhí)行降序排列操作，最后線網(wǎng)布線器會(huì)調(diào)用最內(nèi)層的迷宮布線器依次對(duì)線網(wǎng)Ni內(nèi)的每一個(gè)漏端ti，j進(jìn)行布線.PathFinder 擁塞協(xié)商方法起到了引路者以及奠基人的角色，它是目前大部分FPGA 布線算法的基礎(chǔ)，學(xué)術(shù)上通用的VPR 工具以及nextpnr 工具在布線階段使用的都是在PathFinder 基礎(chǔ)上改進(jìn)的布線方法.同時(shí)，現(xiàn)階段幾乎所有的FPGA 廠商都在使用基于擁塞協(xié)商的PathFinder 布線方法，或是在這個(gè)方法基礎(chǔ)上引申出來(lái)的其他布線方法，但隨著電路規(guī)模的增大，PathFinder 布線方法耗時(shí)越來(lái)越長(zhǎng)，這一問(wèn)題隨著FPGA 的發(fā)展將愈發(fā)突出.因此，亟需探索新的解決方案或是對(duì)現(xiàn)有解決方案進(jìn)行優(yōu)化以適應(yīng)FPGA 不斷發(fā)展的需求［57］.現(xiàn)有的解決方案可以分為FPGA串行布線與FPGA并行布線兩種類型.

3.1 FPGA串行布線技術(shù)

現(xiàn)有的FPGA串行布線技術(shù)都是基于PathFinder方法的改進(jìn).將FPGA 電路中常用的邏輯單元打包成宏并提前進(jìn)行編譯，是減少布線時(shí)間的有效手段［58，59］.2011 年，Lavin 等［59］通過(guò)設(shè)置硬宏的方法將FPGA 電路中常用的一些邏輯單元提前進(jìn)行編譯并在數(shù)據(jù)庫(kù)中加以保存，在對(duì)用戶設(shè)計(jì)電路進(jìn)行編譯時(shí)便可以從數(shù)據(jù)庫(kù)中選擇與之相匹配的硬宏.這種方法可以明顯減少電路編譯的時(shí)間，同Xilinx 公司的ISE 工具相比較，此方法能夠獲得10 到50 倍的加速比，改進(jìn)效果是非常可觀的.2012 年，Coole 等［60］構(gòu)建了一種新的FPGA 布局布線工具，通過(guò)設(shè)置宏單元能夠使布線方法在更高的層次上運(yùn)行，能夠獲得指數(shù)級(jí)的加速比.但由于宏單元是提前設(shè)置并封裝好的，在實(shí)際布線時(shí)其中的連接關(guān)系是無(wú)法更改的，增加了FPGA 布線時(shí)的局限性.簡(jiǎn)化FPGA 的布線結(jié)構(gòu)是另一種降低FPGA 布線時(shí)間的方法［61］.PathFinder 方法在每次對(duì)線網(wǎng)執(zhí)行布線迭代時(shí)需要確定具體使用的是布線通道中的哪條布線資源，2015 年，F(xiàn)erreira 等［62］提出在使用PathFinder 方法確定布線通道后，將布線通道中互連資源的分配問(wèn)題建模為布爾滿足問(wèn)題［63，64］，隨后使用求解器MiniSat 對(duì)上述問(wèn)題進(jìn)行了求解［65］.通過(guò)簡(jiǎn)化FPGA 結(jié)構(gòu)的方法，能夠明顯降低FPGA 布線方法復(fù)雜度，但此類方法過(guò)分依賴FPGA 硬件架構(gòu)，并不適用于商用FPGA 芯片的設(shè)計(jì)流程，實(shí)用性有待進(jìn)一步加強(qiáng).

PathFinder 方法以線網(wǎng)為單位每次執(zhí)行“拆線-重布”的操作，在檢測(cè)到存在布線資源重復(fù)使用的情況時(shí)，對(duì)所有線網(wǎng)進(jìn)行拆分，依次執(zhí)行重新布線.上述過(guò)程是非常耗時(shí)的.為此，2016 年，比利時(shí)根特大學(xué)研究人員［66，67］提出了基于連接的FPGA 布線方案，連接由線網(wǎng)Ni中的單個(gè)源端si與單個(gè)漏端ti，j組成，在每次迭代的過(guò)程中以連接為單位執(zhí)行“拆線-重布”的操作，只有當(dāng)不同的連接屬于同一個(gè)線網(wǎng)時(shí)才可以共享相同的布線資源節(jié)點(diǎn).與VPR 7.0相比基于連接的FPGA 布線方案在布線階段能夠提供3.4倍的加速比［67］.與基于連接的FPGA 布線方案不同，2020 年，Murray 等［68］設(shè)計(jì)了一種自適應(yīng)的增量布線器，能夠保持一種自然的基于線網(wǎng)的結(jié)構(gòu)，在每次“拆線-重布”時(shí)只拆除非法的布線資源節(jié)點(diǎn)，從而保證在下次迭代時(shí)，合法的路徑能夠被重復(fù)使用，減少了在RRG 中重復(fù)搜索所需要的時(shí)間.同時(shí)，針對(duì)一些具有高扇出屬性的線網(wǎng)制定了特殊的前向搜索機(jī)制，即每次只對(duì)與漏端ti，j空間上相近的布線節(jié)點(diǎn)進(jìn)行搜索，以降低布線所需時(shí)間.相比于基于連接的FPGA布線方案，能夠進(jìn)一步減少17%的布線時(shí)間.

3.2 FPGA并行布線技術(shù)

隨著多核處理器與圖形處理器的普及，越來(lái)越多的學(xué)者將并行計(jì)算應(yīng)用到FPGA 布線領(lǐng)域以減少FPGA在布線時(shí)花費(fèi)的時(shí)間［69］.根據(jù)并行化方式的不同，又可以將并行布線技術(shù)分為粗粒度FPGA并行布線技術(shù)［70］、細(xì)粒度FPGA 并行布線技術(shù)［71］以及兩種不同并行布線技術(shù)的混合［72］.粗粒度FPGA 并行布線技術(shù)通過(guò)將線網(wǎng)劃分為不同的分區(qū)，在每個(gè)分區(qū)內(nèi)執(zhí)行獨(dú)立的布線操作.最終布線后的性能參數(shù)取決于線網(wǎng)的劃分方式、并行運(yùn)算過(guò)程中數(shù)據(jù)的同步模式以及沖突的回避方式等多種因素.細(xì)粒度FPGA 并行布線技術(shù)能夠?qū)蝹€(gè)線網(wǎng)的布線過(guò)程實(shí)現(xiàn)并行加速，最終的性能參數(shù)取決于并行布線過(guò)程中的并行度以及共享數(shù)據(jù)的同步方式等諸多因素.此外，評(píng)判某一FPGA 并行布線方法的性能還需將布線方法的可擴(kuò)展性與確定性等問(wèn)題聯(lián)合起來(lái)進(jìn)行考慮.本文對(duì)不同的FPGA 并行布線技術(shù)進(jìn)行了分析總結(jié)（如表2所示）.

表2 FPGA并行布線技術(shù)

3.2.1 粗粒度FPGA并行布線技術(shù)

（1）基于字典序的FPGA并行布線

1997 年，Chan 等［73］首次嘗試將PathFinder 方法執(zhí)行并行化操作，研究人員首先將所有線網(wǎng)按字典序進(jìn)行排序，從而使那些可能共享資源的線網(wǎng)相鄰并盡可能分配給同一個(gè)中央處理器（Central Processing Unit，CPU）.隨后，將線網(wǎng)列表劃分成互不相交的集合，每個(gè)集合靜態(tài)地分配給CPU 執(zhí)行并行布線.并行布線的過(guò)程中，每個(gè)CPU 會(huì)單獨(dú)保存線網(wǎng)布線的擁塞狀態(tài)等信息，一旦某個(gè)CPU 的擁塞狀態(tài)信息發(fā)生變化，該CPU 將首先更新本地保存的數(shù)據(jù)信息，并通過(guò)UNIX 套接字通知其他處理器對(duì)擁塞信息進(jìn)行更新.與原始PathFinder 算法相比較，上述方法最高能夠獲得3.2 倍的加速比.但此方法的布線結(jié)果具有不確定性，布線結(jié)果依賴于線網(wǎng)的布線順序，并且由于是靜態(tài)的線網(wǎng)劃分，每個(gè)CPU 間存在負(fù)載不均衡的問(wèn)題.2000年，上述團(tuán)隊(duì)的研究人員［74］對(duì)CPU 負(fù)載不均衡的問(wèn)題進(jìn)行了優(yōu)化，但布線結(jié)果仍然具有不確定性.

（2）基于負(fù)載均衡的FPGA并行布線

2012 年，Gort 等［75］提出了多進(jìn)程并發(fā)執(zhí)行的方式以加速布線過(guò)程，這些并發(fā)執(zhí)行的進(jìn)程運(yùn)行在不同的CPU 內(nèi)核中（如圖1 所示）.每個(gè)進(jìn)程運(yùn)行一個(gè)單獨(dú)的VPR 實(shí)例，負(fù)責(zé)對(duì)分配給它的線網(wǎng)執(zhí)行布線操作并維護(hù)自身的數(shù)據(jù)結(jié)構(gòu).不同VPR 實(shí)例間的信息同步通過(guò)消息傳遞接口（Message Passing Interface，MPI）來(lái)實(shí)現(xiàn).

圖1 基于負(fù)載均衡的FPGA并行布線

VPR 實(shí)例在完成某一信號(hào)的布線后，會(huì)向其他VPR 實(shí)例發(fā)送無(wú)阻塞更新信息，隨后繼續(xù)執(zhí)行布線操作而無(wú)需等待從其他VPR 實(shí)例接收更新消息.VPR 實(shí)例發(fā)送的更新信息中包含了最新的布線信息，這些信息被保存在MPI的信息隊(duì)列中.為了接收更新的消息，VPR 實(shí)例會(huì)在布線過(guò)程中的特定位置發(fā)出阻塞接收的調(diào)用請(qǐng)求，并且為了保證布線結(jié)果的確定性，這些位置在每次運(yùn)行過(guò)程中都是相同的.如果某一時(shí)刻VPR 實(shí)例想要接收信息但更新消息卻不可用，由于先前已經(jīng)調(diào)用了阻塞接收的請(qǐng)求，VPR 實(shí)例會(huì)暫停其布線流程直至消息更新可用為止.為了最大程度地減少VPR 實(shí)例駐留時(shí)間，作者會(huì)在任務(wù)劃分的過(guò)程中保證每個(gè)VPR 實(shí)例的負(fù)載都盡可能相等，并且僅在MPI 消息隊(duì)列中存在VPR 實(shí)例想要更新的消息時(shí)，才會(huì)允許VPR實(shí)例發(fā)出阻塞接收的調(diào)用請(qǐng)求.與此同時(shí)，為了能夠精準(zhǔn)地確定阻塞接收調(diào)用請(qǐng)求的發(fā)出時(shí)間，每個(gè)VPR 實(shí)例都會(huì)維護(hù)一個(gè)工作計(jì)數(shù)器以評(píng)估每個(gè)VPR 實(shí)例所執(zhí)行的工作量.

（3）基于迭代劃分的FPGA并行布線

北京大學(xué)團(tuán)隊(duì)研究人員［76］與中山大學(xué)團(tuán)隊(duì)研究人員［77］在前人研究工作的基礎(chǔ)上探索了基于迭代劃分的FPGA 并行布線方案，通過(guò)遞歸劃分的方法能夠?qū)⒕€網(wǎng)劃分為多個(gè)集合，每個(gè)集合內(nèi)的線網(wǎng)互不相交，進(jìn)而可以執(zhí)行并行布線的操作.

首先，使用二分法能夠?qū)PGA 劃分為兩個(gè)子區(qū)域，根據(jù)劃分的結(jié)果能夠得到三個(gè)不同的線網(wǎng)集合：橫跨兩個(gè)子區(qū)域的線網(wǎng)集合以及完全在兩個(gè)子區(qū)域內(nèi)的線網(wǎng)集合.由于在兩個(gè)子區(qū)域內(nèi)的線網(wǎng)互不相交，因此可以執(zhí)行并行布線的操作.可以通過(guò)迭代的方式重復(fù)上述步驟以增加布線方法的并行度.

圖2 展示了基于迭代劃分的FPGA 并行布線方法的原理.首先，圖中的藍(lán)色實(shí)線將FPGA 分成了上下兩個(gè)區(qū)域：S1與S2.隨后，圖中綠色的虛線進(jìn)行了進(jìn)一步的劃分：將區(qū)域S1劃分為S3與S4兩個(gè)子區(qū)域，將區(qū)域S2劃分為S5與S6兩個(gè)子區(qū)域.最后，圖中紅色的虛線又進(jìn)一步執(zhí)行了劃分的操作：將區(qū)域S3劃分為S7與S8兩個(gè)子區(qū)域，將區(qū)域S4劃分為S9與S10兩個(gè)子區(qū)域，將區(qū)域S5劃分為S11與S12兩個(gè)子區(qū)域，將區(qū)域S6劃分為S13與S14兩個(gè)子區(qū)域.上述劃分過(guò)程可以使用一個(gè)L級(jí)二叉樹表示（如圖2（a）所示）.劃分完成后，布線問(wèn)題被建模為分布式內(nèi)存系統(tǒng)的任務(wù)調(diào)度問(wèn)題：任務(wù)T0負(fù)責(zé)對(duì)所有的線網(wǎng)執(zhí)行布線操作，任務(wù)T1負(fù)責(zé)對(duì)子區(qū)域S1內(nèi)的線網(wǎng)執(zhí)行布線操作，任務(wù)T2負(fù)責(zé)對(duì)子區(qū)域S2內(nèi)的線網(wǎng)執(zhí)行布線操作，依此類推，任務(wù)Ti負(fù)責(zé)對(duì)子區(qū)域Si內(nèi)的線網(wǎng)執(zhí)行布線操作.上述任務(wù)被靜態(tài)地映射到不同進(jìn)程，不同進(jìn)程使用MPI 進(jìn)行數(shù)據(jù)間的同步（如圖2（b）所示）.布線過(guò)程從主進(jìn)程p=0開始執(zhí)行，即在一個(gè)L級(jí)的完美二叉樹上執(zhí)行任務(wù)T0.T0首先將線網(wǎng)劃分為S1與S2兩個(gè)子區(qū)域，接下來(lái)T0會(huì)對(duì)橫跨兩個(gè)子區(qū)域的線網(wǎng)集合執(zhí)行串行布線的操作，布線結(jié)束后，它會(huì)將右側(cè)的L-1 級(jí)子樹分配給進(jìn)程p+2L-1=p+4.最后，T0通過(guò)遞歸調(diào)用函數(shù)ParMaze（）會(huì)將左側(cè)的L-1級(jí)子樹分配給任務(wù)T1.隨后，進(jìn)程p+4 與任務(wù)T2會(huì)返回子區(qū)域S2內(nèi)線網(wǎng)的布線樹，任務(wù)T1會(huì)返回子區(qū)域S1內(nèi)線網(wǎng)的布線樹.不斷重復(fù)上述過(guò)程，直至所有的線網(wǎng)都完成了布線操作.

圖2 遞歸劃分原理

但隨著遞歸迭代次數(shù)的增加，跨區(qū)域線網(wǎng)的數(shù)量也在同時(shí)增多，導(dǎo)致FPGA 并行布線方法的并行度越來(lái)越低.針對(duì)上述問(wèn)題，2020年，Wang等［78］提出了一種混合線網(wǎng)劃分機(jī)制，在線網(wǎng)遞歸劃分的過(guò)程中將線網(wǎng)劃分為互斥線網(wǎng)集合與重疊線網(wǎng)集合，隨后針對(duì)兩組不同的集合采取不同的并行布線策略，并且在布線的過(guò)程中可以很好地解決資源沖突以及負(fù)載不均衡的問(wèn)題.

3.2.2 細(xì)粒度FPGA并行布線技術(shù)

不同于粗粒度FPGA 并行布線技術(shù)，細(xì)粒度FPGA并行布線技術(shù)在布線時(shí)不會(huì)改變線網(wǎng)的布線順序.據(jù)統(tǒng)計(jì)，約70%的布線時(shí)間花費(fèi)在了搜索鄰居節(jié)點(diǎn)以及優(yōu)先級(jí)隊(duì)列的處理上［79］.因此，如何對(duì)PathFinder 算法的迷宮布線器進(jìn)行細(xì)粒度加速是當(dāng)前亟需解決的問(wèn)題［80～82］.

（1）基于Galois模型的FPGA并行布線

2014 年，Moctar 等［83］率先探索了使用Galois 模型對(duì)PathFinder 算法中的迷宮布線器進(jìn)行并行加速的操作，并在VPR 5.0 的基礎(chǔ)上對(duì)該項(xiàng)工作進(jìn)行了實(shí)現(xiàn).多線程的并行策略基于Galois 迭代合并機(jī)制，即允許單個(gè)線程同時(shí)處理多個(gè)迭代.每個(gè)線程都會(huì)維護(hù)一個(gè)本地優(yōu)先級(jí)隊(duì)列，優(yōu)先級(jí)隊(duì)列中存儲(chǔ)了需要進(jìn)行拓展的節(jié)點(diǎn)，若本地優(yōu)先級(jí)為空，線程將訪問(wèn)存儲(chǔ)在共享內(nèi)存空間中的全局優(yōu)先級(jí)隊(duì)列.上述工作使用互斥鎖實(shí)現(xiàn)不同線程間的同步，但當(dāng)某些情況下無(wú)法獲取互斥鎖時(shí)，Galois 會(huì)根據(jù)先前保存的數(shù)據(jù)副本將沖突進(jìn)行回滾，以盡可能降低不同線程間的數(shù)據(jù)沖突.同VPR 5.0 相比，基于Galois 模型的FPGA 并行布線方法最高能夠獲得5.46 倍的加速比.但根據(jù)此方法得到的布線結(jié)果具有不確定性，布線結(jié)果依賴于線程完成工作的先后順序.此外，Galois 在回滾的過(guò)程中將會(huì)產(chǎn)生大量的開銷，嚴(yán)重影響了該方法的可擴(kuò)展性.2018年，上述團(tuán)隊(duì)研究人員［84］對(duì)此項(xiàng)工作進(jìn)行了擴(kuò)展，消除了因數(shù)據(jù)回滾操作而帶來(lái)的影響，通過(guò)Galois 模型多線程能夠同時(shí)對(duì)單個(gè)線網(wǎng)執(zhí)行并行布線的操作，在布線結(jié)果具有確定性的情況下，能夠?qū)崿F(xiàn)3.67 倍的加速比.

（2）基于Posix線程的FPGA并行布線

2010 年，Gort 等［79］提出使用Posix 線程來(lái)加速迷宮布線器中成本函數(shù)的計(jì)算過(guò)程.當(dāng)存在N個(gè)可用的線程時(shí)，將其拆分為一個(gè)主線程與N-1 個(gè)輔助線程（如圖3 所示）.主線程執(zhí)行迷宮布線器的串行部分以及1/N的并行部分.每個(gè)線程都會(huì)維護(hù)自己的優(yōu)先級(jí)隊(duì)列，主線程首先會(huì)查看所有優(yōu)先級(jí)隊(duì)列的頂部節(jié)點(diǎn)，隨后借助同步路障選取出成本函數(shù)最低的節(jié)點(diǎn)，在此基礎(chǔ)上，主線程會(huì)拓展這個(gè)成本函數(shù)最低的節(jié)點(diǎn)并通知所有的輔助線程做好準(zhǔn)備工作.接下來(lái)，所有的線程會(huì)計(jì)算待拓展節(jié)點(diǎn)的成本函數(shù)并將其添加到各自的優(yōu)先級(jí)隊(duì)列中.一旦主線程完成了添加節(jié)點(diǎn)的操作，它會(huì)在第二道同步路障處等待其他線程，不斷重復(fù)上述步驟，直至迷宮布線器完成布線.

圖3 基于Posix線程的FPGA并行布線

Zhu 等［85］同時(shí)考慮粗粒度與細(xì)粒度的FPGA 并行布線，提出利用線程來(lái)代替進(jìn)程以減少通信開銷，根據(jù)線網(wǎng)的扇出將線網(wǎng)劃分為高扇出線網(wǎng)與低扇出線網(wǎng)兩種類型.高扇出線網(wǎng)會(huì)被進(jìn)一步劃分為互不重疊的低扇出線網(wǎng)的集合，從而能夠執(zhí)行并行布線的操作.對(duì)于低扇出線網(wǎng)，該團(tuán)隊(duì)研究人員使用互不重疊的邊界框?qū)€網(wǎng)進(jìn)行標(biāo)記，并同時(shí)執(zhí)行布線操作.上述布線方法最終在VPR 5.0架構(gòu)的基礎(chǔ)上通過(guò)Posix多線程技術(shù)進(jìn)行了實(shí)現(xiàn).與文獻(xiàn)［81］的方法相類似，在實(shí)現(xiàn)的過(guò)程中由主線程負(fù)責(zé)所有的輔助線程，并通過(guò)設(shè)置同步路障的方式完成線程間的同步.此并行布線方法同樣包含兩道同步路障，第一道同步路障負(fù)責(zé)喚醒所有的輔助線程對(duì)線網(wǎng)執(zhí)行并行布線操作.當(dāng)所有輔助線程完成布線任務(wù)后，第二道同步路障負(fù)責(zé)通知主線程將布線結(jié)果合并、更新阻塞信息等，進(jìn)入下一次布線迭代.通過(guò)該方法得到的布線結(jié)果具有較好的確定性.

4 未來(lái)發(fā)展趨勢(shì)

迄今為止，國(guó)內(nèi)外科研人員對(duì)FPGA 布局與布線技術(shù)有了較為深入的研究，并提出了一些具有代表性的研究成果.從當(dāng)前的研究成果可以得出：關(guān)于FPGA 布局技術(shù)，主要可以分為基于劃分的布局技術(shù)、基于啟發(fā)式的布局技術(shù)以及基于解析式的布局技術(shù)三種類型，三種類型的FPGA 布局技術(shù)具備各自的優(yōu)缺點(diǎn)，在應(yīng)用的過(guò)程中可根據(jù)需求進(jìn)行選擇.關(guān)于FPGA 布線技術(shù)，均是以基于擁塞協(xié)商的PathFinder 布線技術(shù)為根基，在此基礎(chǔ)上又能夠細(xì)分為FPGA 串行布線技術(shù)與FPGA并行布線技術(shù).相比較于串行布線技術(shù)，并行布線技術(shù)能夠獲得更高的加速比，但在布線的過(guò)程中也面臨著資源競(jìng)爭(zhēng)、布線方法的確定性以及可擴(kuò)展性等諸多問(wèn)題.通過(guò)上述分析可知，對(duì)FPGA 布局和布線技術(shù)的研究仍然任重而道遠(yuǎn)，基于現(xiàn)有的研究基礎(chǔ)，布局與布線技術(shù)未來(lái)的發(fā)展趨勢(shì)可以歸納為以下幾個(gè)方面：

（1）利用人工智能技術(shù)優(yōu)化FPGA布局和布線的流程.FPGA電路規(guī)模越大，對(duì)布局與布線技術(shù)的要求就越高，系統(tǒng)運(yùn)行時(shí)間便越長(zhǎng).FPGA布局與布線問(wèn)題屬于典型的啟發(fā)式探索問(wèn)題，變量空間大，難以尋找全局最優(yōu)解，而人工智能技術(shù)是非常適合于此類高維數(shù)據(jù)空間問(wèn)題求解的.但現(xiàn)階段卻鮮有將人工智能技術(shù)應(yīng)用于FPGA布局與布線領(lǐng)域的研究.因此，隨著人工智能技術(shù)與相關(guān)工具的發(fā)展，可以嘗試突破現(xiàn)有方法的架構(gòu)，將人工智能等方法應(yīng)用到FPGA布局與布線的流程中，在不影響收斂速度前提下，提升FPGA布局與布線解的質(zhì)量.

（2）探索多驅(qū)動(dòng)的布局和布線策略.隨著FPGA應(yīng)用領(lǐng)域的不斷拓展，在布局與布線的過(guò)程中僅考慮線長(zhǎng)、時(shí)序等信息是遠(yuǎn)遠(yuǎn)不夠的.例如，現(xiàn)階段在航空、航天等各重要核心領(lǐng)域的電子系統(tǒng)中，F(xiàn)PGA 在正扮演一個(gè)其它芯片無(wú)法替代的角色.但隨著FPGA的大規(guī)模使用，其在空間應(yīng)用中的輻照問(wèn)題也越來(lái)越突出.宇宙空間中存在著大量的高能粒子，這些高能粒子會(huì)對(duì)FPGA電子器件的功能造成影響，產(chǎn)生軟錯(cuò)誤.但如果在布局與布線的過(guò)程中就考慮到了軟錯(cuò)誤的影響，便有可能將軟錯(cuò)誤產(chǎn)生的概率降至最低.因此，在實(shí)際應(yīng)用的過(guò)程中，需要將線長(zhǎng)、時(shí)延、軟錯(cuò)誤、擁擠度、功耗等諸多因素聯(lián)合起來(lái)進(jìn)行考慮，以滿足未來(lái)FPGA 全方位發(fā)展的需求，同時(shí)這也是在今后研究中需要進(jìn)一步探索的方向.

（3）研究更加簡(jiǎn)單可行的FPGA 并行布局與布線方法.通過(guò)并行計(jì)算的方法能夠顯著提升FPGA 布局和布線的速度，減少使用EDA 工具將FPGA 電路編譯為二進(jìn)制碼流所需要的時(shí)間.但隨著FPGA 電路的規(guī)模越來(lái)越大，現(xiàn)有的并行布局與布線方法的執(zhí)行難度也在不斷加大，并行方法的確定性以及可擴(kuò)展性等問(wèn)題越來(lái)越突出.在未來(lái)的工作中，可以嘗試研究更加簡(jiǎn)單可行的FPGA 并行布局、布線方法，從而加大布局、布線方法在執(zhí)行過(guò)程中的并行度，進(jìn)一步減少FPGA EDA工具在布局和布線階段所需花費(fèi)的時(shí)間.

5 結(jié)論

隨著科技的不斷發(fā)展，現(xiàn)代工業(yè)中所使用的FPGA電路的規(guī)模也在不斷增大，對(duì)FPGA 布局和布線技術(shù)提出了更高的要求.本文圍繞著FPGA 布局與布線問(wèn)題展開，從FPGA 布局關(guān)鍵技術(shù)與布線關(guān)鍵技術(shù)2 個(gè)方面對(duì)研究進(jìn)展做了分析與總結(jié).在此基礎(chǔ)上，對(duì)未來(lái)的發(fā)展趨勢(shì)進(jìn)行了展望，以其對(duì)未來(lái)本領(lǐng)域的研究具有借鑒意義.我們堅(jiān)信，隨著研究人員對(duì)布局與布線技術(shù)的不斷探索，終將滿足未來(lái)FPGA 發(fā)展的需求，為FPGA更普遍的應(yīng)用提供有力支撐.