Detailed-Routing Algorithms for Dense Pin Clusters in Integrated Circuits
Author:
- 18 February 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 28 (3) , 340-349
Abstract
As 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 an 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 multicommodity-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 interdependence and contention between different flow commodities is minimal. Using this model, we propose a Lagrangian-relaxation-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.Keywords
This publication has 16 references indexed in Scilit:
- A Length-Matching Routing Algorithm for High-Performance Printed Circuit BoardsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- Optimizing Yield in Global Routing2006 IEEE/ACM International Conference on Computer Aided Design, 2006
- Algorithms for simultaneous escape routing and Layer assignment of dense PCBsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- Placement and routing tools for the Triptych FPGAIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1995
- A faster strongly polynomial minimum cost flow algorithm1988
- An Applications Oriented Guide to Lagrangian RelaxationInterfaces, 1985
- Validation of subgradient optimizationMathematical Programming, 1974
- Wire routing by optimizing channel assignment within large apertures1971
- A solution to line-routing problems on the continuous plane1969
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961