skip to main content
10.1145/1120725.1120783acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

A practical cut-based physical retiming algorithm for field programmable gate arrays

Published: 18 January 2005 Publication History

Abstract

This paper presents a heuristic cut-based retiming algorithm for FPGA designs. It handles complex retiming constraints including timing, architectural and structural constraints; improves retimeability by incorporating logic resynthesis; and efficiently integrates with incremental placement. Thus, the algorithm improves timing compliance by allowing groups of registers to be rapidly retimed across blocks of combinational logic in the physical domain without violating any complex constraints. Experiments have shown that this algorithm can improve the performance of FPGA designs by 16% on average, while achieving a 61.7% speedup in terms of runtime compared with classic retiming algorithms.

References

[1]
C. Leiserson, F. Rose and J. Saxe, "Optimizing Synchronous Circuitry". J. VLSI and Computer Systems, pp. 41--67, 1983.
[2]
S. Sapatnekar and R. Deokar, "Utilizing the retiming skew equivalence in a practical algorithm for retiming large circuits", IEEE Trans. on CAD of ICAS, pp. 1237--1248. Oct. 1996.
[3]
G. Even, I. Y. Spillinger and L. Stok, "Retiming revised and reversed", IEEE Trans. on CAD of ICAS, pp. 348--357, mar., 1996.
[4]
K. Lalgudi and M. Papaefthymiou, "DELAY: an efficient tool for retiming with realistic delay modeling", DAC Conf. pp. 304--309, 1995.
[5]
J. Cong and S. Lim, "Physical planning with retiming", ICCAD Conf., pp. 2--7, 2000.
[6]
D. Singh and S. Brown, "Integrated retiming and placement for field programmable gate arrays", FPGA 2002, pp. 67--76, 2002.
[7]
P. Suaris, D. Wang and N. Chou, "Smart Move: A Placement-aware Retiming And Replication Method for Field Programmable Gate Arrays", Proc. ASICON'2003, pp. 67--70, Beijing, China.
[8]
U. Seidl, K. Eckl and F. Johannes, "Performance-directed Retiming for FPGAs using Post-placement Delay Information", DATE'2003.
[9]
C. Chu, E. Young, D. Tong and S. Dechu, "Retiming with Interconnect and gate delay", ICCAD Conf., pp. 221--226, 2003.
[10]
"Altera Stratix FPGA family", Altera corporation, 2004.
[11]
Virtex-II 1.5V Field-Programmable Gate Arrays, Xilinx, 2001.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference
January 2005
1495 pages
ISBN:0780387376
DOI:10.1145/1120725
  • General Chair:
  • Ting-Ao Tang
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: 18 January 2005

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

ASPDAC05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 102
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 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