一種基于線網(wǎng)劃分的并行FPGA布線算法

朱 春，來金梅

?

一種基于線網(wǎng)劃分的并行FPGA布線算法

朱 春，來金梅

(復(fù)旦大學(xué)專用集成電路與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，上海 201203)

針對(duì)在現(xiàn)場(chǎng)可編程門陣列(FPGA)軟件系統(tǒng)中大規(guī)模電路設(shè)計(jì)布線時(shí)間較長(zhǎng)的問題，提出一種基于線網(wǎng)引腳位置劃分且具有平臺(tái)獨(dú)立性的多線程FPGA布線算法。對(duì)高扇出線網(wǎng)采用將單根線網(wǎng)拆分成子線網(wǎng)并同時(shí)布線的方法，對(duì)低扇出線網(wǎng)采用選擇若干位置不相交疊的線網(wǎng)進(jìn)行同時(shí)布線的方法，給出線網(wǎng)邊界框圖的數(shù)據(jù)結(jié)構(gòu)來縮短選擇若干低扇出線網(wǎng)的時(shí)間，采取負(fù)載平衡機(jī)制和同步措施，分別提高布線效率和保證布線結(jié)果的確定性。實(shí)驗(yàn)結(jié)果證明，在Intel 4核處理器平臺(tái)上，與單線程VPR算法相比，該并行算法的平均布線效率提高了90%，平均布線質(zhì)量下降不超過2.3%，并能夠得到確定的布線結(jié)果，在EDA方面具有重要的理論與實(shí)用價(jià)值。

現(xiàn)場(chǎng)可編程門陣列；多線程；布線；高扇出線網(wǎng)；低扇出線網(wǎng)；邊界框圖；確定性

1 概述

由于集成電路工藝水平已進(jìn)入納米范疇以及可編程邏輯設(shè)計(jì)具有的高度靈活性，F(xiàn)PGA的容量和復(fù)雜度得以迅速提高以滿足更廣泛的應(yīng)用需求。設(shè)計(jì)從行為級(jí)描述到最終的物理實(shí)現(xiàn)需要經(jīng)歷邏輯綜合、映射、打包、布局、布線、位流生成以及編程下載等過程。應(yīng)用于FPGA的大規(guī)模設(shè)計(jì)流程往往需要大量的時(shí)間，這其中布局布線占有相當(dāng)?shù)谋壤齕1-2]。因此，提高編譯效率、降低運(yùn)行時(shí)間成為用戶的迫切需求。另一方面，多核處理器已成為當(dāng)代計(jì)算機(jī)的主流，為并行算法的研究提供了良好的基礎(chǔ)和方向。

本文通過分析線網(wǎng)的引腳數(shù)量和位置信息來實(shí)現(xiàn)具有平臺(tái)獨(dú)立性的多線程布線算法。

2 相關(guān)背景

經(jīng)典的單線程FPGA布線算法是基于擁擠度協(xié)商的算法，如PathFinder[3]、VPR(Versatile Place and Route)[4-5]、Directed A*[6]等。它們的執(zhí)行效率按序逐步提高，然而單線程的特點(diǎn)使其均未充分利用多核處理器的潛在運(yùn)算能力。文獻(xiàn)[7]研究了FPGA并行布線算法，利用通過網(wǎng)絡(luò)連接的分布式單核處理器作為實(shí)驗(yàn)平臺(tái)，但沒有同步處理器間的通信，導(dǎo)致每次運(yùn)行中代價(jià)更新信號(hào)到達(dá)相應(yīng)處理器的時(shí)間具有不確定性，每次運(yùn)行的布線結(jié)果不相同，因此，不能夠支持用戶在軟件平臺(tái)上調(diào)試，無法應(yīng)用于商業(yè)工具?；诙嗪颂幚砥鞯亩嗑€程ASIC布線算法[8]，對(duì)FPGA布線算法研究具有一定的指導(dǎo)意義，但是它并沒有針對(duì)高扇出線網(wǎng)與低扇出線網(wǎng)分別進(jìn)行處理，因?yàn)楦呱瘸鼍€網(wǎng)的布線時(shí)間過長(zhǎng)一直是FPGA布線面臨的難題。由于該算法是非迭代性算法，因此迭代性算法中降低線網(wǎng)選擇時(shí)間的需求并不十分迫切。此外，ASIC算法應(yīng)用于FPGA中的離散互聯(lián)資源時(shí)無法解決收斂性問題。

