An efficient approach to multi-layer layer assignment with application to via minimization

In this paper, we present an efficient heuristic algorithm for the layer assignment and via minimization problem for multi-layer gridless IC, PCB, and MCM layout. We introduce the notion of the extended conflict-continuation (ECC) graph to represent the multi-layer layer assignment problem. Our algorithm is based on a linear time optimal algorithm that solves a special case of the layer assignment problem when the ECC graph is a tree. For the general layer assignment problem where the ECC graph as not a tree, our algorithm constructs a sequence of induced subtrees in the ECC graph and applies our linear time optimal algorithm to each of the induced subtrees. We have applied this algorithm to the via minimization problem and get very encouraging results. We have achieved 13%-16% via reduction on the routing layout generated by V4R router[13], which is a router known to have low usage of vias. We successfully applied our algorithm to routing examples of over 30,000 wire segments and over 40,000 vias.