New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing

Full text

Pdf (347 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 33rd annual Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 395 - 400

Year of Publication: 1996

ISBN:0-89791-779-0

Authors

John Lillis	CSE Dept., UCSD, La Jolla, CA
Chung-Kuan Cheng	CSE Dept., UCSD, La Jolla, CA
Ting-Ting Y. Lin	ECE Dept., UCSD, La Jolla, CA
Ching-Yen Ho	LSI Logic Corp., Milpitas, CA

Sponsors

IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 17, Citation Count: 40

Additional Information:

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/240518.240594 What is a DOI?

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	Kenneth D. Boese , Andrew B. Kahng , Gabriel Robins, High-performance routing trees with identified critical sinks, Proceedings of the 30th international conference on Design automation, p.182-187, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164662]
	2	K. D. Boese, A. B. Kahng, B. A. McCoy, G. Robins, "Fidelity and Near-Optimality of Elmore-Based Routing Constructions," Proc. Proc. IEEE Intl. Co@ Computer-Aided Design, 1993.
	3	J.J. Cong, K.S. Leung, "Optimal Wiresizing Under Elmore Delay Model," IEEE Trans. on CAD, v. 14 no. 3 (1995) pp. 321-336.
	4	Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
	5	W.C. Elmore, "The Transient Response of Damped Linear Network with particular Regard to Wideband Amplifiers," J. Applied Physics 19 (1948), pp 55-63.
	6	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
	7	M. Hanan, "On Steiner's Problem With Rectilinear Distance," SIAM J. Applied Math., 14 (1966), pp. 255-265.
	8	T. D. Hodes, B. A. McCoy, G. Robins, "Dynamically- Wiresized Elmore-Based Routing Constructions," Proc. IEEE Intl. Symp. Circuits and Systems, 1994.
	9	F. K. Hwang, D. S. Richards, P. Winter, "The Steiner Tree Problem," Elsevier Science Publishers, (1992), pp. 213-214.
	10	F.K. Hwang, "On Steiner Minimal Trees with Rectilinear Distance," SIAM J. Applied Math. 30 (1976), pp. 104-114.
	11	M. A. B. Jackson, E. S. Kuh, M. Marek-Sadowska, "Timing- Driven Routing for Building Block Layout," Proc. IEEE Intl. Symp. Circuits and Systems, 1987, pp. 518-519.
	12	A. B. Kahng, G. Robins, "A New Class of Iterative Steiner Tree Heuristics With Good Performance," IEEE Trans. Computer-Aided Design, 11 (1992), pp. 893-902.
	13	John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
	14	J. Lillis, C. K. Cheng, T. T. Lin, C.-Y. Ho, "New Techniques for Performance Driven Routing with Explicit Area/Delay Tradeoff and Simultaneous Wire Sizing," Technical Report ~CS96-469, CSE Dept., UCSD.
	15	Sachin S. Sapatnekar, RC interconnect optimization under the Elmore delay model, Proceedings of the 31st annual conference on Design automation, p.387-391, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196430]
	16	Ashok Vittal , Malgorzata Marek-Sadowska, Minimal delay interconnect design using alphabetic trees, Proceedings of the 31st annual conference on Design automation, p.392-396, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196432]
	17	L.P.P.P van Ginneken, "Buffer Placement in Distributed RC- tree Networks for Minimal Elmore Delay," Proc. International Symposium on Circuits and Systems, 1990, pp 865- 868.