文獻(xiàn)[1]研究了基于現(xiàn)代多核處理器架構(gòu)的并行布線算法，并分別提出了粗粒度與細(xì)粒度的2種方案。在粗粒度的方法中，線網(wǎng)集合被分配成若干子集，每個(gè)子集被分配給一個(gè)VPR實(shí)體[1]。在每個(gè)VPR實(shí)體內(nèi)部線網(wǎng)按序進(jìn)行布線，VPR實(shí)體之間的布線過程同時(shí)進(jìn)行。一種稱為work- counter的設(shè)計(jì)通過使用共享內(nèi)存作為通信媒介來控制VPR實(shí)體之間的同步。此粗粒度方法使用多進(jìn)程機(jī)制實(shí)現(xiàn)，在速度上取得了明顯的改進(jìn)，但進(jìn)程間通信(Inter-process Communication, IPC)需要額外維護(hù)共享內(nèi)存，系統(tǒng)的開銷較大[9]。在細(xì)粒度方法中，布線算法中的波前擴(kuò)展過程[10]被劃分成若干個(gè)子過程，使用等量的線程承擔(dān)單根線網(wǎng)布線中同一階段的某一部分。細(xì)粒度方法在速度方面的改進(jìn)收效甚微，且程序的性能取決于處理器中的存儲(chǔ)架構(gòu)。

本文提出的算法與文獻(xiàn)[1]中的粗粒度算法相似，但存在以下2點(diǎn)不同：(1)根據(jù)線網(wǎng)的特征，即扇出數(shù)量，調(diào)整并行策略。高扇出線網(wǎng)與低扇出線網(wǎng)分別被分配到2個(gè)不同的子集，每個(gè)子集內(nèi)線網(wǎng)布線的并行策略不同。因?yàn)樵谖墨I(xiàn)[1]中的粗粒度算法高扇出線網(wǎng)可能導(dǎo)致過長(zhǎng)的等待時(shí)間，所以對(duì)高扇出線網(wǎng)進(jìn)行特別處理以消除這種情況的發(fā)生；(2)使用多線程的方法，即線程間通信(Inter-thread Com- munication, ITC)的方式[9]。因?yàn)镮TC的維護(hù)成本與系統(tǒng)開銷相對(duì)于IPC輕得多。

文獻(xiàn)[11]的實(shí)驗(yàn)結(jié)果表明：在VPR框架下，當(dāng)高扇出線網(wǎng)的總數(shù)比率不到1%時(shí)，它們的布線時(shí)間占用約70%的總布線時(shí)間。巨大的線網(wǎng)邊界框[9]和較多的待布線終端數(shù)是導(dǎo)致布線時(shí)間成指數(shù)時(shí)間增長(zhǎng)的原因，其中，線網(wǎng)邊界框指包含整個(gè)線網(wǎng)的最小矩形框。因此，有必要對(duì)高扇出線網(wǎng)和低扇出線網(wǎng)采用不同的布線策略。方法如下：

高扇出線網(wǎng)被分解成若干子線網(wǎng)，每個(gè)子線網(wǎng)具有較小的邊界框和較少的終端數(shù)。通過平衡每個(gè)子線網(wǎng)的邊界框面積與扇出數(shù)量的乘積來平衡線程間的負(fù)載，使得高扇出線網(wǎng)的布線時(shí)間降低為其中一個(gè)子線網(wǎng)的最大布線時(shí)間。子線網(wǎng)全部完成布線后，合并它們的布線結(jié)果作為此高扇出線網(wǎng)的布線結(jié)果。

低扇出線網(wǎng)本身的性質(zhì)表明它們不適合被分割。通過計(jì)算布局后線網(wǎng)的位置判斷2個(gè)低扇出線網(wǎng)的邊界框是否有交疊。如果不交疊，這2根線網(wǎng)就可以同時(shí)進(jìn)行布線。線網(wǎng)邊界框圖被設(shè)計(jì)用來簡(jiǎn)化選擇低扇出線網(wǎng)的過程。

3 多線程布線算法

3.1 背景算法及多線程框架

