Efficient Algorithms for Layer Assignment Problem

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