一种高效且可扩展的障碍物规避型VLSI全局路由算法

《ACM Transactions on Design Automation of Electronic Systems》：A High Efficient and Scalable Obstacle-Avoiding VLSI Global Routing Flow

障碍物感知全局路由优化方法研究。针对VLSI设计中障碍物引发的布线复杂度问题，提出基于规则障碍规避斯泰纳树（OARSMT）的预处理算法，结合稀疏迷宫路由技术实现障碍感知全局布线。相较于传统方法，在保证布线长度最优的同时，有效消除障碍物违规，降低过孔数与运行时开销。

　　

摘要

路由是VLSI设计流程中的关键步骤。随着制造技术的进步，设计规则中出现了更多的约束条件，尤其是在路由过程中遇到障碍物时，这导致了路由复杂性的增加。不幸的是，许多全局路由器由于缺乏可扩展的避障树生成方法以及处理具有复杂障碍物和网络的现代设计的能力，难以生成高效且无障碍的路由方案。在这项工作中，我们提出了一种针对具有障碍物的VLSI设计的高效全局路由流程。该流程在树生成阶段采用了基于规则的避障直线斯坦纳最小树（OARSMT）算法。该算法既具有可扩展性，又运行速度快，能够在早期全局范围内生成避开障碍物的树拓扑结构。在后续阶段，我们提出了基于OARSMT的避障稀疏迷宫路由方法，以进一步减少障碍物违规情况并降低溢出成本。与之前在具有障碍物的基准测试中使用的先进方法相比，我们的方法成功消除了障碍物违规问题，并减少了线长和溢出成本，同时仅牺牲了少量的过孔数量和运行时间开销。