2-terminal nets ‘via minimization’ through dynamic-programming for partitioning of terminals

In the routing in VLSI and printed circuit board (PCB) using the multilayered board, a routing technique is considered to reduce the number of vias produced in the routing. It is shown that the problem to determine the routing and layer assignment, to minimize the number of vias without considering the constraints of the line width and the line spacing, is NP-hard even if the net is restricted to be the two-terminal net. On the other hand, the following polynomial-time algorithm is proposed. Let the number of continuous intervals of terminals not containing the local net that can cover all terminals be delta (by local net is meant a net with both ends in the same interval). Then there exists a polynomial-time algorithm when delta is 2 and the number of layers k is a constant or when k is 2 and delta is a constant. This paper proposes a polynomial algorithm based on the dynamic programming which can handle both delta and k as parameters. Furthermore, a method also is proposed in which the partition into intervals is arbitrary and the local net can be contained. In addition, the total number l of the local nets can be handled as a parameter; l and delta are in a trade-off relation. A method is discussed which solves the problem with minimum complexity in terms of the time estimated by the proposed method.