利用HOP模型提高布線速度

惠鋒，許晨瑞，胡凱

（1.無錫中微億芯有限公司，江蘇無錫214072；2.中國電子科技集團(tuán)公司第五十八研究所，江蘇無錫214072）

利用HOP模型提高布線速度

惠鋒1，許晨瑞1，胡凱2

（1.無錫中微億芯有限公司，江蘇無錫214072；2.中國電子科技集團(tuán)公司第五十八研究所，江蘇無錫214072）

隨著FPGA規(guī)模的不斷擴(kuò)大，基于千萬門級FPGA芯片開發(fā)的用戶設(shè)計(jì)，如何快速有效地完成布線，提高布線效率是一個關(guān)鍵問題。該文在探路算法的基礎(chǔ)上利用HOP模型來提高布線速度，減少了布線運(yùn)行時間。

布線；HOP；探路算法

1 引言

FPGA的布線是在芯片布局以后，用布線資源(包括布線通道、布線開關(guān)、邏輯單元端口)把已經(jīng)占用的邏輯單元連接起來。布線的理想目標(biāo)是：使布線能夠順利完成，有最好的連通性；使關(guān)鍵路徑延時最短；使互連線的總長度最小，節(jié)約布線資源。但隨著FPGA的規(guī)模越來越大，用戶設(shè)計(jì)和設(shè)計(jì)約束越來越復(fù)雜，用戶實(shí)現(xiàn)一次完整的FPGA設(shè)計(jì)流程將花費(fèi)很長的時間，其中布線模塊占用了大量的運(yùn)行時間，因此如何提高布線效率、減少布線時間是一個關(guān)鍵問題。

常用的布線算法分為基于路徑驅(qū)動的布線算法和基于時序驅(qū)動的布線算法[1]。迷宮算法是最基本的布線算法，在迷宮算法的基礎(chǔ)上提出的直接搜索的布線算法都有良好的布通性。因此，在分析這些常用算法的基礎(chǔ)上，衍生了一種基于路徑驅(qū)動的改進(jìn)布線算法[2]。基本的迷宮布線算法使用的是寬度優(yōu)先搜索算法，它在一個網(wǎng)的源端點(diǎn)和目的端點(diǎn)之間找到一條最短路徑。在搜索時從網(wǎng)的源端點(diǎn)開始向鄰居端點(diǎn)延伸，以此類推直到所有的目的端點(diǎn)都到達(dá)，或者沒有找到路徑終止。然而，迷宮搜索算法的最大缺點(diǎn)就是運(yùn)行速度非常慢，因?yàn)樵诓季€資源圖中有很多節(jié)點(diǎn)要被遍歷。

探路布線算法[2]是一般的布線算法，被用于大多數(shù)的FPGA中，通用的布局布線(VPR)中就是用該算法實(shí)現(xiàn)布線功能。探路算法是基于寬度優(yōu)先的迷宮布線算法，使用的是考慮花費(fèi)的啟發(fā)式搜索算法。

探路算法所使用的擁塞解決算法是基于多次迭代算法的擁塞協(xié)商算法，擁塞協(xié)商算法首先把所有的網(wǎng)布到FPGA里面，而不考慮是否發(fā)生了擁塞。當(dāng)布線完成以后，會對過多使用的布線資源進(jìn)行一個懲罰，下次迭代時將以一個比較小的概率選擇該布線資源。如果擁塞發(fā)生，那么撤銷所有的布線，重新進(jìn)行布線，然后再有擁塞發(fā)生，再次懲罰，最終經(jīng)過若干次迭代之后，布線成功或者資源不夠用。為了提高布線效率，對探路算法進(jìn)行改進(jìn)，探路算法的成本函數(shù)如下:

Cost表示的是從源端點(diǎn)到特定布線資源的花費(fèi)。Cost_prev表示從源端點(diǎn)到當(dāng)前布線資源的花費(fèi)，C0表示布線資源的基本花費(fèi)，初始化為1，但是當(dāng)該資源已經(jīng)被使用以后，它的值就變得非常大，通過快速增大C0的值，可以降低迭代的次數(shù)。而在探路算法中，基本值增大的比較慢，所以就會有很多的迭代次數(shù)?！鱀表示從當(dāng)前的布線資源到目標(biāo)端點(diǎn)的花費(fèi)，如何有效地提高△D的正確率，使布線器朝正確的方向進(jìn)行搜索，將會大幅減少布線時間。

通過對軟件測試集布局后的網(wǎng)表進(jìn)行分析，線網(wǎng)中驅(qū)動點(diǎn)與負(fù)載點(diǎn)的相對位置在9×9范圍以內(nèi)的在總線網(wǎng)中占了一定的比率，如何快速處理這類線網(wǎng)，將會有效提高布線的速度，從而減少運(yùn)行時間。本文在探路算法的基礎(chǔ)上使用Xilinx專為V5系列[3]開發(fā)的HOP布線模型，對符合條件的線網(wǎng)通過查表方式，優(yōu)先確定布線器的搜索方向及節(jié)點(diǎn)，提高探路算法△D的正確率，從而快速完成布線，表1為測試集電路中符合曼哈頓距離9×9以內(nèi)線網(wǎng)的統(tǒng)計(jì)數(shù)據(jù)，Total Nets、Nets(Hop)以及Rate分別表示測試電路的總線網(wǎng)數(shù)、符合HOP模型的線網(wǎng)數(shù)以及它在整個電路中所占的比率。