使用VPR[5]中的布線算法作為基本算法。在基本串行算法中，線網(wǎng)按序依次進(jìn)行布線，布線過程中允許線網(wǎng)之間橋接。在所有線網(wǎng)均完成初始布線后，每根線網(wǎng)的布線結(jié)果均為最佳方案。然后，橋接的布線資源節(jié)點(diǎn)面臨擁擠代價(jià)懲罰[3-5]，算法開始實(shí)施新一輪布線，布線過程中路徑選擇較多的線網(wǎng)會(huì)盡量避開擁擠的節(jié)點(diǎn)。重復(fù)如上步驟直到所有的橋接全部移除，這些工作全部由單一線程完成。在本文的算法中，線網(wǎng)的選擇、劃分、合并以及代價(jià)更新等工作由主線程完成，具體的布線工作由主線程和子線程共同完成。其中，主線程為整個(gè)布線程序的線程，子線程由主線程創(chuàng)建和回收。所有的子線程只被創(chuàng)建一次并在程序終結(jié)前由主線程回收。

為了避免線程間出現(xiàn)死鎖或者數(shù)據(jù)競(jìng)爭(zhēng)等情況，在每個(gè)子線程的地址空間中拷貝一份主線程的布線資源圖[10]。主線程控制每份拷貝之間的信息同步以確保布線結(jié)果的確定性。POSIX線程[9]被用來搭建整個(gè)多線程的環(huán)境。使用Pthread barriers[12]來同步線程間的布線過程以及控制布線資源圖中關(guān)于擁擠信息的更新。barrier是控制若干線程同步的機(jī)制，當(dāng)預(yù)設(shè)數(shù)量的線程均到達(dá)相應(yīng)的barrier時(shí)才可以越過它繼續(xù)執(zhí)行，否則所有的線程都要休眠等待。本文采用了2道barrier：第1道barrier告知所有線程工作已經(jīng)由主線程分配完成，允許執(zhí)行布線；第2道barrier告知主線程所有的布線工作已經(jīng)完成，統(tǒng)一所有布線結(jié)果，進(jìn)行代價(jià)更新，重新為所有線程分配布線工作。顯然，當(dāng)并行環(huán)境設(shè)定為線程時(shí)，程序中存在1個(gè)主線程和－1個(gè)子線程。

線程的工作模型為對(duì)等工作模型[9]，即主線程給子線程分配好工作以后依然還要和子線程一起承擔(dān)布線的工作。多線程框架如圖1所示。從圖中可知，需要采用必要的措施來保證各線程在2道barrier之間的工作時(shí)間相近，這樣程序在第2道barrier處等待的時(shí)間就會(huì)很短。理論情況下時(shí)間相同，所有線程同時(shí)到達(dá)第2道barrier，等待時(shí)間為0，效率最高。

圖1 對(duì)等線程模型及同步機(jī)制

3.2 高扇出線網(wǎng)并行算法

由于高扇出線網(wǎng)的布線任務(wù)被分解成若干子線網(wǎng)的布線，因此任意子線網(wǎng)都需要一份線網(wǎng)源端的拷貝，即所有子線網(wǎng)的數(shù)據(jù)結(jié)構(gòu)中都存有相同的源端。另一方面，在VPR布線算法中，線網(wǎng)的邊界框具有限制布線器搜索路徑的范圍以及節(jié)省布線資源的作用。為了不讓任意2個(gè)子線網(wǎng)間的布線搜索工作存在重復(fù)，它們的線網(wǎng)邊界框應(yīng)不發(fā)生交疊。因此，本文以源端為基準(zhǔn)對(duì)高扇出線網(wǎng)進(jìn)行切割。具體的分割策略如圖2所示。在VPR算法中影響布線時(shí)間的2個(gè)重要指標(biāo)為：線網(wǎng)邊界框的大小和終端數(shù)量[4]。邊界框越大，布線時(shí)間越長(zhǎng)；終端數(shù)量越多，布線時(shí)間越長(zhǎng)。為了平衡線程的負(fù)載，給任意線網(wǎng)定義一個(gè)特征值=×，其中，代表子線網(wǎng)的終端數(shù)量；代表其邊界框的面積；當(dāng)一根線網(wǎng)的所有子線網(wǎng)間的值相近時(shí)，線程的布線時(shí)間相近，用于等待的時(shí)間就會(huì)縮短。在兩線程環(huán)境下，線網(wǎng)按圖2(a)和圖2(b)的策略進(jìn)行劃分，為了保證程序加速性能的最大化即線程負(fù)載的平衡，需要對(duì)這2種策略進(jìn)行一個(gè)選擇。在每種策略下，定義：

其中，1和2指任意策略下分得的2根子線網(wǎng)的特征值。

