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

A Multi-Layer Channel Routing Based on Topological Analysis

作　　者：卢永江[1] 

机构地区：[1]浙江大学电气工程学院,浙江杭州310027

出　　处：《电路与系统学报》2003年第6期6-9,共4页Journal of Circuits and Systems

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

关 键 词：拓扑分析 多层通道布线 线段交叠图 通孔最小化 模拟退火算法 轮廓线跟踪 

分 类 号：TN405[电子电信—微电子学与固体电子学]