TY - JOUR

T1 - Efficient Algorithms for Layer Assignment Problem

AU - Chang, K. C.

AU - Du, David Hung Chang

PY - 1987/1

Y1 - 1987/1

N2 - The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets. The objective of the layer assignment problem in general is to minimize the number of vias required. Thus, it is also referred to as the via minimization problem. In a via minimization problem, if the topology of the given layout is fixed, the problem is referred to as a constrained via minimization (CVM) problem. On the other hand, if both the topology of the layout and the layer assignment are to be decided, it is referred to as an unconstrained via minimization (UVM) problem. In this paper, both the CVM and UVM problems are studied. For the CVM problems, efficient algorithms which can be easily modified to take extra constraints into consideration are proposed. Experimental results show that the proposed algorithms for the CVM problem are time efficient compared with existing algorithms and generate better (near-optimal) results. For the UVM problems, a new heuristic approach is presented which generates better results but takes longer computing time. In the CVM problem, some vias are “essential” to the given layout. That is, they have to be selected and cannot be replaced by other possible vias. An efficient algorithm for identifying essential vias is also presented and discussed in this paper.

AB - The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets. The objective of the layer assignment problem in general is to minimize the number of vias required. Thus, it is also referred to as the via minimization problem. In a via minimization problem, if the topology of the given layout is fixed, the problem is referred to as a constrained via minimization (CVM) problem. On the other hand, if both the topology of the layout and the layer assignment are to be decided, it is referred to as an unconstrained via minimization (UVM) problem. In this paper, both the CVM and UVM problems are studied. For the CVM problems, efficient algorithms which can be easily modified to take extra constraints into consideration are proposed. Experimental results show that the proposed algorithms for the CVM problem are time efficient compared with existing algorithms and generate better (near-optimal) results. For the UVM problems, a new heuristic approach is presented which generates better results but takes longer computing time. In the CVM problem, some vias are “essential” to the given layout. That is, they have to be selected and cannot be replaced by other possible vias. An efficient algorithm for identifying essential vias is also presented and discussed in this paper.

UR - http://www.scopus.com/inward/record.url?scp=0023089597&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023089597&partnerID=8YFLogxK

U2 - 10.1109/TCAD.1987.1270247

DO - 10.1109/TCAD.1987.1270247

M3 - Article

AN - SCOPUS:0023089597

SN - 0278-0070

VL - 6

SP - 67

EP - 78

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 1

ER -