分別計(jì)算2種策略的Delta值，選取具有較小Delta值的策略。在三線程和四線程的環(huán)境下，線網(wǎng)預(yù)先被分解成 4根子線網(wǎng)，如圖2(c)~圖2(f)所示。如果是四線程，即將這4根子線網(wǎng)分配給這4個(gè)線程。如果是三線程，需要將這4根子線網(wǎng)中的任意2根進(jìn)行合并，合并的規(guī)則仍然是最終的任意2根線網(wǎng)邊界框間沒有交疊，這樣就會(huì)出現(xiàn) 圖2(c)~圖2(f)所示的4種情況，需要選擇其中一個(gè)作為最終方案。

圖2 高扇出線網(wǎng)劃分策略

對(duì)任意一種策略定義：

其中，anv指每種策略下所有子線網(wǎng)特征值的均值；set即代表所有子線網(wǎng)特征值的方差。選擇具有最小set值的策略為最終結(jié)果。

所有高扇出線網(wǎng)在布線前進(jìn)行有且僅有一次劃分，在后續(xù)布線輪次中不會(huì)變更。它們?cè)诩现邪淳W(wǎng)表讀入時(shí)的順序存儲(chǔ)，布線過程中不發(fā)生改變。布線流程如圖3所示。

圖3 高扇出線網(wǎng)布線流程

首先按序獲取一根線網(wǎng)，清空上一輪的布線結(jié)果后更新所有布線資源圖的擁擠代價(jià)，然后取出所有子線網(wǎng)按輪詢策略[9]分配給所有線程的容器。當(dāng)所有線程完成布線后，主線程合并布線結(jié)果并重新取下一根線網(wǎng)，子線程進(jìn)入休眠狀態(tài)等待被喚醒。

3.3 低扇出線網(wǎng)并行算法

低扇出線網(wǎng)的邊界框規(guī)模要小很多，不適合分割。因此，如果2個(gè)低扇出線網(wǎng)在布局后的位置相距較遠(yuǎn)，如線網(wǎng)邊界框沒有發(fā)生交疊，就認(rèn)為它們的布線過程不會(huì)產(chǎn)生布線資源的競(jìng)爭(zhēng)，可以同時(shí)進(jìn)行。

由于線網(wǎng)的數(shù)據(jù)結(jié)構(gòu)中表征邊界信息的是2個(gè)坐標(biāo)：(min,min)和(max,max)，計(jì)算2根線網(wǎng)邊界框是否重疊需要對(duì)其中的2組坐標(biāo)進(jìn)行比較運(yùn)算。假設(shè)計(jì)算任意2個(gè)線網(wǎng)邊界框之間是否重疊的時(shí)間復(fù)雜度為(1)，那么計(jì)算根線網(wǎng)中兩兩之間是否存在邊界框重疊的時(shí)間復(fù)雜度即為(2)。每次從線網(wǎng)集合中選擇根邊界框互相不重疊的線網(wǎng)，最少需要(2)復(fù)雜度的時(shí)間，如設(shè)計(jì)中共存在根線網(wǎng)，那么一個(gè)布線輪次總耗費(fèi)的時(shí)間復(fù)雜度為(/)×(2)。如果完成布線需要次布線迭代，選擇線網(wǎng)時(shí)間最少為×(/)×(2)。

為了避免在每個(gè)布線輪次做重復(fù)性的選擇工作，縮短選擇的時(shí)間，提出線網(wǎng)邊界框圖的數(shù)據(jù)結(jié)構(gòu)，使得低扇出線網(wǎng)的選擇更加方便且高效。線網(wǎng)邊界框圖是無向圖[13]，圖中節(jié)點(diǎn)代表線網(wǎng)，邊代表2根線網(wǎng)的邊界框發(fā)生交疊，如圖4所示。

圖4 線網(wǎng)邊界框圖

