Performance-driven placement of cell based IC's

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Performance-driven placement of cell based IC's

Full text

Pdf (842 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 26th ACM/IEEE Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 370 - 375

Year of Publication: 1989

ISBN:0-89791-310-8

Authors

M. A. B. Jackson	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California
E. S. Kuh	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS\TCDA : TC Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 33, Citation Count: 48

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

ABSTRACT

The increasingly important role of the interconnect in the timing performance of present and future integrated circuit technologies underscores the need to reconsider conventional physical design CAD tools, and devise new ways to influence performance during layout. Interconnects are not perfect conductors, they introduce parasitic elements that load the logic gates and distort the temporal properties of the design as viewed by the logic designer. Cell placement that minimizes wirelength as the sole objective does not solve the problem, leaving a margin for performance improvement that has not been fully exploited. This paper presents a novel approach to performance-driven placement, combining timing analysis and physical design to dynamically optimize the performance of the chip during placement. The ideas are embodied in a program named Allegro, and preliminary results tested on Sea-of-Gate designs are encouraging.

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.

	Burs85	Michael Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
	Chen84	C. K. Cheng and E.S. Kuh, "Module Placement Based on Resistive Network Optimization," IEEE Trans. on Comput,er-Aided Design of Integrated Circuits and Systems, Vol. CAD-3, No. 3, July 1984, pp. 218-225.
	Dai87	W. M. Dai, H. It. Chen, et. al., "BEAR: A New Building-Block Layout System,"Proc. IEEE .rut 'l Conference on Computer-Aided Design, 1987, pp. 34-38.
	Dhar84	S. Dhar, M. A. Franklin, and D. F. Wann, "Reduction of Clock Delays in VLSI Structures,'IEEE International Conference on Computer Design, pp. 778-783, October 1984.
	DeLe87	R. De Leone and O. L Mangasarian,"Serial and Parallel Solution "of Large Scale Linear Programs by Augmented Lagrangian Successive Overrelaxation," Univ. of Wisconsin Computer Sciences Dept. Technical Report, No. 701, Nov. 1987.
	Dunl84	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
	Haug87	P. S. Hauge, R. Nair, and E. J. Yoffa, "Circuit Placement for Predictable Performance," Proe. IEEE Int7 Conference on Computer- Aided Design, 1987, pp. 88-91.
	Hitc83	R.B. Hitchcock, G.L. Smith and D.D. Cheng, "Timing Analysis of Computer Hardware," IBM Journal of Research and Development, vol. 26, no. 1, Jan. i983, pp. 100-105.
	Jack87	M. A. B. 3ackson, E.S. Kuh, M. Marek- Sadowska, "Timing-Driven Routing for Building Block Layout," Proe. IEEE Int'l Symposium on Circuits and Systems, 1987, pp. 518- 519.
	Karm84	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	Murt87	B. A. Murtagh, and M.A. Saunders, MINOS 5.1 USER's GUIDE, Stanford University Systems Optimization Laboratory, Technical Report SOL 83-20R, Jan. 1987.
	Ogaw86	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
	Teig86	S. Teig, R.L. Smith, and J. Seaton, "Timing- Driven Layout of Cell-Based IC's," VLSI Systems Design, May 1986, pp. 63-73.
	Tsay88	Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, Proud: a fast sea-of-gates placement algorithm, Proceedings of the 25th ACM/IEEE conference on Design automation, p.318-323, June 12-15, 1988, Atlantic City, New Jersey, United States

CITED BY 48

	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
	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
	Andrew A. Kennings , Igor L. Markov, Analytical minimization of half-perimeter wirelength, Proceedings of the 2000 conference on Asia South Pacific design automation, p.179-184, January 2000, Yokohama, Japan
	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
	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
	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
	Takeo Hamada , Chung-Kuan Cheng , Paul M. Chau, Prime: a timing-driven placement tool using a piecewise linear resistive network approach, Proceedings of the 30th international conference on Design automation, p.531-536, June 14-18, 1993, Dallas, Texas, United States
	Jin Huang , Xian-Long Hong , Chung-Kuan Cheng , E. S. Kuh, An efficient timing-driven global routing algorithm, Proceedings of the 30th international conference on Design automation, p.596-600, June 14-18, 1993, Dallas, Texas, United States
	Min Xu , Fadi J. Kurdahi, Layout-driven RTL binding techniques for high-level synthesis using accurate estimators, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.312-343, Oct. 1997
	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
	Jaewon Kim , S. M. Kang, A timing-driven data path layout synthesis with integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.716-719, November 05-09, 1995, San Jose, 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
	Henrik Esbensen , Ernest S. Kuh, A performance-driven IC/MCM placement algorithm featuring explicit design space exploration, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.1, p.62-80, Jan. 1997
	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
	Anmol Mathur , C. L. Liu, Compression-relaxation: a new approach to performance driven placement for regular architectures, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.130-136, November 06-10, 1994, San Jose, 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
	Soohong Kim , Robert M. Owens , Mary J. Irwin, PERFLEX: a performance driven module generator, Proceedings of the conference on European design automation, p.154-159, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	Weitong Chuang , Ibrahim N. Hajj, Delay and area optimization for compact placement by gate resizing and relocation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.145-148, November 06-10, 1994, San Jose, California, United States
	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
	Amir H. Ajami , Massoud Pedram, Post-layout timing-driven cell placement using an accurate net length model with movable Steiner points, Proceedings of the 2001 conference on Asia South Pacific design automation, p.595-600, January 2001, Yokohama, Japan
	Ikuo Harada , Hitoshi Kitazawa, A global router optimizing timing and area for high-speed bipolar LSI's, Proceedings of the 31st annual conference on Design automation, p.177-181, June 06-10, 1994, San Diego, 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
	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
	Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States
	W. K. Luk, A fast physical constraint generator for timing driven layout, Proceedings of the 28th conference on ACM/IEEE design automation, p.626-631, June 17-22, 1991, San Francisco, 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
	Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States
	Sung-Woo Hur , John Lillis, Relaxation and clustering in a local search framework: application to linear placement, Proceedings of the 36th ACM/IEEE conference on Design automation, p.360-366, June 21-25, 1999, New Orleans, Louisiana, United States
	Haoxing Ren , David Z. Pan , David S. Kung, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	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
	XianLong Hong , Tong Jing , JingYu Xu , HaiYun Bao , Jun Gu, CNB: a critical-network-based timing optimization method for standard cell global routing, Journal of Computer Science and Technology, v.18 n.6, p.732-738, November 2003
	Stelian Alupoaei , Srinivas Katkoori, Net Clustering Based Constructive and Iterative Improvement Approaches for Macro-Cell Placement, Journal of VLSI Signal Processing Systems, v.37 n.1, p.151-163, May 2004
	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
	Ting-Yuan Wang , Jeng-Liang Tsai , Charlie Chung-Ping Chen, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	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
	Chao-Yang Yeh , Malgorzata Marek-Sadowska, Skew-programmable clock design for FPGA and skew-aware placement, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA
	Qingzhou (Ben) Wang , Devang Jariwala , John Lillis, A study of tighter lower bounds in LP relaxation based placement, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	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
	Miloš Hrkić , Miloš Hrkić , John Lillis , Giancarlo Beraudo, An approach to placement-coupled logic replication, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Qingzhou (Ben) Wang , John Lillis , Shubhankar Sanyal, An LP-based methodology for improved timing-driven placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Yue Zhuo , Hao Li , Qiang Zhou , Yici Cai , Xianlong Hong, New timing and routability driven placement algorithms for FPGA synthesis, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	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
	A. B. Kahng , Q. Wang, An analytic placer for mixed-size placement and timing-driven placement, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.565-572, November 07-11, 2004
	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
	Jason Cong , Michail Romesis , Min Xie, Optimality and Stability Study of Timing-Driven Placement Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.472, November 09-13, 2003
	Hao Li , Yue Zhuo, Criticality history guided FPGA placement algorithm for timing optimization, Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 04-06, 2008, Orlando, Florida, USA