Article

Timing optimization of FPGA placements by logic replication

Authors:

Giancarlo Beraudo,

John LillisAuthors Info & Claims

DAC '03: Proceedings of the 40th annual Design Automation Conference

Pages 196 - 201

https://doi.org/10.1145/775832.775885

Published: 02 June 2003 Publication History

Get Access

Abstract

Logic replication for placement level timing optimization is studied in the context of FPGAs. We make the observation that critical paths are dominated by interconnect delay and are frequently highly circuitous. We propose a systematic replication technique to "straighten" such paths. The resulting algorithm has several components: cell selection, slot selection for a duplicate cell, fanout partitioning and placement legalization. This algorithm is described and promising preliminary experimental results are reported with up to 29% improvement in critical path delay.

References

[1]

L.T. Liu, M.T. Kuo, C.K. Cheng, and T.C. Hu. A Replication Cut for Two-Way Partitioning, IEEE Trans. on CAD, 1995

Google Scholar

[2]

J. Hwang and A. El Gamal. Optimal replication for min-cut partitioning. ICCAD 1992

Digital Library

Google Scholar

[3]

W. K. Mak and D. F. Wong. Minimum replication min-cut partitioning. IEEE Transactions on CAD,. October 1997

Google Scholar

[4]

C. Kring and A. Newton. A cell-Replicating Approach to Mincut-Based Circuit Partitioning. ICCAD 1991

Google Scholar

[5]

V. Betz and J. Rose.VPR: A New Packing, Placement and Routing Tool for FPGA Research. 7th International Workshop on Field-Programmable Logic and Applications, 1997

Digital Library

Google Scholar

[6]

J. Lillis, C.-K. Cheng, T.-T. Y. Lin. Algorithms for Optimal Introduction of Redundant Logic for Timing and Area Optimization. Proc. IEEE International Symposium on Circuits and Systems, 1996

Crossref

Google Scholar

[7]

A. Srivastava, R. Kastner, M. Sarrafzadeh.Timing Driven Gate Duplication: Complexity Issues and Algorithms. ICCAD 2000

Digital Library

Google Scholar

[8]

S.-W. Hur and J. Lillis.Mongrel: Hybrid techniques for standard cell placement. ICCAD 2000.

Digital Library

Google Scholar

[9]

A. Marquardt, V. Betz and J. Rose. Timing-Driven Placement for FPGAs. International Symposium on FPGAs, 2000

Digital Library

Google Scholar

[10]

W. Gosti, A. Narayan, R. K. Brayton, A. L. Sangiovanni-Vincentelli. Wireplanning in logic synthesis. ICCAD 1998

Digital Library

Google Scholar

[11]

W. Gosti, S. P. Khatri, A. L. Sangiovanni-Vincentelli. Addressing The Timing Closure Problem By Integrating Logic Optimization And Placement. ICCAD-2001

Digital Library

Google Scholar

[12]

Neumann, D. Stoffel, H. Hartje, W. Kunz. Cell Replication and Redundancy Elimination During Placement for Cycle Time Optimization. ICCAD 1999

Digital Library

Google Scholar

Cited By

View all

Guo LLau JChi YWang JYu CChen ZZhang ZCong J(2020)Analysis and Optimization of the Implicit Broadcasts in FPGA HLS to Improve Maximum Frequency2020 57th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18072.2020.9218718(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/DAC18072.2020.9218718
Wagle AYang JDengi AVrudhula S(2018)FPGAs with Reconfigurable Threshold Logic Gates for Improved Performance, Power and Area2018 28th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2018.00051(256-2563)Online publication date: Aug-2018
https://doi.org/10.1109/FPL.2018.00051
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
Show More Cited By

Index Terms

Timing optimization of FPGA placements by logic replication
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

An approach to placement-coupled logic replication
DAC '04: Proceedings of the 41st annual Design Automation Conference

We present a set of techniques for placement-coupled, timing-driven logic replication. Two components are at the core of the approach. First is an algorithm for optimal timing-driven fanin tree embedding; the algorithm is very general in that it can ...
Techniques for improved placement-coupled logic replication
GLSVLSI '06: Proceedings of the 16th ACM Great Lakes symposium on VLSI

Several recent papers have utilized logic replication driven by placement-level timing analysis for improving clock period (e.g., [1], [8], [18], and [2]). All of these papers demonstrated, through various optimization strategies, the potential of the ...
Criticality history guided FPGA placement algorithm for timing optimization
GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSI

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 ...

Comments

Information & Contributors

Information

Published In

DAC '03: Proceedings of the 40th annual Design Automation Conference

June 2003

1014 pages

ISBN:1581136889

DOI:10.1145/775832

General Chair:
Ian Getreu
Ambric Inc., Portland, OR
,
Program Chairs:
Limor Fix
Intel Semiconductors Ltd., Haifa, Israel
,
Luciano Lavagno
Cadence Berkeley Labs., Berkeley, CA

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: 02 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC03

Sponsor:

SIGDA

DAC03: 2003 40th Annual Design Automation Conference

June 2 - 6, 2003

CA, Anaheim, USA

Acceptance Rates

DAC '03 Paper Acceptance Rate 152 of 628 submissions, 24%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
500
Total Downloads

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

Reflects downloads up to 25 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Guo LLau JChi YWang JYu CChen ZZhang ZCong J(2020)Analysis and Optimization of the Implicit Broadcasts in FPGA HLS to Improve Maximum Frequency2020 57th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18072.2020.9218718(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/DAC18072.2020.9218718
Wagle AYang JDengi AVrudhula S(2018)FPGAs with Reconfigurable Threshold Logic Gates for Improved Performance, Power and Area2018 28th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2018.00051(256-2563)Online publication date: Aug-2018
https://doi.org/10.1109/FPL.2018.00051
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
Vorwerk KKennings AGreene J(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
https://dl.acm.org/doi/10.1109/TCAD.2008.2009167
Sheldon DVahid FGebotys CMartin G(2008)Don't forget memoriesProceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis10.1145/1450135.1450171(155-160)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1450135.1450171
Gulati KKhatri SNarayanan VYan ZMacii EBhanja S(2008)Improving FPGA routability using network codingProceedings of the 18th ACM Great Lakes symposium on VLSI10.1145/1366110.1366147(147-150)Online publication date: 4-May-2008
https://dl.acm.org/doi/10.1145/1366110.1366147
Plaza SMarkov IBertacco VPan DNam G(2008)Optimizing non-monotonic interconnect using functional simulation and logic restructuringProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353653(95-102)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353653
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
Sheldon DVahid FHutton MChow P(2008)A pipelined binary tree as a case study on designing efficient circuits for an FPGA in a bram aware designProceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays10.1145/1344671.1344728(264-264)Online publication date: 24-Feb-2008
https://dl.acm.org/doi/10.1145/1344671.1344728
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
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

An approach to placement-coupled logic replication

Techniques for improved placement-coupled logic replication

Criticality history guided FPGA placement algorithm for timing optimization

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations