引用本文: | 陈迅,张民选.延迟驱动的FPGA高扇出信号线快速布线算法[J].国防科技大学学报,2011,33(6):61-65.[点击复制] |
CHEN Xun,ZHANG Minxuan.A Fast Timing-driven Routing Algorithm for FPGA High Fan-out Net[J].Journal of National University of Defense Technology,2011,33(6):61-65[点击复制] |
|
|
|
本文已被:浏览 6773次 下载 5155次 |
延迟驱动的FPGA高扇出信号线快速布线算法 |
|
(1.信息工程大学 电子技术学院,河南 郑州 450004;2.国防科技大学 计算机学院,湖南 长沙 410073)
|
摘要: |
采用基本的延迟驱动Pathfinder布线器对FPGA高扇出信号进行布线,大部分时间会用于初始化寻路的优先级队列,而初始化工作主要是将已得到的布线树中的布线资源结点插入优先级队列。但是分析发现,并非所有被插入的资源结点对布线都是有帮助的。因此提出了一种基于树剪枝的优先级队列初始化算法,这种算法对已有的布线树中的资源点进行筛选后再插入优先级队列。实验结果显示该算法能够取得5.23倍的队列初始化时间加速,在不损失算法结果质量的情况下获得1.55倍的布线加速。 |
关键词: 现场可编程逻辑阵列 布线算法 高扇出信号 树剪枝 延迟驱动 |
DOI: |
投稿日期:2011-06-20 |
基金项目:国家“核高基”重大专项“超高性能CPU新型架构研究”资助项目(2011ZX01028-001-001) |
|
A Fast Timing-driven Routing Algorithm for FPGA High Fan-out Net |
CHEN Xun1,2, ZHANG Minxuan3 |
(1.Institute of Electronic Technology, Information Engineering Univ, Zhengzhou 450004, China;2.
2.College of Computer, National Univ. of Defense Technology, Changsha 410073, China;3.2.College of Computer, National Univ. of Defense Technology, Changsha 410073, China)
|
Abstract: |
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. |
Keywords: FPGA(Field Programmable Gate Array) routing algorithm high-fan-out net pruning tree timing-driven |
|
|