如果2根線網(wǎng)的邊界框沒有發(fā)生交疊，它們?cè)趫D中對(duì)應(yīng)的節(jié)點(diǎn)就是不相鄰的，因而可以被選擇來同時(shí)布線。終端數(shù)量多的線網(wǎng)往往邊界框的面積較大，相鄰的節(jié)點(diǎn)就越多，很難和其他線網(wǎng)同時(shí)被選中，這也是高扇出線網(wǎng)未采用這種方法的原因。在布線開始前，讀入設(shè)計(jì)網(wǎng)表之后，程序有且僅有一次構(gòu)建線網(wǎng)邊界框圖。為了盡量使規(guī)模相等或相近的線網(wǎng)能夠優(yōu)先被選擇，對(duì)低扇出線網(wǎng)的集合做預(yù)處理。低扇出線網(wǎng)在集合中的初始存儲(chǔ)順序?yàn)榫W(wǎng)表讀入時(shí)的順序，在構(gòu)建邊界框圖之前按照3.2節(jié)定義的特征值對(duì)線網(wǎng)在數(shù)據(jù)結(jié)構(gòu)中的存儲(chǔ)順序進(jìn)行從高到低的排序。本文分別對(duì)從高到低排序和從低到高排序進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)從高到低的排序比從低到高排序?qū)е赂痰倪\(yùn)行時(shí)間和更好的布線質(zhì)量。相應(yīng)節(jié)點(diǎn)在邊界框圖中的存儲(chǔ)順序相同。規(guī)模相近的線網(wǎng)就會(huì)更容易在同一回合內(nèi)被選中，線程間的負(fù)載就會(huì)因此得到平衡。另一方面，因?yàn)榫哂休^高特征值的線網(wǎng)鄰接點(diǎn)較多，它們被優(yōu)先選擇后圖中剩余的連通分支[12]就會(huì)變多，搜索效率增高，進(jìn)而提高速度。整個(gè)低扇出線網(wǎng)集合的布線流程如圖5所示。初始布線輪次，如果為線程環(huán)境，每回合開始前主線程從邊界框圖中選擇個(gè)互補(bǔ)相鄰的節(jié)點(diǎn)，并將選中的節(jié)點(diǎn)打上標(biāo)簽。在本輪后續(xù)選擇線網(wǎng)時(shí)，被打上標(biāo)簽的節(jié)點(diǎn)就會(huì)被過濾掉。根據(jù)選中的節(jié)點(diǎn)獲取對(duì)應(yīng)的線網(wǎng)分配給線程接口容器，線程接口容器為線程獲取主線程為其分配線網(wǎng)的接口。當(dāng)所有線程完成工作后主線程更新?lián)頂D代價(jià)并檢查收斂性。收斂性檢查后主線程重復(fù)如上循環(huán)，子線程進(jìn)入休眠狀態(tài)等待被喚醒。初始布線輪次完成以后，在同一回合布線的線網(wǎng)被綁定為同一組并貼上組標(biāo)簽，在后續(xù)布線輪次中程序識(shí)別組標(biāo)簽而取線網(wǎng)，不要額外的計(jì)算或者比較，時(shí)間復(fù)雜度為(1)。

圖5 低扇出線網(wǎng)布線流程

收斂性分析：由于物理上的一根互聯(lián)線段的兩端可能位于不同的線網(wǎng)邊界框中，因此也不能完全保證2個(gè)邊界框不交疊的線網(wǎng)在布線過程中沒有資源競(jìng)爭(zhēng)。內(nèi)部實(shí)驗(yàn)證明，如果不采取措施解決此類問題，對(duì)某些測(cè)試用例來說程序可能無法結(jié)束，即算法不收斂。因此，為了解決收斂性問題，在每回合布線結(jié)束后分析所布的根線網(wǎng)之間有沒有資源的沖突。如果某2根線網(wǎng)的布線結(jié)果存在資源沖突，即在邊界框圖中對(duì)應(yīng)節(jié)點(diǎn)之間加上一條邊使它們相鄰，從而保證在以后的布線輪次中這2根線網(wǎng)不會(huì)在同一回合內(nèi)布線。然后，撤銷此組線網(wǎng)的組標(biāo)簽使它們處于自由狀態(tài)。如果沒有檢測(cè)到收斂性問題，此回合內(nèi)的線網(wǎng)依然會(huì)在下一個(gè)迭代輪次內(nèi)同時(shí)布線。

在一輪布線完成后，程序?qū)]有組標(biāo)簽的自由線網(wǎng)集中在一起，重新進(jìn)行分組。這里沒有組標(biāo)簽的線網(wǎng)來源包含以下2個(gè)方面：(1)在收斂性檢測(cè)中被撤銷組標(biāo)簽的線網(wǎng)，即具有資源沖突而不滿足收斂性的線網(wǎng)；(2)初始輪次布線的最后幾個(gè)回合中很難在邊界框圖中同時(shí)找到存在個(gè)互相不相鄰且未參與布線的節(jié)點(diǎn)，這些節(jié)點(diǎn)在每輪布線后都參與重新分組。如果沒有滿足與線程數(shù)等數(shù)量的線網(wǎng)，多余的線程會(huì)空置并直接行進(jìn)到第2道barrier。

