延迟驱动的FPGA高扇出信号线快速布线算法  

A Fast Timing-driven Routing Algorithm for FPGA High Fan-out Net

作　　者：陈迅[1,2] 张民选[2] 

机构地区：[1]信息工程大学电子技术学院,河南郑州450004 [2]国防科技大学计算机学院,湖南长沙410073

出　　处：《国防科技大学学报》2011年第6期61-65,共5页Journal of National University of Defense Technology

基　　金：国家"核高基"重大专项"超高性能CPU新型架构研究"资助项目(2011ZX01028-001-001)

摘　　要：采用基本的延迟驱动Pathfinder布线器对FPGA高扇出信号进行布线,大部分时间会用于初始化寻路的优先级队列,而初始化工作主要是将已得到的布线树中的布线资源结点插入优先级队列。但是分析发现,并非所有被插入的资源结点对布线都是有帮助的。因此提出了一种基于树剪枝的优先级队列初始化算法,这种算法对已有的布线树中的资源点进行筛选后再插入优先级队列。实验结果显示该算法能够取得5.23倍的队列初始化时间加速,在不损失算法结果质量的情况下获得1.55倍的布线加速。For base timing-driven PathFinder router,it is found that the High-Fan-Out-Net routing spends around half of the time to insert the previous routed routing tree into routing resource node priority queue,but not all the nodes inserted are useful.In light of this finding,we proposed a pruning tree based priority queue initialization algorithm by just inserting the routing resource node which shares the same direction with next routing sink.For the High-Fan-out Net benchmark,results show our algorithm can shorten the initialization time by 5.23 times,and achieve 1.55 times speedup with almost the same quality of result.

关 键 词：现场可编程逻辑阵列 布线算法 高扇出信号 树剪枝 延迟驱动 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]