Timing-driven placement for FPGAs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Timing-driven placement for FPGAs

Full text

Pdf (883 KB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays table of contents

Monterey, California, United States

Pages: 203 - 213

Year of Publication: 2000

ISBN:1-58113-193-3

Authors

Alexander Marquardt	Right Track CAD Corp., 720 Spadina Ave., Suite #313, Toronto, ON and Dept. of Electrical and Computer Engineering, University of Toronto, 10 King's College Road, Toronto, ON, M5S 3G4
Vaughn Betz	Right Track CAD Corp., 720 Spadina Ave., Suite #313, Toronto, ON and Dept. of Electrical and Computer Engineering, University of Toronto, 10 King's College Road, Toronto, ON, M5S 3G4
Jonathan Rose	Right Track CAD Corp., 720 Spadina Ave., Suite #313, Toronto, ON and Dept. of Electrical and Computer Engineering, University of Toronto, 10 King's College Road, Toronto, ON, M5S 3G4

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 59, Citation Count: 53

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

ABSTRACT

In this paper we introduce a new Simulated Annealing-based timing-driven placement algorithm for FPGAs. This paper has three main contributions. First, our algorithm employs a novel method of determining source-sink connection delays during placement. Second, we introduce a new cost function that trades off between wire-use and critical path delay, resulting in significant reductions in critical path delay without significant increases in wire-use. Finally, we combine connection-based and path-based timing-analysis to obtain an algorithm that has the low time-complexity of connection-based timing-driven placement, while obtaining the quality of path-based timing-driven placement.A comparison of our new algorithm to a well known non-timing-driven placement algorithm demonstrates that our algorithm is able to increase the post-place-and-route speed (using a full path-based timing-driven router and a realistic routing architecture) of 20 MCNC benchmark circuits by an average of 42%, while only increasing the minimum wiring requirements by an average of 5%.

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	V. Betz, "Architecture and CAD for Speed and Area Optimization of FPGAs," Ph.D. Dissertation, University of Toronto, 1998.
	2	Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
	3	R. Hitchcock, G. Smith and D. Cheng, "Timing Analysis of Computer-Hardware," IBM Journal of Research and Development, Jan. 1983, pp. 100- 105.
	4	Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for island-style FPGAs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.332-338, November 05-09, 1995, San Jose, California, United States
	5	Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
	6	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 [doi>10.1145/217474.217531]
	7	B. Riess and Cx Ettelt, "SPEED: Fast and Efficient Timing Driven Placement," IEEE International Symposium on Circuits and Systems, 1995, pp. 377 - 380.
	8	S. Yang, "Logic Synthesis and Optimization Benchmarks, Version 3.0," Tech. Report, Microelectronics Center of North Carolina, 1991.
	9	E.M. Sentovich et al, "SIS: A System for Sequential Circuit Analysis," Tech. Report No. UCB/ERL M92/41, University of California, Berkeley, 1992.
	10	J. Cong and Y. Ding, "Flowmap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup- Table Based FPGA Designs," IEEE Trans. on CAD, Jan. 1994, pp. 1-12.
	11	Xilinx Inc., "Virtex 2.5 V Field Programmable Gate Arrays", Advance Product Data Sheet, 1998.
	12	S. Kirkpatrick, C. Gelatt and M. Vecchi, "Optimization by Simulated Annealing," Science, May 13, 1983, pp. 671 - 680.
	13	Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
	14	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 [doi>10.1145/217474.217531]
	15	A. Marquardt, "Cluster-Based Architecture, Timing-Driven Packing. and Timing-Driven Placement for FPGAs," M.A.Sc. Thesis, University of Toronto, 1999.

CITED BY 53

	Guy Lemieux , David Lewis, Using sparse crossbars within LUT, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.59-68, February 2001, Monterey, California, United States
	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
	Steven J. E. Wilton, A crosstalk-aware timing-driven router for FPGAs, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.21-28, February 2001, Monterey, California, United States
	Russell Tessier, Fast placement approaches for FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.2, p.284-305, April 2002
	Jason Cong , Xin Yuan, Multilevel global placement with retiming, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Joey Y. Lin , Ashok Jagannathan , Jason Cong, Placement-driven technology mapping for LUT-based FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	Jason Cong , Yiping Fan , Xun Yang , Zhiru Zhang, Architecture and synthesis for multi-cycle communication, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	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
	Giancarlo Beraudo , John Lillis, Timing optimization of FPGA placements by logic replication, 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
	Andy Ye , Jonathan Rose, Using bus-based connections to improve field-programmable gate array density for implementing datapath circuits, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA
	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
	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
	Gang Chen , Jason Cong, Simultaneous timing-driven placement and duplication, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA
	Jason H. Anderson , Farid N. Najm, Power estimation techniques for FPGAs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1015-1027, 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
	Hassan Hassan , Mohab Anis , Mohamed Elmasry, LAP: a logic activity packing methodology for leakage power-tolerant FPGAs, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, 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
	Liang-Yu Lin , Cheng-Yeh Wang , Pao-Jui Huang , Chih-Chieh Chou , Jing-Yang Jou, Communication-driven task binding for multiprocessor with latency insensitive network-on-chip, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	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
	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
	Jason H. Anderson , Farid N. Najm, Interconnect capacitance estimation for FPGAs, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.713-718, January 27-30, 2004, Yokohama, Japan
	Yan Lin , Lei He , Mike Hutton, Stochastic physical synthesis considering prerouting interconnect uncertainty and process variation for FPGAs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.2, p.124-133, February 2008
	Gang Chen , Jason Cong, Simultaneous placement with clustering and duplication, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.740-772, July 2006
	Hosung (Leo) Kim , John Lillis , Miloš Hrkić , Miloš Hrkić, Techniques for improved placement-coupled logic replication, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	Padmini Gopalakrishnan , Xin Li , Lawrence Pileggi, Architecture-aware FPGA placement using metric embedding, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	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
	Deming Chen , Jason Cong , Peichen Pan, FPGA Design Automation: A Survey, Foundations and Trends® in Electronic Design Automation, v.1 n.3, p.139-169, January 2006
	Yan Lin , Lei He, Stochastic physical synthesis for FPGAs with pre-routing interconnect uncertainty and process variation, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA
	Bo Hu, Timing-driven placement for heterogeneous field programmable gate array, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	David Kearney , Mark Jasiunas, Using simulated partial dynamic run-time reconfiguration to share embedded FPGA compute and power resources across a swarm of unpiloted airborne vehicles, EURASIP Journal on Embedded Systems, v.2007 n.1, p.8-8, January 2007
	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
	Shantanu Dutt , Huan Ren , Fenghua Yuan , Vishal Suthar, A network-flow approach to timing-driven incremental placement for ASICs, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, 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
	Di Wu , G. Venkataraman , Jiang Hu , Quiyang Li , R. Mahapatra, DiCER: distributed and cost-effective redundancy for variation tolerance, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.393-397, November 06-10, 2005, San Jose, CA
	Jason Cong , Yiping Fan , Guoling Han , Xun Yang , Zhiru Zhang, Architectural Synthesis Integrated with Global Placement for Multi-Cycle Communication, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.536, 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
	Julien Lamoureux , Steven J. E. Wilton, On the Interaction Between Power-Aware FPGA CAD Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.701, 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
	Ken Eguro , Scott Hauck, Enhancing timing-driven FPGA placement for pipelined netlists, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Andrew B. Kahng , Chul-Hong Park , Puneet Sharma , Qinke Wang, Lens aberration aware placement for timing yield, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.1, p.1-26, January 2009
	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
	Hosung (Leo) Kim , John Lillis, A framework for layout-level logic restructuring, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Catherine L. Zhou , Wai-Chung Tang , Wing-Hang Lo , Yu-Liang Wu, How much can logic perturbation help from netlist to final routing for FPGAs, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Keith So, Enforcing long-path timing closure for FPGA routing with path searches on clamped lexicographic spirals, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA
	Wei Zhang , Li Shang , Niraj K. Jha, NanoMap: an integrated design optimization flow for a hybrid nanotube/CMOS dynamically reconfigurable architecture, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Raphael Rubin , André DeHon, Choose-your-own-adventure routing: lightweight load-time defect avoidance, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, February 22-24, 2009, Monterey, California, USA
	Chia-I Chen , Juinn-Dar Huang, CriAS: a performance-driven criticality-aware synthesis flow for on-chip multicycle communication architecture, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Yifang Liu , Rupesh S. Shelar , Jiang Hu, Delay-optimal simultaneous technology mapping and placement with applications to timing optimization, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Amit Agarwal , Jason Cong , Brian Tagiku, Fault tolerant placement and defect reconfiguration for nano-FPGAs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Wei Zhang , Niraj K. Jha , Li Shang, A hybrid Nano/CMOS dynamically reconfigurable system—Part II: Design optimization flow, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.5 n.3, p.1-31, August 2009