3.4 算法實(shí)現(xiàn)

布線前，程序要做如下預(yù)處理工作。首先，解析硬件描述文件以構(gòu)建布線資源圖。其次，讀入網(wǎng)表并依次計(jì)算線網(wǎng)的位置信息以及終端數(shù)量。根據(jù)終端數(shù)量將線網(wǎng)分為高扇出線網(wǎng)集合與低扇出線網(wǎng)集合。低扇出線網(wǎng)集合用作輸入來構(gòu)建線網(wǎng)邊界框圖。主線程創(chuàng)建－1個(gè)子線程，設(shè)定它們的競(jìng)爭(zhēng)范圍[9]為系統(tǒng)級(jí)并分別拷貝一份布線資源圖。這樣每個(gè)線程即為一個(gè)VPR實(shí)體，設(shè)定參數(shù)均相同。在每輪布線迭代中，所有的線網(wǎng)都要拆分重布而不只是布有沖突的線網(wǎng)以保證收斂性以及更良好的布線質(zhì)量。低扇出線網(wǎng)集合優(yōu)先于高扇出線網(wǎng)集合布線，實(shí)驗(yàn)證明這能達(dá)到更良好的布線質(zhì)量。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)平臺(tái)

本文的實(shí)驗(yàn)基于以下2種平臺(tái)：(1)Intel Core 2 Quad Q8400處理器，Windows XP系統(tǒng)，4 GB主存；(2)Intel Core i5-2400處理器，Windows 7系統(tǒng)，4 GB主存。測(cè)試電路選自于MCNC基準(zhǔn)電路以及opencore平臺(tái)上經(jīng)過FPGA驗(yàn)證后的電路。打包和布局采用的工具是賽靈思(Xilinx) ISE 10.1，使用的FPGA架構(gòu)為賽靈思XC2V500，重復(fù)單元內(nèi)互聯(lián)結(jié)構(gòu)包含水平和豎直方向各40根兩倍線、120根6倍線以及24根長(zhǎng)線。打包后測(cè)試電路的資源情況如表1所示。其中，H-nets代表高扇出線網(wǎng)；L-nets代表低扇出線網(wǎng)。在本文中，如果一根線網(wǎng)的終端數(shù)量達(dá)到或者超過40[11]，則將其定義為高扇出線網(wǎng)。

表1 測(cè)試電路資源情況

4.2 布線質(zhì)量

為了比較布線質(zhì)量，統(tǒng)計(jì)布線成功后總共實(shí)際使用的互聯(lián)資源長(zhǎng)度，即將電路中每根線網(wǎng)實(shí)際使用到的互聯(lián)線段長(zhǎng)度加總。因?yàn)橐粋€(gè)最終的設(shè)計(jì)使用的互聯(lián)資源總長(zhǎng)度越少說明布線的質(zhì)量越高，即布線在滿足連通所有線網(wǎng)的前提下盡量節(jié)省資源的使用量。實(shí)驗(yàn)結(jié)果表明，在2種不同平臺(tái)上得到的布線質(zhì)量統(tǒng)計(jì)結(jié)果完全相同，而不同數(shù)量線程環(huán)境下的布線質(zhì)量如表2所示。百分比的計(jì)算均基于均值。其中，對(duì)于特定數(shù)量的線程，所有的電路都經(jīng)過至少5次的重復(fù)運(yùn)行實(shí)驗(yàn)。結(jié)果表明，對(duì)特定電路，不同平臺(tái)運(yùn)行的結(jié)果均相同，進(jìn)而表明了本文的算法具有平臺(tái)獨(dú)立性和確定性。從最后一行的結(jié)果看，布線質(zhì)量惡化最高只有2.3%，屬于設(shè)計(jì)可以接受的范圍。

表2 2種平臺(tái)的布線質(zhì)量

4.3 布線時(shí)間

布線時(shí)間包括構(gòu)建布線資源圖、邊界框圖以及對(duì)所有線網(wǎng)進(jìn)行布線的時(shí)間。對(duì)于所有的測(cè)試電路，不同平臺(tái)以及不同數(shù)量的線程環(huán)境下的布線時(shí)間、平均值以及加速比如表3~表8所示。加速比的計(jì)算均基于均值。

