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-layout layer assignment and via minimization problem of multilayer gridless integrated circuit (IC), printed circuit board (PCB), and multichip module (MCM) layouts. We formulate the multilayer layer assignment problem by introducing the notion of the extended conflict-continuation (ECC) graph. When the formulated ECC graph of a layer assignment problem is a tree, we show that the problem can be solved by an algorithm which is both linear time and optimal. 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 subtrees to refine the layer assignment. Our experiments show that, on average, the number of vertices of an induced subtree found by our algorithm is between 12% and 34% of the total number of vertices of an ECC graph. This indicates that our algorithm is able to refine a large portion of the, layout optimally on each refinement, thus, producing highly optimized layer assignment solutions. We applied this algorithm to the via minimization problem and obtained very encouraging results, We achieved 13%-15% via reduction on the routing layout generated by the V4R router, which is a router known to have low usage of vias. Our algorithm has been successfully applied to routing examples of over 30 000 wire segments and over 40 000 vias. Finally, we outline how our layer assignment algorithm can also be used for delay and crosstalk minimization in high-performance IC, PCB, and MCM designs