skip to main content
10.1145/1228784.1228918acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

New timing and routability driven placement algorithms for FPGA synthesis

Published: 11 March 2007 Publication History

Abstract

We present new timing and congestion driven FPGA placement algorithms with minimal runtime overhead. By predicting the post-routing critical edges and estimating congestion accurately, our algorithms simultaneously reduce the critical path delay and the minimum number of routing tracks. The core of our algorithm consists of a criticality history record of connection edges and a congestion map. This approach is applied to the 20 largest MCNC benchmark circuits. Experimental results show that compared with VPR [1], our algorithms yield an average of 8.1% reduction (maximum 30.5%) in the critical path delay and 5% reduction in channel width. Meanwhile, the average runtime of our algorithms is only 2.3X as of VPR's.

References

[1]
V. Betz and J. Rose. VPR: A new packing, placement and routing tool for FPGA research. In Proceedings of the 7th International 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]
E. Bozorgzadeh, S. Ogrenci-Memik, X. Yang, and M. Sarrafzadeh. Routability-driven packing: Metrics and algorithms for cluster-based FPGAs. Journal of Circuits Systems and Computers, 13(1):77--100, 2004.
[4]
D. Chen and J. Cong. Daomap: a depth-optimal area optimization mapping algorithm for FPGA designs. In Proceedings of the IEEE/ACM International conference on Computer-aided design, pages 752--759, 2004.
[5]
C. Cheng. RISA: Accurate and efficient placement routability modeling. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 690--695, 1994.
[6]
A. DeHon. Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% lut utilization). In Proceedings of the ACM/SIGDA Seventh International Symposium on Field Programmable Gate Arrays, pages 69--78, 1999.
[7]
A. E. Dunlop, V. D. Agrawal, D. N. Deutsch, M. F. Jukl, P. Kozak, and M. Wiesel. Chip layout optimization using critical path weighting. In Proceedings of the 21st conference on Design automation, pages 133--136, 1984.
[8]
H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In Proceedings of the 35th annual conference on Design automation, pages 269--274, 1998.
[9]
T. Hamada, C.-K. Cheng, and P. M. Chau. Prime: a timing-driven placement tool using a piecewise linear resistive network approach. In Proceedings of the 30th international conference on Design automation, pages 531--536, 1993.
[10]
M. Jackson and E. S. Kuh. Performance-driven placement of cell based ic's. In Proceedings of the 26th ACM/IEEE conference on Design automation, pages 370--375, 1989.
[11]
T. Kong. A novel net weighting algorithm for timing-driven placement. In Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided Design, pages 172--176, 2002.
[12]
J. Y. Lin, D. Chen, and J. Cong. Optimal simultaneous mapping and clustering for fpga delay optimization. In Proceedings of the 43rd annual conference on design automation, pages 472--477, 2006.
[13]
A. Marquardt, V. Betz, and J. Rose. Timing-driven placement for FPGAs. In Proceedings of the ACM/SIGDA Eighth International Symposium 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]
A. Srinivasan, K. Chaudhary, and E. S. Kuh. Ritual: A performance driven placement algorithm for small cell ic's. In IEEE/ACM International Conference on Computer-Aided Design, pages 45--51, 1991.
[16]
R. Tessier. Fast placement approaches for FPGAs. ACM Transactions on Design Automation of Electronic Systems, 7(2):284--305, April 2002.
[17]
Q. Wang, J. Lillis, and S. Sanyal. An LP-based methodology for improved timing-driven placement. In Proceedings of the 2005 Conference on Asia South Pacific Design Automation, pages 1139--1147, 2005.
[18]
M. G. Wrighton and A. M. DeHon. Hardware-assisted simulated annealing with application for fast fpga placement. In Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, pages 33--42, 2003.
[19]
Y. Zhuo, H. Li, and S. P. Mohanty. A congestion driven placement algorithm for FPGA synthesis. In Proceedings of the 16th IEEE International Conference on Field Programmable Logic and Applications, 2006.

Cited By

View all
  • (2024)Exploring the Usage of Fast Carry Chains to Implement Multistage Ring Oscillators on FPGAs: Design and CharacterizationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2024.339530232:8(1472-1484)Online publication date: Aug-2024
  • (2023)On improving the critical path delay of PathFinder at smaller channel widths2023 22nd International Symposium on Communications and Information Technologies (ISCIT)10.1109/ISCIT57293.2023.10376068(127-132)Online publication date: 16-Oct-2023
  • (2009)Improving simulated annealing-based FPGA placement with directed movesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200916728:2(179-192)Online publication date: 1-Feb-2009
  • Show More Cited By

Index Terms

  1. New timing and routability driven placement algorithms for FPGA synthesis

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI
      March 2007
      626 pages
      ISBN:9781595936059
      DOI:10.1145/1228784
      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: 11 March 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. congestion driven placement
      2. net weight
      3. physical synthesis
      4. timing driven placement

      Qualifiers

      • Article

      Conference

      GLSVLSI07
      Sponsor:
      GLSVLSI07: Great Lakes Symposium on VLSI 2007
      March 11 - 13, 2007
      Stresa-Lago Maggiore, Italy

      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

      • Downloads (Last 12 months)2
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 27 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Exploring the Usage of Fast Carry Chains to Implement Multistage Ring Oscillators on FPGAs: Design and CharacterizationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2024.339530232:8(1472-1484)Online publication date: Aug-2024
      • (2023)On improving the critical path delay of PathFinder at smaller channel widths2023 22nd International Symposium on Communications and Information Technologies (ISCIT)10.1109/ISCIT57293.2023.10376068(127-132)Online publication date: 16-Oct-2023
      • (2009)Improving simulated annealing-based FPGA placement with directed movesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200916728:2(179-192)Online publication date: 1-Feb-2009
      • (2008)Criticality history guided FPGA placement algorithm for timing optimizationProceedings of the 18th ACM Great Lakes symposium on VLSI10.1145/1366110.1366175(267-272)Online publication date: 4-May-2008

      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