Optimal layer assignment for escape routing of buses

Escape routing is a critical problem in PCB design. In IC-CAD'07, a layer assignment algorithm was proposed for escape routing of buses. The algorithm is optimal for single layer design in the sense that it determines if a set of buses can all be escaped on one layer. If they cannot, the algorithm is able to select a maximum subset of the buses that can be escaped on one layer. This, in turn, leads to a heuristic for the layer assignment problem with multiple layers, which is to repeatedly assign a maximum subset of the unassigned buses to a new layer. In this work, we present an algorithm that solves the multi-layer layer assignment problem optimally. Our algorithm guarantees to produce a layer assignment with minimum number of layers. We applied our algorithm on industrial data and obtained encouraging results. Categories and Subject Descriptors B.7.2 [Integrated Circuits]: Design Aids-Placement and Routing General Terms Algorithm, Theory