利用HOP模型提高布線速度

惠鋒，許晨瑞，胡凱

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

利用HOP模型提高布線速度

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

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

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

布線；HOP；探路算法

1 引言

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

常用的布線算法分為基于路徑驅動的布線算法和基于時序驅動的布線算法[1]。迷宮算法是最基本的布線算法，在迷宮算法的基礎上提出的直接搜索的布線算法都有良好的布通性。因此，在分析這些常用算法的基礎上，衍生了一種基于路徑驅動的改進布線算法[2]?；镜拿詫m布線算法使用的是寬度優先搜索算法，它在一個網的源端點和目的端點之間找到一條最短路徑。在搜索時從網的源端點開始向鄰居端點延伸，以此類推直到所有的目的端點都到達，或者沒有找到路徑終止。然而，迷宮搜索算法的最大缺點就是運行速度非常慢，因為在布線資源圖中有很多節點要被遍歷。

探路布線算法[2]是一般的布線算法，被用于大多數的FPGA中，通用的布局布線(VPR)中就是用該算法實現布線功能。探路算法是基于寬度優先的迷宮布線算法，使用的是考慮花費的啟發式搜索算法。

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

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

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

表1 HOP線網資源

2 HOP模型

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

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

圖1 V5系列HOP分布

3 改進算法實現

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

4 算法驗證

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

表2 HOP布線資源

圖2 改進算法流程圖

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

表3 測試結果表

5 結束語

分析Xilinx專為V5系列開發的新型對角對稱互連模式，在基于布通率的協商探路算法的基礎上，對線網在曼哈頓距離為9×9以內的線網使用HOP模型進行布線，可以有效降低布線運行時間；添加HOP模型可以有效降低布線時間，最大可以降低15%，平均能降低4.2%的運行時間。

[1]王伶俐，楊萌，周學功.深亞微米FPGA結構與CAD設計[M].北京：電子工業出版社，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獲得更高系統性能[P].Xilinx白皮書WP245.

[6]Xilinx公司.ASMBL創新下一代平臺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—),男，江蘇無錫人，本科學歷，軟件工程師，現從事EDA軟件領域工作。

2017-3-29