IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2009 · 44 citations · 28 references
EngineeringComputer EngineeringComputer ScienceCircuit TheoryOptimizationSystem-on-chip DesignCombinatorial OptimizationLayout OptimizationNetwork-on-chip DesignRoutingRouting AlgorithmsVery-large-scale Integration LayoutComplexityDetailed RoutingEscape RoutingIterative Design ProcessLagrangian RelaxationMulticommodity FlowPolynomial-time AlgorithmsRelaxation-based Heuristics
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.
28
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
An Algorithm for Path Connections and Its Applications
C. Y. Lee · IEEE Transactions on Electronic Computers · 1961 · 1.6K citations
Validation of subgradient optimization
Michael Held, Philip Wolfe, Harlan Crowder · Mathematical Programming · 1974 · 1.4K citations