A powerful global router: based on Steiner min-max trees
- 7 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A study is made of the global routing of multiterminal nets. The authors propose a novel global router. Each step consists of finding a tree, called Steiner min-max tree, that is, a Steiner tree with the maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). An efficient algorithm is presented for obtaining a Steiner min-max tree, in a weighted graph. Experimental results on difficult examples, randomly generated data, master slice chips, and benchmark examples from the physical design workshop are very promising. (In all cases, previous results have been improved.).Keywords
This publication has 10 references indexed in Scilit:
- A new global router for row-based layoutPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- New global routing subsystem for CMOS gate arraysIEE Proceedings - Circuits, Devices and Systems, 1994
- Global wire routing in two-dimensional arraysAlgorithmica, 1987
- A Hierarchical Global Wiring Algorithm for Custom Chip DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- A Simple Yet Effective Technique for Global WiringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Global Wiring by Simulated AnnealingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- Hierarchical Wire RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- Routing Techniques for Gate ArrayIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957