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

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

采用基本的延迟驱动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.