一个基于层次式PB角钩链结构的区域布线器(英文)

A Gridless Router Based on Hierarchical PB Corner Stitching Structure

提出一个新的基于层次式 PB角钩链结构的多层无网格布线器 .该布线器基于 PB层次式角勾链数据结构和网块扩展算法 ,使用朝向目标的加速策略提高算法的运行速度 ,并使用改进的二叉区间树管理算法的中间数据 .还提出了基于拥挤度的无网格拆线重布算法 .通过显式记录每个线网段周边的拥挤状况 ,并将其结合到网块扩展的费用当中 ,使拆除线网的选择和待布线网的路径搜索统一起来 .实验结果表明 ,该布线器能有效地提高布通率 。

A multi layer gridless area router is reported.Based on corner stitching,this router adopts tile expansion to explore path for each net.A heuristic method that penalizes nodes deviating from the destination is devised to accelerate the algorithm.Besides,an enhanced interval tree is used to manage the intermediate data structure.In order to improve the completion rate of routing,a new gridless rip up and rerouting algorithm is proposed.The experimental results indicate that the completion rate is improved after the rip up and reroute process and the speed of this algorithm is satisfactory.