一种减少重复搜索的FPGA快速布线算法  

A Fast FPGA Routing Algorithm Based on Repeated Search Avoidance

作　　者：刘洋[1,2] 杨海钢[1] 黄志洪[1,2] 刘峰[1] 罗杨[1] 

机构地区：[1]中国科学院电子学研究所可编程芯片与系统研究室,北京100190 [2]中国科学院大学,北京100049

出　　处：《计算机辅助设计与图形学学报》2014年第6期1015-1024,共10页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2012AA012301);中国科学院;国家外国专家局创新团队国际合作伙伴计划

摘　　要：为了提高FPGA布线的运行速度,提出一种减少重复搜索的快速布线算法,该算法分为布通驱动布线算法和时序驱动布线算法.在布通驱动布线算法中,通过把线网的布线路径转换成连接的布线路径来判断每条连接的路径中是否存在拥塞节点,如果存在,保留其布线路径,否则重新进行搜索;时序驱动布线算法采用临界度判定机制来平衡运行速度和时序性能之间的比重.实验结果表明,与公认的VPR布线算法相比,布通驱动布线算法和时序驱动布线算法的运行时间分别平均减少了95.19%和28.98%,且时序驱动布线算法的关键路径延时减少了4.80%.This paper presents a fast FPGA routing algorithm that reduces repeated search in order to improve the speed of FPGA routing.The algorithm divides into routability-driven algorithm and timing-driven algorithm.By transforming the routed path of each net into routed paths of connections,routability-driven algorithm judges whether the path of every connection contains congested nodes or not.If the path of one connection contains congested nodes,it will be ripped-up and rerouted; otherwise,the path will be reserved.Criticality determinant strategy is employed to trade-off running speed and timing performance in timing-driven algorithm.Experimental results demonstrated that,the proposed routability-driven algorithm and timing-driven algorithm decrease 95.19％ and 28.98％ of runtime respectively,and critical path delay of timing-driven algorithm can be reduced by 4.80％ on average,compared with VPR.

关 键 词：可编程门阵列 布线 重复搜索 拥塞节点 临界度判定 

分 类 号：TP302.1[自动化与计算机技术—计算机系统结构]