基于PathFinder和拆线-重布的FPGA时序布线算法  

An FPGA Timing Routing Algorithm Based on PathFinder and Rip-up and Retry Approach

作　　者：刘洋[1,2] 杨海钢[1] 喻伟[1,2] 崔秀海[1] 黄娟[1] 

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

出　　处：《计算机辅助设计与图形学学报》2014年第1期138-145,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61106033);国家科技重大专项(2013ZX03006004)

摘　　要：为了解决当前FPGA布线算法的绕线问题,进一步减少关键路径的延时,提出一种混合PathFinder和拆线-重布的FPGA时序布线算法.在PathFinder时序算法整体布线布通之后,拆掉一些影响关键路径延时的线网路径,再对这些拆掉的线网采用PathFinder算法进行增量布线;在重布的过程中,通过为关键连接和其他连接采用差别化的关键度来专门优化关键连接的路径,从而减少整个关键路径的延时.实验结果表明,与VPR时序驱动布线算法相比,该算法能平均减少12.97%的关键路径延时,而运行时间仅增加了4.87%.In order to improve timing performance of FPGA implementations, this paper presents an FPGA timing-driven routing algorithm that mixes PathFinder algorithm and the rip-up and retry approach. After execution of PathFinder algorithm, the proposed algorithm rips up the routed paths of nets influencing the critical path delay, and then incrementally reroutes these nets. During the rip-up and retry stage, the algorithm optimizes the path of critical connection and decreases critical path delay, by setting different criticalities for critical connection and non-critical connections. Experimental results demonstrated that the proposed method decreases 12.97%o of critical path delay, while, compared with the VPR, the run time only increases by 4.87o//oo on average.

关 键 词：FPGA 时序布线 柝线一萤布 增量布线 关键摩 

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