Partitioning routing area into zones with distinct pins

Topological routing has gained importance in state-of-the-art layout synthesis. This paper poses the problem of partitioning the routing area of a given placement into a minimum set of zones such that in each zone, no two pins belong to the same net. Thus, topological routing can be completed among the zones whereas within a zone the only wires are from a pin to the boundary of the zone. Hence, such partitioning may accelerate routing by reducing the problem size. The related problem of identifying a zone with maximum number of distinct pins is also considered here. Both problems are observed to be NP-hard. A genetic algorithm for the first one and a greedy heuristic for the second problem are proposed. Experimental results are observed to be near optimal in most of the cases