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.
Citation:
K. Sinha, S. Sur-Kolay, B.B. Bhattacharya, P.S. Dasgupta, "Partitioning Routing Area into Zones with Distinct Pins," vlsid, pp.345, The 14th International Conference on VLSI Design (VLSID '01), 2001