一个可处理多种约束的多层布线通孔最少化算法

Constrained Via Minimization with Practical Considerations for Different-Styled Multi-Layer Routing

本文分析了常用的VLSI多层布线图模型线段 -相交图SCG的局限性 ,提出了对SCG模型的修正 ,并基于该模型用模拟退火算法来解决通孔最少化问题 ,算法可以处理严格和非严格分层的布线 ,并考虑了许多物理约束的处理方法 .实验证明算法可以较大程度地减少通孔 .

The weakness of the commonly-used Segment-Crossing Graph (SCG) model for VLSI multi-layer routing is first discussed, then a Modified Segment-Crossing Graph model is presented, and finally a modified simulated annealing approach for constrained via minimization problem on the basis of this model is given. In the algorithm, many physical constraints are taken into consideration, and both restricted and non-restricted layer model routing can be treated. The experimental results prove the number of vias can be reduced largely.