Pattern routing: use and theory for increasing predictability and avoiding coupling
Authors:
- 7 August 2002
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 21 (7) , 777-790
Abstract
Deep submicron effects, along with increasing interconnect densities, have increased the complexity of the routing problem. Whereas previously we could focus on minimizing wirelength, we must now consider a variety of objectives during routing. For example, an increased amount of timing restrictions means that we must minimize interconnect delay. But, interconnect delay is no longer simply related to wirelength. Coupling capacitance has become a dominant component of delay due to the shrinking of device sizes. Regardless, the most important objective is producing a routable circuit. Unfortunately, this often conflicts with minimizing interconnect delay as minimum delay routes create congested areas, for which an exact routing cannot be realized without violating design rules. In this work, we use the concept of pattern routing to develop algorithms that guide the router to a solution that minimizes interconnect delay - by considering both coupling and wirelength-without damaging the routability of the circuit. The paper is divided into two parts. The first part demonstrates that pattern routing can be used without affecting the routability of the circuit. We propose two schemes to choose a set of nets to pattern route. Using these schemes, we show that the routability is not hindered. The second part builds on the previous part by presenting a framework for coupling reduction using pattern routing. We develop theory and algorithms relating pattern routing and coupling. Additionally, we give suggestions on how to extend our theory and use our algorithms for both global and detailed routing.Keywords
This publication has 35 references indexed in Scilit:
- A postprocessing algorithm for crosstalk-driven wire perturbationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000
- A global wiring paradigm for deep submicron designIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000
- Performance optimization of VLSI interconnect layoutIntegration, 1996
- COP: a Crosstalk OPtimizer for gridded channel routingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996
- Minimum crosstalk switchbox routingIntegration, 1995
- A Simple Yet Effective Technique for Global WiringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Single bend wiringJournal of Algorithms, 1986
- Rectilinear line segment intersection, layered segment trees, and dynamizationJournal of Algorithms, 1982
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- Reducibility among Combinatorial Problems1972