朱 春，來金梅

?

一種基于線網劃分的并行FPGA布線算法

朱 春，來金梅

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

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

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

1 概述

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

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

2 相關背景

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

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

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

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

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

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

3 多線程布線算法

3.1 背景算法及多線程框架

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

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

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

圖1 對等線程模型及同步機制

3.2 高扇出線網并行算法

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

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

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

圖2 高扇出線網劃分策略

對任意一種策略定義：

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

所有高扇出線網在布線前進行有且僅有一次劃分，在后續(xù)布線輪次中不會變更。它們在集合中按網表讀入時的順序存儲，布線過程中不發(fā)生改變。布線流程如圖3所示。

圖3 高扇出線網布線流程

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

3.3 低扇出線網并行算法

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

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

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

圖4 線網邊界框圖

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

圖5 低扇出線網布線流程

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

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

3.4 算法實現(xiàn)

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

4 實驗結果與分析

4.1 實驗平臺

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

表1 測試電路資源情況

4.2 布線質量

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

表2 2種平臺的布線質量

4.3 布線時間

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

表3 Q8400平臺高扇出線網布線時間 ms

表4 i5-2400平臺高扇出線網布線時間 ms

表5 Q8400平臺低扇出線網布線時間 ms

表6 i5-2400平臺低扇出線網布線時間 ms

表7 Q8400平臺總布線時間 ms

表8 i5-2400平臺總布線時間 ms

表3、表4展示了算法對于高扇出線網集合的布線加速能力，表5、表6展示了算法對于低扇出線網集合的布線加速能力，表7、表8展示了算法對于整個線網集合的加速 能力。

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

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

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

5 結束語

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

[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ù)學[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”計劃基金資助項目(2012AA012001)。

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

2013-03-05

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

10.3969/j.issn.1000-3428.2014.03.061