表3 Q8400平臺(tái)高扇出線網(wǎng)布線時(shí)間 ms

表4 i5-2400平臺(tái)高扇出線網(wǎng)布線時(shí)間 ms

表5 Q8400平臺(tái)低扇出線網(wǎng)布線時(shí)間 ms

表6 i5-2400平臺(tái)低扇出線網(wǎng)布線時(shí)間 ms

表7 Q8400平臺(tái)總布線時(shí)間 ms

表8 i5-2400平臺(tái)總布線時(shí)間 ms

表3、表4展示了算法對(duì)于高扇出線網(wǎng)集合的布線加速能力，表5、表6展示了算法對(duì)于低扇出線網(wǎng)集合的布線加速能力，表7、表8展示了算法對(duì)于整個(gè)線網(wǎng)集合的加速 能力。

通過觀察表3、表4可以發(fā)現(xiàn)，2種平臺(tái)在2~4線程環(huán)境下算法對(duì)于高扇出線網(wǎng)的布線加速百分比分別為48%、57%、99%以及55%、58%、100%。表5、表6表明， 2種平臺(tái)在2~4線程環(huán)境下算法對(duì)于低扇出線網(wǎng)的布線加速百分比分別為35%、58%、86%以及52%、65%、88%。對(duì)于整個(gè)電路，表7、表8表明，2種平臺(tái)在2~4線程環(huán)境下算法的布線加速百分比分別為38%、57%、89%以及53%、64%、91%。

通過對(duì)以上2組平臺(tái)的測(cè)試數(shù)據(jù)觀察得知，算法的加速百分比隨著線程數(shù)量的增加而明顯增加，因而算法具有良好的加速擴(kuò)展性。2種平臺(tái)實(shí)驗(yàn)數(shù)據(jù)相近，從另一方面說明了算法具有平臺(tái)獨(dú)立性。Intel Core i5-2400平臺(tái)上的布線時(shí)間相對(duì)于Intel Core 2 Qaud平臺(tái)較短是因?yàn)榍罢呦鄬?duì)于后者的處理能力更高，它具有更高的時(shí)鐘頻率和更高級(jí)的緩存設(shè)計(jì)。計(jì)算表7、表8中同等數(shù)量線程下的加速百分比差值，2~4線程分別為15%、7%、2%，呈逐漸減小的趨勢(shì)，預(yù)示算法的加速性能隨著線程數(shù)量的增加會(huì)遇到瓶頸。

最后，將本文提出的算法與其他并行FPGA布線算法進(jìn)行比較。文獻(xiàn)[7]的研究成果顯示出了良好的加速擴(kuò)展性，但是該平臺(tái)是基于網(wǎng)絡(luò)連接的分布式處理器，而不是現(xiàn)代多核處理器。另一方面，該算法不保證結(jié)果的確定性。文獻(xiàn)[1]第1個(gè)發(fā)布了基于現(xiàn)代多核處理器平臺(tái)的FPGA并行布線算法研究，提出了粗粒度與細(xì)粒度2種方法，粗粒度方法具有良好的加速擴(kuò)展性，而細(xì)粒度方法的加速擴(kuò)展性較差且依賴于平臺(tái)。粗粒度方法在2~4線程環(huán)境下的加速百分比為51%、64%、92%(Intel Core i5平臺(tái))和49%、72%、111%(Intel Core 2平臺(tái))。本文提出的算法與粗粒度算法的加速擴(kuò)展性相近，但是子線程通過主線程的地址空間進(jìn)行通信，無需維護(hù)共享內(nèi)存的通信機(jī)制。此外，線程的上下文切換成本較進(jìn)程的上下文切換成本較低[9]，系統(tǒng)開銷較小，具有較高的實(shí)用性。

5 結(jié)束語

本文提出了對(duì)FPGA布線進(jìn)行加速的多線程布線算法，針對(duì)不同扇出類型的線網(wǎng)采用不同的并行策略。測(cè)試表明此算法具有良好的加速擴(kuò)展性、平臺(tái)獨(dú)立性以及能夠提供確定的布線結(jié)果，系統(tǒng)開銷較小，與其他算法相比具有良好的實(shí)用性。在此基礎(chǔ)上，將進(jìn)一步開發(fā)基于時(shí)序驅(qū)動(dòng)的并行布線算法，擬降低工業(yè)界比較常用的時(shí)序驅(qū)動(dòng)布線時(shí)間較長(zhǎng)的問題。

