Timing driven placement for large standard cell circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Timing driven placement for large standard cell circuits

Full text

Pdf (57 KB)

Source

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

San Francisco, California, United States

Pages: 211 - 215

Year of Publication: 1995

ISBN:0-89791-725-1

Authors

William Swartz	TimberWolf Systems, Inc., 10880 Cassandra Way, Dallas, TX
Carl Sechen	Department of Electrical Engineering, University of Washington, Seattle, Washington

Sponsors

EDAC : Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/217474.217531 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	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]
	2	Wilm E. Donath , Reini J. Norman , Bhuwan K. Agrawal , Stephen E. Bello , Sang Yong Han , Jerome M. Kurtzberg , Paul Lowy , Roger I. McMillan, Timing driven placement using complete path delays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.84-89, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123232]
	3	S.E. Dreyfus, "An Appraisal of Some Shortest-Path Algorithms," Operations Research, Vol. 17, 1969, pp. 395- 412.
	4	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
	5	P. de Forcrand and H. Zimmermann, "Timing-Driven Auto- Placement," Proc. Int. Conf on Comp. Design, 1987, pp. 518- 521.
	6	T. Gao, P. M. Vidya, and C. L. Liu, "A New Performance Driven Placement Algorithm," Proc. Int. Conf. on Computed- Aided Design, November 1991, pp. 44-47.
	7	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
	8	T. Hasegawa, "A New Placement Algorithm Minimizing Path Delays," Proc. Int. Conf. on Computed-Aided Design, 1991, pp. 2052-2055.
	9	P. Hauge, R. Nair, and E. Yoffa, "Circuit Placement for Predictable Performance." Proc. Int. Conf. on Computed- Aided Design, 1987, pp. 88-91.
	10	R.B. Hitchcock, G. L. Smith, D. D. Cheng, "Timing analysis of computer hardware," IBM Journal of Research and Development, Vol 24, No. 1, Jan. 1983, pp. 100-105.
	11	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 [doi>10.1145/74382.74444]
	12	M. Jackson, E. Kuh, and M. Marek-Sadowska, "Timing- Driven Routing for Building Block Layout," Proc. of Int. Symp. Circuits and Systems, 1987, pp. 518-519.
	13	E. Lawler, Combinatorial Optimization: Networks and Matroids (New York: Holt, Rinehart, and Winston, 1976), pp. 98-106.
	14	M. Marek-Sadowska and S. Lin, "Timing Driven Placement." Proc. Int. Conf. on Computed-Aided Design, 1989, pp. 94-97.
	15	Arvind Srinivasan, An algorithm for performance-driven initial placement of small-cell ICs, Proceedings of the 28th conference on ACM/IEEE design automation, p.636-639, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127743]
	16	Wern-Jieh Sun , Carl Sechen, Efficient and effective placement for very large circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.170-177, November 07-11, 1993, Santa Clara, California, United States
	17	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 [doi>10.1145/127601.127165]
	18	W. Swartz and C. Sechen, "New Algorithms for the Placement and Routing of Macro Cells," Proc. Int. Conf. on Computed- Aided Design, 1990, pp. 336-339.
	19	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 [doi>10.1145/123186.123234]
	20	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 [doi>10.1145/127601.122882]
	21	J.Y. Yen, "Finding the K Shortest Loopless Paths in a Network," Management Science, Vol. 17, July 1971, pp. 712- 716.

