Global routing with crosstalk constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Global routing with crosstalk constraints

Full text

Pdf (218 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 35th annual Design Automation Conference table of contents

San Francisco, California, United States

Pages: 374 - 377

Year of Publication: 1998

ISBN:0-89791-964-5

Authors

Hai Zhou	Department of Computer Sciences, University of Texas, Austin, TX
D. F. Wong	Department of Computer Sciences, University of Texas, Austin, TX

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 26, Citation Count: 35

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/277044.277147 What is a DOI?

ABSTRACT

Due to the scaling down of device geometry and increasing frequency in deep sub-micron designs, crosstalk between interconnection wires has become an important issue in VLSI layout design. In this paper, we consider crosstalk avoidance during global routing. W e present a global routing algorithm based on a new Steiner tree formulation and the Lagrangian relaxation technique. W e also give theoretical results on the complexity of the problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	2	H.B. Bakoglu, Circuits, interconnections and packaging for VLSI. Addison- Wesley, 1990.
	3	Kamal Chaudhary , Akira Onozawa , Ernest S. Kuh, A spacing algorithm for performance enhancement and cross-talk reduction, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.697-702, November 07-11, 1993, Santa Clara, California, United States
	4	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	5	Tong Gao , C. L. Liu, Minimum crosstalk channel routing, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.692-696, November 07-11, 1993, Santa Clara, California, United States
	6	Tong Gao , C. L. Liu, Minimum crosstalk switchbox routing, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.610-615, November 06-10, 1994, San Jose, California, United States
	7	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	8	F.K. Hwang, D.S. Richards, and P. Winter, The Steiner Tree Problem. North-Holland, 1992.
	9	Desmond A. Kirkpatrick , Alberto L. Sangiovanni-Vincentelli, Techniques for crosstalk avoidance in the physical design of high-performance digital systems, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.616-619, November 06-10, 1994, San Jose, California, United States
	10	T. Sakurai and K. Tamaru, Simple formulas for two and three dimensional capacitance. IEEE Trans. Electron Devices, 1993.
	11	S. Thakur, K.-Y. Chao and D.F. Wong, An Optimal Layer Assignment Algorithm for Minimizing Crosstalk for Three Layer VHV Channel Routing. ISCAS, 1995.
	12	D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States
	13	Tianxiong Xue , Ernest S. Kuh , Dongsheng Wang, Post global routing crosstalk risk estimation and reduction, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.302-309, November 10-14, 1996, San Jose, California, United States
	14	Hai Zhou , D. F. Wong, An optimal algorithm for river routing with crosstalk constraints, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.310-315, November 10-14, 1996, San Jose, California, United States
	15	H. Zhou and D.F. Wong, Crosstalk Constrained Maze Routing Based on Lagrangian Relaxation. ICCD, 1997.

CITED BY 35

	Phiroze N. Parakh , Richard B. Brown, Crosstalk constrained global route embedding, Proceedings of the 1999 international symposium on Physical design, p.201-206, April 12-14, 1999, Monterey, California, United States
	Sung-Woo Hur , Ashok Jagannathan , John Lillis, Timing driven maze routing, Proceedings of the 1999 international symposium on Physical design, p.208-213, April 12-14, 1999, Monterey, California, United States
	Ki-Wook Kim , Unni Narayanan , Sung-Mo Kang, Domino logic synthesis minimizing crosstalk, Proceedings of the 37th conference on Design automation, p.280-285, June 05-09, 2000, Los Angeles, California, United States
	Chieh Changfan , Yu-Chin Hsu , Fur-Shing Tsai, Post-routing timing optimization with routing characterization, Proceedings of the 1999 international symposium on Physical design, p.30-35, April 12-14, 1999, Monterey, California, United States
	Ke Zhong , Shantanu Dutt, Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion control, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Rony Kay , Rob A. Rutenbar, Wire packing: a strong formulation of crosstalk-aware chip-level track/layer assignment with an efficient integer programming solution, Proceedings of the 2000 international symposium on Physical design, p.61-68, May 2000, San Diego, California, United States
	Paul B. Morton , Wayne Dai, An efficient sequential quadratic programming formulation of optimal wire spacing for cross-talk noise avoidance routing, Proceedings of the 1999 international symposium on Physical design, p.22-28, April 12-14, 1999, Monterey, California, United States
	Joon-Seo Yim , Chong-Min Kyung, Reducing cross-coupling among interconnect wires in deep-submicron datapath design, Proceedings of the 36th ACM/IEEE conference on Design automation, p.485-490, June 21-25, 1999, New Orleans, Louisiana, United States
	Li Chen , Xiaoliang Bai , Sujit Dey, Testing for interconnect crosstalk defects using on-chip embedded processor cores, Proceedings of the 38th conference on Design automation, p.317-320, June 2001, Las Vegas, Nevada, United States
	Marcello Lajolo, Bus guardians: an effective solution for online detection and correction of faults affecting system-on-chip buses, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.974-982, 12/1/2001
	Xiaoliang Bai , Sujit Dey , Janusz Rajski, Self-test methodology for at-speed test of crosstalk in chip interconnects, Proceedings of the 37th conference on Design automation, p.619-624, June 05-09, 2000, Los Angeles, California, United States
	Michael Cuviello , Sujit Dey , Xiaoliang Bai , Yi Zhao, Fault modeling and simulation for crosstalk in system-on-chip interconnects, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.297-303, November 07-11, 1999, San Jose, California, United States
	Murat R Becer , David Blaauw , Ibrahim N. Hajj , Rajendran Panda, Early probabilistic noise estimation for capacitively coupled interconnects, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA
	Krishna Sekar , Sujit Dey, LI-BIST: A Low-Cost Self-Test Scheme for SoC Logic Cores and Interconnects, Journal of Electronic Testing: Theory and Applications, v.19 n.2, p.113-123, April 2003
	Ki-Wook Kim , Seong-Ook Jung , Unni Narayanan , C. L. Liu , Sung-Mo Kang, Noise-aware interconnect power optimization in domino logic synthesis, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.79-89, February 2003
	David Blaauw , Supamas Sirichotiyakul , Chanhee Oh, Driver modeling and alignment for worst-case delay noise, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.2, p.157-166, April 2003
	False-noise analysis using logic implications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.474-498, July 2002
	Hua Xiang , Kai-Yuan Chao , Martin D. F. Wong, An ECO algorithm for eliminating crosstalk violations, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Prashant Saxena , Satyanarayan Gupta, Shield count minimization in congested regions, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Masanori Hashimoto , Masao Takahashi , Hidetoshi Onodera, Crosstalk noise optimization by post-layout transistor sizing, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Murat Becer , Ravi Vaidyanathan , Chanhee Oh , Rajendran Panda, Signal integrity management in an SoC physical design flow, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Lauren Hui Chen , Malgorzata Marek-Sadowska, Closed-Form Crosstalk Noise Delay Metrics, Analog Integrated Circuits and Signal Processing, v.35 n.2-3, p.143-156, May-June 2003
	Li Chen , Xiaoliang Bai , Sujit Dey, Testing for Interconnect Crosstalk Defects Using On-Chip Embedded Processor Cores, Journal of Electronic Testing: Theory and Applications, v.18 n.4-5, p.529-538, August-October 2002
	Edwin Naroska , Shanq-Jang Ruan , Uwe Schwiegelshohn, Simultaneously optimizing crosstalk and power for instruction bus coupling capacitance using wire pairing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.4, p.421-425, April 2006
	Hai-Long Yao , Yi-Ci Cai , Qiang Zhou , Xian-Long Hong, Crosstalk-aware routing resource assignment, Journal of Computer Science and Technology, v.20 n.2, p.231-236, March 2005
	Chin-Chih Chang , Jason Cong, Pseudo pin assignment with crosstalk noise control, Proceedings of the 2000 international symposium on Physical design, p.41-47, May 2000, San Diego, California, United States
	Hua Xiang , Liang Deng , Ruchir Puri , Kai-Yuan Chao , Martin D.F. Wong, Dummy fill density analysis with coupling constraints, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Tianpei Zhang , Sachin S. Sapatnekar, Simultaneous shield and buffer insertion for crosstalk noise reduction in global routing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.6, p.624-636, June 2007
	William Swartz, Issues in global routing, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Tsung-Yi Ho , Yao-Wen Chang , Sao-Jie Chen , D. T. Lee, A Fast Crosstalk- and Performance-Driven Multilevel Routing System, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.382, November 09-13, 2003
	Tiehan Lv , Jorg Henkel , Haris Lekatsas , Wayne Wolf, Enhancing Signal Integrity through a Low-Overhead Encoding Scheme on Address Buses, Proceedings of the conference on Design, Automation and Test in Europe, p.10542, March 03-07, 2003
	Hanif Fatemi , Behnam Amelifar , Massoud Pedram, Power optimal MTCMOS repeater insertion for global buses, Proceedings of the 2007 international symposium on Low power electronics and design, August 27-29, 2007, Portland, OR, USA
	Jinjun Xiong , Lei He, Full-Chip Multilevel Routing for Power and Signal Integrity, Proceedings of the conference on Design, automation and test in Europe, p.21116, February 16-20, 2004
	Ashoka Sathanur , Antonio Pullini , Luca Benini , Alberto Macii , Enrico Macii , Massimo Poncino, Timing-driven row-based power gating, Proceedings of the 2007 international symposium on Low power electronics and design, August 27-29, 2007, Portland, OR, USA
	Chin-Hsiung Hsu , Huang-Yu Chen , Yao-Wen Chang, Multi-layer global routing considering via and wire capacities, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California