利用HOP模型提高布线速度

惠锋，许晨瑞，胡凯

（1.无锡中微亿芯有限公司，江苏无锡214072；2.中国电子科技集团公司第五十八研究所，江苏无锡214072）

利用HOP模型提高布线速度

惠锋1，许晨瑞1，胡凯2

（1.无锡中微亿芯有限公司，江苏无锡214072；2.中国电子科技集团公司第五十八研究所，江苏无锡214072）

随着FPGA规模的不断扩大，基于千万门级FPGA芯片开发的用户设计，如何快速有效地完成布线，提高布线效率是一个关键问题。该文在探路算法的基础上利用HOP模型来提高布线速度，减少了布线运行时间。

布线；HOP；探路算法

1 引言

FPGA的布线是在芯片布局以后，用布线资源(包括布线通道、布线开关、逻辑单元端口)把已经占用的逻辑单元连接起来。布线的理想目标是：使布线能够顺利完成，有最好的连通性；使关键路径延时最短；使互连线的总长度最小，节约布线资源。但随着FPGA的规模越来越大，用户设计和设计约束越来越复杂，用户实现一次完整的FPGA设计流程将花费很长的时间，其中布线模块占用了大量的运行时间，因此如何提高布线效率、减少布线时间是一个关键问题。

常用的布线算法分为基于路径驱动的布线算法和基于时序驱动的布线算法[1]。迷宫算法是最基本的布线算法，在迷宫算法的基础上提出的直接搜索的布线算法都有良好的布通性。因此，在分析这些常用算法的基础上，衍生了一种基于路径驱动的改进布线算法[2]。基本的迷宫布线算法使用的是宽度优先搜索算法，它在一个网的源端点和目的端点之间找到一条最短路径。在搜索时从网的源端点开始向邻居端点延伸，以此类推直到所有的目的端点都到达，或者没有找到路径终止。然而，迷宫搜索算法的最大缺点就是运行速度非常慢，因为在布线资源图中有很多节点要被遍历。

探路布线算法[2]是一般的布线算法，被用于大多数的FPGA中，通用的布局布线(VPR)中就是用该算法实现布线功能。探路算法是基于宽度优先的迷宫布线算法，使用的是考虑花费的启发式搜索算法。

探路算法所使用的拥塞解决算法是基于多次迭代算法的拥塞协商算法，拥塞协商算法首先把所有的网布到FPGA里面，而不考虑是否发生了拥塞。当布线完成以后，会对过多使用的布线资源进行一个惩罚，下次迭代时将以一个比较小的概率选择该布线资源。如果拥塞发生，那么撤销所有的布线，重新进行布线，然后再有拥塞发生，再次惩罚，最终经过若干次迭代之后，布线成功或者资源不够用。为了提高布线效率，对探路算法进行改进，探路算法的成本函数如下:

Cost表示的是从源端点到特定布线资源的花费。Cost_prev表示从源端点到当前布线资源的花费，C0表示布线资源的基本花费，初始化为1，但是当该资源已经被使用以后，它的值就变得非常大，通过快速增大C0的值，可以降低迭代的次数。而在探路算法中，基本值增大的比较慢，所以就会有很多的迭代次数。△D表示从当前的布线资源到目标端点的花费，如何有效地提高△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