表1 HOP線網(wǎng)資源

2 HOP模型

Xilinx專為V5系列開發(fā)了新型對角對稱互連模式[4~6]，能以較少中繼段(HOP)到達(dá)較多區(qū)域，從而提高性能。這種新模式允許在2到3個中繼段之內(nèi)連接更多邏輯，更規(guī)則的布線模式使布線軟件可以更容易地找到最佳路徑。

通過對V5系列布線資源文件（XDLRC）的詳細(xì)分析，以INT_X30Y30為中心遍歷最大HOP為3的所有有效布線資源數(shù)據(jù)，V5系列HOP分布圖如圖1所示，數(shù)字為0是起始點(diǎn)，數(shù)字為1是經(jīng)過一個中繼段共12個，數(shù)字為2是經(jīng)過二個中繼段共96個，數(shù)字為3是經(jīng)過三個中繼段共180個，表2為INT_X30Y30中WL2BEG2為起始點(diǎn)實(shí)際布線資源的片段。

圖1 V5系列HOP分布

3 改進(jìn)算法實(shí)現(xiàn)

首先通過對HOP模型進(jìn)行數(shù)據(jù)建模，對符合曼哈頓距離9×9以內(nèi)的線網(wǎng)進(jìn)行標(biāo)記，在全局布線時對符合要求的線網(wǎng)通過查表方式進(jìn)行快速布線，否則按照正常的探路算法進(jìn)行布線。在詳細(xì)布線階段，如果線網(wǎng)存在共享資源，對符合要求的線網(wǎng)，優(yōu)先通過查表獲取空閑資源，否則按照正確的協(xié)商探路布線流程，直至所有的線網(wǎng)都完成布線，改進(jìn)算法處理流程如圖2所示。

4 算法驗(yàn)證

為了驗(yàn)證算法，本文使用了通用的MCNC測試集，在Xilinx的xc5vlx330ff1760器件上分別使用基于布通率的協(xié)商探路算法以及優(yōu)化后的算法進(jìn)行布線，測試結(jié)果如表3所示。SLICEs表示電路所占的資源，Total Nets、Nets(Hop)以及Rate分別表示電路的所有線網(wǎng)、符合HOP模型的線網(wǎng)以及在整個電路中占用的比率，Normal、HOP分別是基于布通率的協(xié)商探路算法和優(yōu)化后的算法所運(yùn)行的時間，Over表示優(yōu)化后減少運(yùn)行時間的比率。

表2 HOP布線資源

圖2 改進(jìn)算法流程圖

從測試結(jié)果可以看出，對于規(guī)模較小或符合HOP模型的線網(wǎng)不多的測試用例來說，添加HOP模型對布通率的協(xié)商探路算法沒能有效地降低布線時間，而對規(guī)模較大、符合HOP模型的線網(wǎng)多的測試用例，添加HOP模型可以有效降低布線時間，最大可以降低15%，平均能降低4.2%的運(yùn)行時間。

表3 測試結(jié)果表

5 結(jié)束語

分析Xilinx專為V5系列開發(fā)的新型對角對稱互連模式，在基于布通率的協(xié)商探路算法的基礎(chǔ)上，對線網(wǎng)在曼哈頓距離為9×9以內(nèi)的線網(wǎng)使用HOP模型進(jìn)行布線，可以有效降低布線運(yùn)行時間；添加HOP模型可以有效降低布線時間，最大可以降低15%，平均能降低4.2%的運(yùn)行時間。

[1]王伶俐，楊萌，周學(xué)功.深亞微米FPGA結(jié)構(gòu)與CAD設(shè)計(jì)[M].北京：電子工業(yè)出版社，2008：51-104.

[2]Larry McMurchie,Carl EBeling.Dept of Computer Science and Engineering University of Washington,WA，PathFInder:A Negotiation-Based Performance-Driven Route For FPGAs[M].Field Programmable Gate Arrays, 1995.

[3]Xilinx公司.Virtex-5 User Guide[P].Xilinx公司用戶手冊UG190(V2.1).

[4]Xilinx公司.Achieve Higher Performance with Virtex-5 FPGAs[P].Xcell Journal(59),2006:9-10.

[5]Xilinx公司.使用Virtex-5系列FPGA獲得更高系統(tǒng)性能[P].Xilinx白皮書WP245.

[6]Xilinx公司.ASMBL創(chuàng)新下一代平臺FPGA[J].今日電子,2004,(5):28-29.

Improvement of Routing Speed Using HOP Model

HUI Feng1,XU Chenrui1,HU Kai2
（1.East Technologies Inc.,Wuxi 214072,China；2.China Electronics Technology Group Corporation No.58 Research Institute,Wuxi 214072,China）

The increasing expansion of logic resources on 10M-gate FPGA-based ICs is posing new challenge to routing efficiency.In the paper,HOP model based on PathFinder algorithm is used to improve the routing efficiency.

route;HOP;PathFinder algorithm

TN402

A

1681-1070（2017）08-0021-04

惠鋒(1977—),男，江蘇無錫人，本科學(xué)歷，軟件工程師，現(xiàn)從事EDA軟件領(lǐng)域工作。

2017-3-29