Article

Using logic duplication to improve performance in FPGAs

Authors:

Karl Schabas,

Stephen D. BrownAuthors Info & Claims

FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays

Pages 136 - 142

https://doi.org/10.1145/611817.611838

Published: 23 February 2003 Publication History

Get Access

Abstract

The purpose of this paper is to introduce a modified packing and placement algorithm for FPGAs that utilizes logic duplication to improve performance. The modified packing algorithm was designed to leave unused basic logic elements (BLEs) in timing critical clusters, to allow potential targets for logic duplication. The modified placement algorithm consists of a new stage after placement in which logic duplication is performed to shorten the length of the critical path. In this paper, we show that in a representative FPGA architecture using .18 mm technology, the length of the final critical path can be reduced by an average of 14.1%. Approximately half of this gain comes directly from the changes to the packing algorithm while the other half comes from the logic duplication performed during placement.

References

[1]

Altera. "Stratix Datasheets", Available from: http://www.altera.com/products/devices/stratix/stx-index.jsp http://www.altera.com

Google Scholar

[2]

Betz V. Architecture and CAD for Speed and Area Optimization of FPGAs. Ph. D. Dissertation, University of Toronto, 1998.

Google Scholar

[3]

Betz, V., and Rose, J. VPR: A New Packing, Placement and Routing tool for FPGA research. Int. Workshop on Field-Programmable Logic and Applications, 1997, pp. 213--222.

Digital Library

Google Scholar

[4]

Betz, V., Rose J., and Marquardt A. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers, 1999.

Digital Library

Google Scholar

[5]

Cheng C. RISA: Accurate and Efficient Placement Routability Modeling. ICCAD, 1994, pp. 690--695.

Digital Library

Google Scholar

[6]

Cong, J. and Ding, Y. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. On Computer-Aided Design, Jan. 1994, pp. 1--12.

Google Scholar

[7]

Kirkpatrick, S., Gelatt, C., and Vecchi M. Optimization by Simulated Annealing. Science, May 13, 1983, pp. 671--680.

Google Scholar

[8]

Marquardt, A., Betz, V., and Rose, J. Using Cluster-Based Logic blocks and Timing-Driven Packing to Improve FPGA Speed and Density. ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Monterey, CA, February 1999, pp. 37--46.

Digital Library

Google Scholar

[9]

Schabas, K. M.A.Sc. Thesis in Progress: Using Logic Duplication to Improve Performance in FPGAs. University of Toronto, 2002.

Google Scholar

[10]

Sentovich, E. M., et al. SIS: A System for Sequential Circuit Analysis. Tech. Report No. UCB/ERL M92/41, University of California, Berkeley, 1992.

Google Scholar

[11]

Singh, A. and Marek-Sadowska, M. Efficient Circuit Clustering for Area and Power Reduction in FPGAs. International Symposium on Field Programmable Gate arrays, Monterey, CA, February 2002, pp 59--66.

Digital Library

Google Scholar

Cited By

View all

Hutton MBetz VAnderson J(2016)FPGA Synthesis and Physical DesignElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-18(373-413)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-18
Leow YAkoglu A(2013)A Hybrid FPGA Model to Estimate On-Chip Crossbar Logic Utilization in SoC PlatformsProceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum10.1109/IPDPSW.2013.138(239-246)Online publication date: 20-May-2013
https://dl.acm.org/doi/10.1109/IPDPSW.2013.138
Ahmed TKundarewich PAnderson J(2009)Packing Techniques for Virtex-5 FPGAsACM Transactions on Reconfigurable Technology and Systems10.1145/1575774.15757772:3(1-24)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1145/1575774.1575777
Show More Cited By

Index Terms

Using logic duplication to improve performance in FPGAs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Simultaneous timing-driven placement and duplication
FPGA '05: Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays

Logic duplication is an effective method for improving circuit performance. In this paper we present an algorithm named SPD that performs simultaneous placement and duplication to minimize the longest path delay. We introduce the notion of feasible ...
Simultaneous placement with clustering and duplication

Clustering, duplication, and placement are critical steps in a cluster-based FPGA design flow. Clustering has a great impact on the wirelength, timing, and routability of a circuit. Logic duplication is an effective method for improving performance ...
Simultaneous placement with clustering and duplication
DAC '04: Proceedings of the 41st annual Design Automation Conference

Clustering, duplication, and placement are critical steps in a cluster-based FPGA design flow. Clustering has a great impact on the wirelength, timing, and routability of a circuit. Logic duplication is an effective method for improving performance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays

February 2003

256 pages

ISBN:158113651X

DOI:10.1145/611817

General Chair:
Steve Trimberger
Xilinx
,
Program Chair:
Russ Tessier
University of Massachusetts - Amherst

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 February 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

FPGA03

Sponsor:

FPGA03: ACM/SIGDA International Symposium on Field Programmable Gate Arrays 2003

February 23 - 25, 2003

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
483
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hutton MBetz VAnderson J(2016)FPGA Synthesis and Physical DesignElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-18(373-413)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-18
Leow YAkoglu A(2013)A Hybrid FPGA Model to Estimate On-Chip Crossbar Logic Utilization in SoC PlatformsProceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum10.1109/IPDPSW.2013.138(239-246)Online publication date: 20-May-2013
https://dl.acm.org/doi/10.1109/IPDPSW.2013.138
Ahmed TKundarewich PAnderson J(2009)Packing Techniques for Virtex-5 FPGAsACM Transactions on Reconfigurable Technology and Systems10.1145/1575774.15757772:3(1-24)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1145/1575774.1575777
Pevzner VKennings AFox ANam GSaxena P(2009)Physical optimization for FPGAs using post-placement topology rewritingProceedings of the 2009 international symposium on Physical design10.1145/1514932.1514955(91-98)Online publication date: 29-Mar-2009
https://dl.acm.org/doi/10.1145/1514932.1514955
Lamoureux JWilton S(2008)On the trade-off between power and flexibility of FPGA clock networksACM Transactions on Reconfigurable Technology and Systems10.1145/1391732.13917331:3(1-33)Online publication date: 19-Sep-2008
https://dl.acm.org/doi/10.1145/1391732.1391733
Kim HLillis JPan DNam G(2008)A framework for layout-level logic restructuringProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353652(87-94)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353652
Ahmed TKundarewich PAnderson JTaylor BAggarwal RHutton MChow P(2008)Architecture-specific packing for virtex-5 FPGAsProceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays10.1145/1344671.1344675(5-13)Online publication date: 24-Feb-2008
https://dl.acm.org/doi/10.1145/1344671.1344675
Lamoureux JWilton S(2007)Clock-Aware Placement for FPGAs2007 International Conference on Field Programmable Logic and Applications10.1109/FPL.2007.4380636(124-131)Online publication date: Aug-2007
https://doi.org/10.1109/FPL.2007.4380636
Kim HLillis JHrkić MQu GIsmail YNarayanan VZhou H(2006)Techniques for improved placement-coupled logic replicationProceedings of the 16th ACM Great Lakes symposium on VLSI10.1145/1127908.1127959(211-216)Online publication date: 30-Apr-2006
https://dl.acm.org/doi/10.1145/1127908.1127959
Hutton MKarchmer DArchell BGovig JSchmit HWilton S(2005)Efficient static timing analysis and applications using edge masksProceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays10.1145/1046192.1046215(174-183)Online publication date: 20-Feb-2005
https://dl.acm.org/doi/10.1145/1046192.1046215
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Simultaneous timing-driven placement and duplication

Simultaneous placement with clustering and duplication

Simultaneous placement with clustering and duplication