[1] Gort M, Anderson J H. Deterministic Multi-core Parallel Routing for FPGAs[C]//Proc. of International Conference on FieldProgrammable Technology. Toronto, Canada: ACM Press, 2010: 78-86.

[2] Betz V, Ludwin A, Padalia K. High-quality, Deterministic Parallel Placement for FPGAs on Commodity Hardware[C]// Proc. ofthe 16th International Symposium on Field Programmable Gate Arrays. New York, USA: ACM Press, 2008: 14-23.

[3] McMurchie L, Ebeling C. PathFinder: A Negotiation-based Performance-driven Router for FPGAs[C]//Proc. ofthe 3rd International Symposium on Field Programmable Gate Arrays.[S. l.]: IEEE Press, 1995: 111-117.

[4] Betz V, Rose J. VPR: A New Packing, Placement and Routing Tool for FPGA Research[C]//Proc. of the 7th InternationalWorkshop on FieldProgrammable Logic and Applications.London, UK: Springer-Verlag, 1997: 213-222.

[5] Luu J, Kuon I, Jamieson P, et al. VPR5.0: FPGA CAD and Architecture Exploration Tools with Single-driver Routing, Heterogeneity and Process Scaling[J]. ACM Transactions on Reconfigurable Technology and Systems, 2011, 4(4): 133-142.

[6] Tessier R. Negotiated A* Routing for FPGAs[C]//Proc. of the 5th Canadian Workshop on Field Programmable Devices. [S. l.]: IEEE Press, 1998: 139-144.

[7] Chan P, Schlag M. New Parallelization and Convergence Results for NC: A Negotiation-based FPGA Router[C]//Proc. ofthe 8th International Symposium on Field Programmable Gate Arrays. New York, USA: ACM Press, 2000: 165-174.

[8]Chiang C, Kawa J, Wen Y. Routing in Multithread Environ- ment[C]//Proc. of the 5th International Conference on ASIC. [S. l.]: IEEE Press, 2003: 203-207.

[9] Hughes C, Hughes T. Professional Multicore Programming: Design and Implementation for C++ Developers[M].[S. l.]: Wiley, 2008.

[10] Betz V,Rose J, Marquardt A. Architecture and CAD for Deep-submicron FPGAs[M]. Norwell, USA: Kluwer Academic Publishers, 1999.

[11] Chen Xun, Zhu Jianwen. Timing-driven Routing of High Fanout Nets[C]//Proc. of International Conference on Field Programmable Logic and Applications. [S. l.]: IEEE Press, 2011: 423-428.

[12]Lewi B, Berg D J. Pthreads Primer: A Guide to Multithreaded Programming[M]. [S. l.]: SunSoft Press, 1996.

[13]屈婉玲,耿素云,張立昂. 離散數(shù)學(xué)[M]. 北京:高等教育出版社, 2008.

編輯 顧逸斐

A Parallel FPGA Wiring Algorithm Based on Nets Partition

ZHU Chun, LAI Jin-mei

(State Key Laboratory of ASIC & System, Fudan University, Shanghai 201203, China)

A platform-independent multi-thread routing method for FPGA is proposed to reduce long compiling times of large design in Field Programmable Gate Array(FPGA) software system. Specifically, the proposed method includes two aspects for maximal paralleli- zation. For high fanout nets, each is partitioned into several subnets to be routed in parallel. Low fanout nets with non-overlapping boundary diagrams are identified and routed in parallel. A new graph, named boundary diagram, is constructed to facilitate the process of selecting low fanout nets to be routed concurrently. In addition, load balancing strategies and synchronization mechanisms are introduced to promote routing efficiency and ensure deterministic results. Experimental results on Intel quad-core processor platforms show that, this technique improves the average routing efficiency by 90% with routing quality degrading by no more than 2.3% and provides deterministic results, which has great theoretical and practical value in EDA field.

Field Programmable Gate Array(FPGA); multi-thread; wiring; high fanout nets; low fanout nets; boundary diagram; deterministic

1000-3428(2014)03-0287-07

A

TP301.6

國家“863”計(jì)劃基金資助項(xiàng)目(2012AA012001)。

朱 春(1987－)，男，碩士研究生，主研方向：FPGA布線算法；來金梅，教授、博士生導(dǎo)師。

2013-03-05

2013-03-28 E-mail：10212020063@fudan.edu.cn

10.3969/j.issn.1000-3428.2014.03.061