CITED BY 40

	Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
	Jason Cong , Lei He, Optimal wiresizing for interconnects with multiple sources, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.4, p.478-511, Oct. 1996
	John Lillis , Chung-Kuan Cheng, Timing optimization for multi-source nets: characterization and optimal repeater insertion, Proceedings of the 34th annual conference on Design automation, p.214-219, June 09-13, 1997, Anaheim, California, United States
	Jason Cong , Patrick H. Madden, Performance driven global routing for standard cell design, Proceedings of the 1997 international symposium on Physical design, p.73-80, April 14-16, 1997, Napa Valley, California, United States
	John Lillis , Premal Buch, Table-lookup methods for improved performance-driven routing, Proceedings of the 35th annual conference on Design automation, p.368-373, June 15-19, 1998, San Francisco, California, United States
	Bharat Krishna , C. Y. Roger Chen , Naresh K. Sehgal, A novel technique for sea of gates global routing, Proceedings of the 10th Great Lakes symposium on VLSI, p.71-74, March 02-04, 2000, Chicago, Illinois, United States
	Jason Cong , Cheng-Kok Koh, Interconnect layout optimization under higher-order RLC model, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.713-720, November 09-13, 1997, San Jose, California, United States
	Takahiro Deguchi , Tetsushi Koide , Shin'ichi Wakabayashi, Timing-driven hierarchical global routing with wire-sizing and buffer-insertion for VLSI with multi-routing-layer, Proceedings of the 2000 conference on Asia South Pacific design automation, p.99-104, January 2000, Yokohama, Japan
	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
	Amir H. Salek , Jinan Lou , Massoud Pedram, A simultaneous routing tree construction and fanout optimization algorithm, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.625-630, November 08-12, 1998, San Jose, California, United States
	Jiang Hu , Sachin S. Sapatnekar, FAR-DS: full-plane AWE routing with driver sizing, Proceedings of the 36th ACM/IEEE conference on Design automation, p.84-89, June 21-25, 1999, New Orleans, Louisiana, United States
	Amir H. Salek , Jinan Lou , Massoud Pedram, MERLIN: semi-order-independent hierarchical buffered routing tree generation using local neighborhood search, Proceedings of the 36th ACM/IEEE conference on Design automation, p.472-478, June 21-25, 1999, New Orleans, Louisiana, United States
	Weiping Shi , Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Shih-Ping Lin , Yao-Wen Chang, A novel framework for multilevel routing considering routability and performance, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.44-50, November 10-14, 2002, San Jose, California
	Miloš Hrkić , John Lillis, Buffer tree synthesis with consideration of temporal locality, sink polarity requirements, solution cost and blockages, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Jiang Hu , Sachin S. Sapatnekar, A timing-constrained algorithm for simultaneous global routing of multiple nets, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Andrew B. Kahng , Bao Liu , Ion I. Mǎandoiu, Non-tree routing for reliability and yield improvement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.260-266, November 10-14, 2002, San Jose, California
	Pasquale Cocchini, Concurrent flip-flop and repeater insertion for high performance integrated circuits, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.268-273, November 10-14, 2002, San Jose, California
	Christoph Bartoschek , Stephan Held , Dieter Rautenbach , Jens Vygen, Efficient generation of short and fast repeater tree topologies, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Jingyu Xu , Xianlong Hong , Tong Jing , Yici Cai , Jun Gu, An efficient hierarchical timing-driven Steiner tree algorithm for global routing, Integration, the VLSI Journal, v.35 n.2, p.69-84, August 2003
	Amitava Bhaduri , Ranga Vemuri, Moment-driven coupling-aware routing methodology, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Huibo Hou , Sachin S. Sapatnekar, Routing tree topology construction to meet interconnect timing constraints, Proceedings of the 1998 international symposium on Physical design, p.205-210, April 06-08, 1998, Monterey, California, United States
	Jiang Hu , Sachin S. Sapatnekar, Simultaneous buffer insertion and non-Hanan optimization for VLSI interconnect under a higher order AWE model, Proceedings of the 1999 international symposium on Physical design, p.133-138, April 12-14, 1999, Monterey, California, United States
	Jiang Hu , Charles J. Alpert , Stephen T. Quay , Gopal Gandham, Buffer insertion with adaptive blockage avoidance, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Charles J. Alpert , Miloš Hrkić , Jiang Hu , Stephen T. Quay, Fast and flexible buffer trees that navigate the physical layout environment, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Miloš Hrkić , John Lillis, S-Tree: a technique for buffered routing tree synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Sampath Dechu , Zion Cien Shen , Chris C. N. Chu, An efficient routing tree construction algorithm with buffer insertion, wire sizing and obstacle considerations, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.361-366, January 27-30, 2004, Yokohama, Japan
	Charles J. Alpert , Miloš Hrkić , Stephen T. Quay, A fast algorithm for identifying good buffer insertion candidate locations, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Dian Zhou , Rui-Ming Li, Design and verification of high-speed VLSI physical design, Journal of Computer Science and Technology, v.20 n.2, p.147-165, March 2005
	Shiyan Hu , Qiuyang Li , Jiang Hu , Peng Li, Utilizing redundancy for timing critical interconnect, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.10, p.1067-1080, October 2007
	C. J. Alpert , Miloš Hrkić , J. Hu , A. B. Kahng , J. Lillis , B. Liu , S. T. Quay , S. S. Sapatnekar , A. J. Sullivan , P. Villarrubia, Buffered Steiner trees for difficult instances, Proceedings of the 2001 international symposium on Physical design, p.4-9, April 01-04, 2001, Sonoma, California, United States
	Shiyan Hu , Qiuyang Li , Jiang Hu , Peng Li, Steiner network construction for timing critical nets, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	D. Bañeres , J. Cortadella , M. Kishinevsky, Layout-aware gate duplication and buffer insertion, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Renato F. Hentschke , Jaganathan Narasimham , Marcelo O. Johann , Ricardo L. Reis, Maze routing steiner trees with effective critical sink optimization, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Jinjun Xiong , Lei He, Full-chip multilevel routing for power and signal integrity, Integration, the VLSI Journal, v.40 n.3, p.226-234, April, 2007
	Ruiming Chen , Hai Zhou, Efficient algorithms for buffer insertion in general circuits based on network flow, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.322-326, November 06-10, 2005, San Jose, CA
	Jingyu Xu , Xianlong Hong , Tong Jing , Yici Cai , Jun Gu, An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.473, January 07-11, 2002
	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
	Amitava Bhaduri , Ranga Vemuri, Inductive and Capacitive Coupling Aware Routing Methodology Driven by a Higher Order RLCK Moment Metric, Proceedings of the conference on Design, Automation and Test in Europe, p.922-923, March 07-11, 2005
	Zhuo Li , Weiping Shi, An O(bn^2) Time Algorithm for Optimal Buffer Insertion with b Buffer Types, Proceedings of the conference on Design, Automation and Test in Europe, p.1324-1329, March 07-11, 2005