Timing influenced layout design

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Timing influenced layout design

Full text

Pdf (674 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 22nd ACM/IEEE Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 124 - 130

Year of Publication: 1985

ISBN:0-8186-0635-5

Authors

Michael Burstein	Tangent Systems, 2840 San Tomas Expressway, Santa Clara, CA and IBM T. J. Watson Research Center, Yorktown Heights, New York
Mary N. Youssef	IBM Corporation, East Fishkill, Hopewell Junction, New York

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 13, Citation Count: 38

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

ABSTRACT

We present a new approach to the automatic layout design for VLSI chips which incorporates timing information to influence the placement and wiring processes. This approach is an extension of the hierarchical layout method, in which placement and wiring are performed simultaneously [1]. We add a third phase of timing to the hierarchy, without affecting the computational complexity of the basic algorithm. Prior to the physical design, timing analysis is performed using statistical estimates for the unknown parameters; namely the lengths of interconnecting wires. The output of this analysis includes a measure for each net that indicates the degree of its contribution to the timing problem. This set of measures is used to bias the placement at the highest level of the hierarchy. Since wiring is performed after each level of partitioning, lengths of interconnecting nets among the partitions become available. These data are used to update the timing information that bias the design. Preliminary results show that, while delays due to interconnections are reduced, wireability of the chip does not deteriorate.

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	Burstein M., S. J. Hong and R. Pelavin, "Hierarchical VLSI Layout: Simultaneous Placement and Wiring of Gate Arrays," Proc. IFIP VLSI-83, Trondheim, August 1983.
	2	Wolf P. K., Sr. et al, "Power/Tilning: Optimization and Layout Techniques for LSI Chips," Design Automation and Fault Tolerant Computing, 1978.
	3	A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
	4	Hitchcock, R. Sr., G. Smith, D. Cheng, "Timing Analysis of Computer Hardware," IBM Journal of Research and Development, Vol. 26, NO. 1, 1982.
	5	Kernighan, B. W. and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, Vol. 49, 1982.
	6	C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
	7	Burstein M. and Pelavin, R., "Hier~trchical Wire Routing," IEEE Trans. on Computer-Aided Design 9f Integrated Data and Systems," Vol. CAD-2, No.4, 1983.
	8	Burstein M. and Pelavila, R., "Hierarchical Wire of Gate-Array VLSI Chips", Proe. ECCTD'83 (6-th European Conf. Circuit Theory and Design), Stuttgart, Germany, 1983.

CITED BY 38

	Qinghua Liu , Bo Hu , Malgorzata Marek-Sadowska, Wire length prediction in constraint driven placement, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	Wen-Ben Jone , Chen-Liang Fang, Timing optimization by gate resizing and critical path identification, Proceedings of the 30th international conference on Design automation, p.135-140, June 14-18, 1993, Dallas, Texas, United States
	M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States
	Ichiang Lin , David H. C. Du, Performance-driven constructive placement, Proceedings of the 27th ACM/IEEE conference on Design automation, p.103-106, June 24-27, 1990, Orlando, Florida, United States
	Vi Cuong Chan , David M. Lewis, Area-speed tradeoffs for hierarchical field-programmable gate arrays, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.51-57, February 11-13, 1996, Monterey, California, United States
	Jacques Benkoski , Andrzej J. Strojwas, The role of timing verification in layout synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.612-619, June 17-22, 1991, San Francisco, California, United States
	S. Kim , R. M. Owens , M. J. Irwin, Experiments with a performance driven module generator, Proceedings of the 29th ACM/IEEE conference on Design automation, p.687-690, June 08-12, 1992, Anaheim, California, United States
	Suphachai Sutanthavibul , Eugene Shragowitz, An adaptive timing-driven layout for high speed VLSI, Proceedings of the 27th ACM/IEEE conference on Design automation, p.90-95, June 24-27, 1990, Orlando, Florida, United States
	S. Prasitjutrakul , W. J. Kubitz, Path-delay constrained floorplanning: a mathematical programming approach for initial placement, Proceedings of the 26th ACM/IEEE conference on Design automation, p.364-369, June 25-28, 1989, Las Vegas, Nevada, United States
	Yasushi Ogawa , Tatsuki Ishii , Yoichi Shiraishi , Hidekazu Terai , Tokinori Kozawa , Kyoji Yuyama , Kyoji Chiba, Efficient placement algorithms optimizing delay for high-speed ECL masterslice LSIs, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.404-410, July 1986, Las Vegas, Nevada, United States
	Y. Fujihara , Y. Sekiyama , Y. Ishibashi , M. Yanaka, DYNAJUST: an efficient automatic routing technique optimizing delay conditions, Proceedings of the 26th ACM/IEEE conference on Design automation, p.791-794, June 25-28, 1989, Las Vegas, Nevada, United States
	Srilata Raman , C. L. Liu , Larry G. Jones, A delay driven FPGA placement algorithm, Proceedings of the conference on European design automation, p.277-282, September 19-23, 1994, Grenoble, France
	J. Frankle, Iterative and adaptive slack allocation for performance-driven layout and FPGA routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.536-542, June 08-12, 1992, Anaheim, California, United States
	T. Gao , P. M. Vaidya , C. L. Liu, A performance driven macro-cell placement algorithm, Proceedings of the 29th ACM/IEEE conference on Design automation, p.147-152, June 08-12, 1992, Anaheim, California, United States
	William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States
	R.-B. Lin , E. Shragowitz, Fuzzy logic approach to placement problem, Proceedings of the 29th ACM/IEEE conference on Design automation, p.153-158, June 08-12, 1992, Anaheim, California, United States
	Ingmar Neumann , Dominik Stoffel , Hendrik Hartje , Wolfgang Kunz, Cell replication and redundancy elimination during placement for cycle time optimization, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.25-30, November 07-11, 1999, San Jose, California, United States
	Yasushi Ogawa , Tsutomu Itoh , Yoshio Miki , Tatsuki Ishii , Yasuo Sato , Reiji Toyoshima, Timing- and constraint-oriented placement for interconnected LSIs in mainframe design, Proceedings of the 28th conference on ACM/IEEE design automation, p.253-258, June 17-22, 1991, San Francisco, California, United States
	S. Kim , P. Banerjee , V. Chickermane , J. H. Patel, APT: an area-performance-testability driven placement algorithm, Proceedings of the 29th ACM/IEEE conference on Design automation, p.141-146, June 08-12, 1992, Anaheim, California, United States
	H. Chang , E. Shragowitz , J. Liu , H. Youssef , B. Lu , S. Sutanthavibul, Net criticality revisited: an effective method to improve timing in physical design, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	S. A. Senouci , A. Amoura , H. Krupnova , G. Saucier, Timing driven floorplanning on programmable hierarchical targets, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.85-92, February 22-25, 1998, Monterey, California, United States
	Massoud Pedram , Narasimha Bhat, Layout driven technology mapping, Proceedings of the 28th conference on ACM/IEEE design automation, p.99-105, June 17-22, 1991, San Francisco, California, United States
	Shyam Ramji , Nagu R. Dhanwada, Design topology aware physical metrics for placement analysis, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA
	Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Adaptive delay estimation for partitioning-driven PLD placement, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.60-63, February 2003
	J. Garbers , B. Korte , H. J. Prömel , E. Schwietzke , A. Steger, VLSI: placement based on routing and timing information, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	Masayuki Terai , Kazuhiro Takahashi , Koji Sato, A new min-cut placement algorithm for timing assurance layout design meeting net length constraint, Proceedings of the 27th ACM/IEEE conference on Design automation, p.96-102, June 24-27, 1990, Orlando, Florida, United States
	Ren-Song Tsay , Juergen Koehl, An analytic net weighting approach for performance optimization in circuit placement, Proceedings of the 28th conference on ACM/IEEE design automation, p.620-625, June 17-22, 1991, San Francisco, California, United States
	Suphachai Sutanthavibul , Eugene Shragowitz, Dynamic prediction of critical paths and nets for constructive timing-driven placement, Proceedings of the 28th conference on ACM/IEEE design automation, p.632-635, June 17-22, 1991, San Francisco, California, United States
	Jason Cong , Joseph R. Shinnerl , Min Xie , Tim Kong , Xin Yuan, Large-scale circuit placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.389-430, April 2005
	Chao-Yang Yeh , Malgorzata Marek-Sadowska, Sequential delay budgeting with interconnect prediction, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1028-1037, October 2004
	Qinghua Liu , Bo Hu , Malgorzata Marek-Sadowska, Individual wire-length prediction with application to timing-driven placement, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1004-1014, October 2004
	Tim (Tianming) Kong, A novel net weighting algorithm for timing-driven placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.172-176, November 10-14, 2002, San Jose, California
	Andrew B. Kahng , Stefanus Mantik , Igor L. Markov, Min-max placement for large-scale timing optimization, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Tao Luo , David Newmark , David Z. Pan, A new LP based incremental timing driven placement for high performance designs, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Taraneh Taghavi , Foad Dabiri , Ani Nahapetian , Majid Sarrafzadeh, Tutorial on congestion prediction, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	Michael D. Moffitt , David A. Papa , Zhuo Li , Charles J. Alpert, Path smoothing via discrete optimization, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Jason Cong , Tim Kong , Joseph R. Shinnerl , Min Xie , Xin Yuan, Large-Scale Circuit Placement: Gap and Promise, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.883, November 09-13, 2003
	Chi-Ming Tsai , Kun-Tien Kuo , Chyi-Hui Hong , Rung-Bin Lin, An Adaptive Interconnect-Length Driven Placer, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.393, January 07-11, 2002