基于拓扑分析的多层通道布线算法

A Multi-Layer Channel Routing Based on Topological Analysis

本文提出了一种基于拓扑分析的多层通道布线算法。算法把整个布线过程分成拓扑分层和物理布线两个部分。拓扑分层利用线段交叠图及模拟退火算法解决线段分层及通孔最少化问题,物理布线过程引入虚拟走线道解决交叉问题,再利用轮廓线跟踪的方法来决定最终确定各线段的布线位置。算法还解决了多层布线分层的管脚约束问题和相邻约束问题。实验结果表明,这是一种有效的方法。

An innovative approach to solve the channel routing problem is proposed. The whole problem is broken into two topics: topological layer definition and physical wire layout. For the first topic, Segment-Crossing Graphics and Simulated Annealing Approach are used to solve the problem of via minimization and layer assignment. For the second topic, virtual routing is introduced in the procedure of wiring to solve the problem of crossing, and then the contour following approach is used to determine positions of all wire-segments. Using the proposed algorithm, the problem of layer assignment in multi-layer wiring under the constraint of pin-out and the constraint of neighborhood can be solved. This algorithm has been verified to be effective through experiment.