CITED BY 55

	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
	J. Song , Z. Shen , W. Zhuang, An effective general connectivity concept for clustering, Proceedings of the conference on Design, automation and test in Europe, p.398-405, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Timing-driven placement for hierarchical programmable logic devices, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.3-11, February 2001, Monterey, California, United States
	Maogang Wang , Xiaojian Yang , Kenneth Eguro , Majid Sarrafzadeh, Multi-center congestion estimation and minimization during placement, Proceedings of the 2000 international symposium on Physical design, p.147-152, May 2000, San Diego, California, United States
	Jason Cong , Zhigang Pan , Lei He , Cheng-Kok Koh , Kei-Yong Khoo, Interconnect design for deep submicron ICs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.478-485, November 09-13, 1997, San Jose, California, United States
	Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, Timing driven placement using physical net constraints, Proceedings of the 38th conference on Design automation, p.780-783, June 2001, Las Vegas, Nevada, United States
	Patrick H. Madden, Reporting of standard cell placement results, Proceedings of the 2001 international symposium on Physical design, p.30-35, April 01-04, 2001, Sonoma, California, United States
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States
	Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, A sensitivity based placer for standard cells, Proceedings of the 10th Great Lakes symposium on VLSI, p.193-196, March 02-04, 2000, Chicago, Illinois, United States
	Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, 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
	Charles J. Alpert , Tony F. Chan , Dennis J.-H. Huang , Andrew B. Kahng , Igor L. Markov , Pep Mulet , Kenneth Yan, Faster minimization of linear wirelength for global placement, Proceedings of the 1997 international symposium on Physical design, p.4-11, April 14-16, 1997, Napa Valley, California, United States
	A. Albrecht , S. K. Cheung , K. S. Leung , C. K. Wong, On the Convergence of Inhomogeneous Markov Chains Approximating Equilibrium Placements of Flexible Objects, Computational Optimization and Applications, v.19 n.2, p.179-208, July 2001
	Satoshi Ono , Patrick H. Madden, On structure and suboptimality in placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	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
	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
	Andrew B. Kahng , Stefanus Mantik , Igor L. Markov , Miodrag Potkonjak , Paul Tucker , Huijuan Wang , Gregory Wolfe, Robust IP watermarking methodologies for physical design, Proceedings of the 35th annual conference on Design automation, p.782-787, June 15-19, 1998, San Francisco, California, United States
	R. Venkatraman , Lalit M. Patnaik, An evolutionary approach to timing driven FPGA placement, Proceedings of the 10th Great Lakes symposium on VLSI, p.81-85, March 02-04, 2000, Chicago, Illinois, 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
	Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Sung-Woo Hur , Tung Cao , Karthik Rajagopal , Yegna Parasuram , Amit Chowdhary , Vladimir Tiourin , Bill Halpin, Force directed mongrel with physical net constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, 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
	Pongstorn Maidee , Cristinel Ababei , Kia Bazargan, Fast timing-driven partitioning-based placement for island style FPGAs, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States
	Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, 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
	Bernd Obermeier , Frank M. Johannes, Quadratic placement using an improved timing model, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	A. Albrecht , S. K. Cheung , K. C. Hui , K. S. Leung , C. K. Wong, Optimal Placements of Flexible Objects: Part II: A Simulated Annealing Approach for the Bounded Case, IEEE Transactions on Computers, v.46 n.8, p.905-929, August 1997
	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
	Ateen Khatkhate , Chen Li , Ameya R. Agnihotri , Mehmet C. Yildiz , Satoshi Ono , Cheng-Kok Koh , Patrick H. Madden, Recursive bisection based mixed block placement, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	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
	Karthik Rajagopal , Tal Shaked , Yegna Parasuram , Tung Cao , Amit Chowdhary , Bill Halpin, Timing driven force directed placement with physical net constraints, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Prashant Saxena , Noel Menezes , Pasquale Cocchini , Desmond A. Kirkpatrick, The scaling challenge: can correct-by-construction design help?, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Pradeep Ramachandaran , Ameya R. Agnihotri , Satoshi Ono , Purushothaman Damodaran , Krishnaswami Srihari , Patrick H. Madden, Optimal placement by branch-and-price, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	A. Albrecht , S. K. Cheung , K. C. Hui , K. S. Leung , C. K. Wong, Optimal Placements of Flexible Objects: Part I: Analytical Results for the Unbounded Case, IEEE Transactions on Computers, v.46 n.8, p.890-904, August 1997
	Wenting Hou , Xianlong Hong , Weimin Wu , Yici Cai, A path-based timing-driven quadratic placement algorithm, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	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
	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
	Chunhong Chen , Xiaojian Yang , Majid Sarrafzadeh, Potential slack: an effective metric of combinational circuit performance, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	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
	Min Pan , Chris Chu, FastRoute: a step to integrate global routing into placement, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	William Swartz, Issues in global routing, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	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
	K. Vorwerk , A. Kennings , A. Vannelli, Engineering details of a stable force-directed placer, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.573-580, November 07-11, 2004
	Mehmet Can Yildiz , Patrick H. Madden, Improved cut sequences for partitioning based placement, Proceedings of the 38th conference on Design automation, p.776-779, June 2001, Las Vegas, Nevada, United States
	Ameya Agnihotri , Mehmet Can YILDIZ , Ateen Khatkhate , Ajita Mathur , Satoshi Ono , Patrick H. Madden, Fractional Cut: Improved Recursive Bisection Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.307, November 09-13, 2003
	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
	Hsiao-Ping Tseng , C. Sechen, A gridless multi-layer router for standard cell circuits using CTM cells, Proceedings of the 1997 European conference on Design and Test, p.319, March 17-20, 1997
	Kristofer Vorwerk , Andrew Kennings, An Improved Multi-Level Framework for Force-Directed Placement, Proceedings of the conference on Design, Automation and Test in Europe, p.902-907, March 07-11, 2005
	Wing On Fung , Tughrul Arslan, A power-aware algorithm for the design of reconfigurable hardware during high level placement, International Journal of Knowledge-based and Intelligent Engineering Systems, v.12 n.3, p.237-244, August 2008
	Wing On Fung , Tughrul Arslan, A power-aware algorithm for the design of reconfigurable hardware during high level placement, International Journal of Knowledge-based and Intelligent Engineering Systems, v.12 n.3, p.237-244, August 2008
	Sandip Aine , Rajeev Kumar , P. P. Chakrabarti, Adaptive parameter control of evolutionary algorithms to improve quality-time trade-off, Applied Soft Computing, v.9 n.2, p.527-540, March, 2009
	Fan Mo , Robert K. Brayton, Placement based multiplier rewiring for cell-based designs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California