An efficient approach to multilayer layer assignment with an application to via minimization

In this paper we present an efficient heuristic algorithm for the post-layo ut layer assignment and via minimization problem of multilayer gridless int egrated circuit (IC), printed circuit board (PCB), and multichip module (MC M) layouts, We formulate the multilayer layer assignment problem hy introdu cing the notion of the extended conflict-continuation (ECC) graph, When the formulated ECC graph of a laver assignment problem is a tree, we show that the problem can be solved by an algorithm which is both linear time and op timal. When the formulated ECC graph is not a tree, we present an algorithm which constructs a sequence of maximal induced subtrees from the ECC graph , then applies our linear time optimal algorithm to each of the induced sub trees to refine the layer assignment. Our experiments show that, on average , the number of vertices of an induced subtree found by our algorithm is be tween 12% and 34% of the total number of vertices of an ECC graph, This ind icates that our algorithm is able to refine a large portion of the layout o ptimally on each refinement, thus, producing highly optimized layer assignm ent solutions. We applied this algorithm to the via minimization problem an d obtained very encouraging results. We achieved 13%-15% via reduction on t he routing layout generated by the V4R router [1], which is a router known to have low usage of vias, Our algorithm has been successfully applied to r outing examples of over 30 000 wire segments and over 40 000 vias. Finally. we outline how our la er assignment algorithm can also be used for delay a nd crosstalk minimization in high performance IC, PCB, and MCM designs.