skip to main content
10.1145/1366110.1366175acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
research-article

Criticality history guided FPGA placement algorithm for timing optimization

Published: 04 May 2008 Publication History

Abstract

We present an efficient timing-driven placement algorithm for FPGAs. Our major contribution is a criticality history guided (CHG) approach that can simultaneously reduce the critical path delay and computation time. The proposed approach keeps track of the timing criticality history of each edge and utilizes this information to effectively guide the placer. We also present a cooling schedule that optimizes both timing and run time when combined with the CHG method. The proposed algorithm is applied to the 20 largest MCNC benchmark circuits. Experimental results show that compared with VPR, our algorithm yields an average of 21.7% reduction (maximum 45.8%) in the critical path delay and it runs 2.2X fasterthan VPR. In addition, our approach outperforms other algorithms discussed in the literature in both delay and run time.

References

[1]
V. Betz and J. Rose. VPR: A new packing, placement and routing tool for FPGA research. In Proc. of the 7th Int'l Workshop on Field Programmable Logic and Applications, pages 213--222, 1997.
[2]
V. Betz, J. Rose, and A. Marquardt. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers, 1999.
[3]
Y.-W. Chang and Y.-T. Chang. An architecture driven metric for simultaneous placement and global routing for FPGAs. In Proc. of the 37th DAC, pages 567--572, June 2000.
[4]
H. Eisenmann and F.M. Johannes. Generic global placement and floorplanning. In Proc. of the 35th DAC, pages 269--274, June 1998.
[5]
P. Gopalakrishnan, X. Li, and L. Pileggr. Architecture aware FPGA placement using metric embedding. In Proc. of the 43rd DAC, pages 460--465, June 2006.
[6]
T. Hamada, C.-K. Cheng, and P.M. Chau. Prime: a timing-driven placement tool using a piecewise linear resistive network approach. In Proc. of the 30th DAC, pages 531--536, June 1993.
[7]
M. Hutton, K. Adibsamii, and A. Leaver. Timing driven placement for hierarchical programmable logic devices. In Proc. of 9th Int'l Symp. on Field Programmable Gate Arrays, pages 3--11, 2001.
[8]
M. Jackson and E. S. Kuh. Performance-driven placement of cell based ICs. In Proc. of the 26th DAC, pages 370--375, June 1989.
[9]
A. Kennings and K. P. Vorwerk. Force-directed methods for generic placement. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 25(10):2076--2087, October 2006.
[10]
T. Kong. A novel net weighting algorithm for timing-driven placement. In Proc. of the 2002 Int'l Conf. on Computer-Aided Design, pages 172--176, November 2002.
[11]
Y. Lu, X. Hong, Q. Zhou, Y. Cai, and J. An efficient quadratic placement based on search space traversing technology. Integration, the VLSI Journal, 40(3):253--260, April 2007.
[12]
P. Maidee, C. Ababei, and K. Bazargan. Fast timing-driven partitioning-based placement for island style FPGAs. In Proc. of the 40th DAC, pages 598--603, 2003.
[13]
A. Marquardt, V. Betz, and J. Rose. Timing-driven placement for FPGAs. In Proc. of 8th Int'l Symp. on Field Programmable Gate Arrays, pages 203--213, 2000.
[14]
U. of Toronto. The FPGA place-and-route challenge. http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html.
[15]
H. Ren, D.Z. Pan, and D.S. Kung. Sensitivity guided net weighting for placement driven synthesis. In Proc. of 12th Int'l Symp. on Physical Design, pages 10--17, 2004.
[16]
A. Srinivasan, K. Chaudhary, and E.S. Kuh. Ritual: A performance driven placement algorithm for small cell ICs. In Int'l Conf. on Computer-Aided Design, pages 45--51, November 1991.
[17]
R. Tessier. Fast placement approaches for FPGAs. ACM Trans. on Design Automation of Electronic Systems, 7(2):284--305, April 2002.
[18]
Q. Wang, J. Lillis, and S. Sanyal. An LP-based methodology for improved timing-driven placement. In Proc. of the Conf. on Asia South Pacific Design Automation, pages 1139--1147, January 2005.
[19]
M.G. Wrighton and A.M. DeHon. Hardware-assisted simulated annealing with application for fast FPGA placement. In Proc. of 11th Int'l Symp. on Field programmable Gate Arrays, pages 33--42, 2003.
[20]
Y. Zhuo, H. Li, Q. Zhou, Y. Cai, and X. Hong. New timing and routability driven placement algorithms for fpga synthesis. In GLSVLSI 2007, pages 570--575, March 2007.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSI
May 2008
480 pages
ISBN:9781595939999
DOI:10.1145/1366110
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. fpga
  2. placement
  3. timing optimization

Qualifiers

  • Research-article

Conference

GLSVLSI08
Sponsor:
GLSVLSI08: Great Lakes Symposium on VLSI 2008
May 4 - 6, 2008
Florida, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25
Great Lakes Symposium on VLSI 2025
June 30 - July 2, 2025
New Orleans , LA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 192
    Total Downloads
  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media