Minimum crosstalk channel routing
Authors:
- 1 May 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 15 (5) , 465-474
Abstract
As technology advances, interconnection wires are placed in closer proximity and circuits operate at higher frequencies. Consequently, reduction of crosstalk between interconnection wires becomes an important consideration in VLSI design. In this paper, we study the gridded channel routing problem with the objective of satisfying crosstalk constraints for the nets. We proposed a new approach to the problem which utilizes existing channel routing algorithms and improves upon the routing results by permuting the routing tracks. The permutation problem is proven to be NP-complete. A novel mixed ILP formulation and effective procedures for reducing the number of variables and constraints in the mixed ILP formulation are then presented. The new algorithm is tested on three large benchmark circuits as well as many randomly generated circuits. The experimental results are very promising.Keywords
This publication has 6 references indexed in Scilit:
- Wiring And Crosstalk Avoidance In Multi-chip Module Design1992
- A new approach to three- or four-layer channel routingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- Compacted channel routing with via placement restrictionsIntegration, 1986
- Glitter: A Gridless Variable-Width Channel RouterIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1986
- Hierarchical channel routerIntegration, 1983
- Efficient Algorithms for Channel RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982