Paper Info
Title
Escape routing for dense pin clusters in integrated circuits
Abstract
As the design complexities and circuit densities are increasing, the detailed routing (DR) problem is becoming a more and more challenging problem. Due to the high complexity of DR algorithms, it is very important to start the routing process with clean solutions, rather than starting with suboptimal routes and trying to fix them in iterative process. In this paper, we propose an escape routing algorithm that can optimize routing of a set of nets around their terminals. For this, we first propose a polynomial-time algorithm that guarantees to find the optimal escape routing solution for a set of nets when the track structures are uniform. Then, we use this algorithm as a baseline, and study the general problem with arbitrary track structures. For this, we propose a novel multi-commodity flow (MCF) model that has a one-to-one correspondence with the escape routing problem. This MCF model is novel in the sense that the inter-dependency and contention between different flow commodities is minimal. Using this model, we propose a Lagrangian-relaxation (LR) based algorithm to solve the escape problem. Our experiments demonstrate that this algorithm improves the overall routability significantly by reducing the number of nets that require rip-up and reroute.
Year
DOI
Venue
2007
10.1145/1278480.1278494
design automation conference
Keywords
Field
DocType
detailed routing,escape routing,multi-commodity flow
Multipath routing,Equal-cost multi-path routing,Mathematical optimization,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Destination-Sequenced Distance Vector routing,Routing table,Distance-vector routing protocol
Conference
ISSN
Citations 
PageRank 
0738-100X
0
0.34
References 
Authors
13
1
Name
Order
Citations
PageRank
Muhammet Mustafa Ozdal131323.18