Via Minimization in VLSI Chip Design - Application of a Planar Max-Cut Algorithm

The design of very large scale integrated (VLSI) chips is an exciting area of applied discrete mathematics.Due to the intractability of the majority of the problems, and also due to the huge instance sizes, the design process is decomposed into various sub-problems. In this paper, for a given detailed routing solution, we revisit the assignment of layers to net segments. For connected metalized nets, a layer change is accomplished by a vertical interconnection area (via). We seek to minimize the use of these vias as vias not only reduce the electrical reliability and performance of the chip, but also decrease the manufacturing yield substantially. In the general case, the via minimization problem is NP-hard. However, it is known that the two layer via minimization problem can be solved as a maximum cut problem on a planar graph which is a polynomial task.The focus of this paper is to use this approach for modern real-world chips. From the roughly two dozen wiring layers present, we take two adjacent ones for the via minimization. As a core-routine, we use a fast maximum cut algorithm on planar graphs. For being able to use the solutions in practice, we integrate practically relevant design rule constraints at the expense of potentially using further vias. Thus, our solution satisfies the additional constraints present in actual current designs. The computational results show that our implementation is fast on real-world instances as it usually computes a solution within a few minutes CPU time only. Moreover, often a considerable amount of vias can be saved