An exact algorithm for practical routing problems

In this paper, we propose an exact algorithm for practical routing problems in automated cell generation. We assume grid-based, Manhattan two layer model. Experimental results show that the proposed method can generate better solutions than commercial tools with respect to the wire length and the number of vias. Our algorithm takes account of the characteristics of VLSI layouts, such as silicides and VDD/GND lines. This enables us to generate all possible routing patterns for real cell layouts. Our method generates all possible routing patterns under some restrictions, so we can pick up optimal patterns by various cost metrics.