VLSI中双层布线导孔数的优化算法

Via Optinization Algorithm of 2-Layer Wiring in VLSI

在超大规模集成电路的设计中,通常需要尽可能地减少布线时产生的导孔,因为导孔数是影响集成电路成品率、可靠性及各种电性能的重要因素.本文的工作是解决VLSI双层金属布线的导孔数优化问题.实际的布线根据其拓扑特性和电连通性等效为带权的图.将这种方法推广到三联和四联导孔的情形,并引入了添加冗余导孔的方法以进一步减少导孔的数目.最后给出了对变权图求最大偶子图的算法,以便对三联及四联情形的导孔进行优化.算法实现后试算的实例表明一般能减少30％-50％的导孔.

This paper presents a method of Iooking for the solution of 2-layer-metal-wiring viaoptimization problem.Accrding to topological chracteristics and electrical connectivity,thewiring is transfered to its equivalent graph with edges weighted in the graph theory.Themethod is then extended to the case of 3-and 4-linkage via,and redundant vias are intro-duced to reduce the existing ones still further Finally an algorithm of obtaining the maxi-mum bipartite graph of variable-edge-weight is presented to optimize the 3-/4-linkage vias.The results of the algorithm show that 30%-50% vias can be eliminated.