loading...
Partitioning Routing Area into Zones with Distinct Pins
Bangalore, India January 03-January 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICVD.2001.902683The 14th International Conference on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
K. Sinha, Kalyani Engineering College
S. Sur-Kolay, Indian Statistical Institute
B.B. Bhattacharya, Indian Statistical Institute
P.S. Dasgupta, Indian Institute of Management
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
Usage of this product signifies your acceptance of the Terms of Use.