research-article

Timing constraint-driven technology mapping for FPGAs considering false paths and multi-clock domains

Authors:

Martin D. F. Wong,

Jason GovigAuthors Info & Claims

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

Pages 370 - 375

Published: 05 November 2007 Publication History

Abstract

Modern FPGA chips contain multiple dedicated clocking networks, because nearly all real designs contain multiple clock domains. In this paper, we present an FPGA technology mapping algorithm targeting designs with multi-clock domains such as those containing multi-clocks, multi-cycle paths, and false paths. We use timing constraints to handle these unique clocking issues. We work on timing constraint graphs and process multiple arrival/required times for each node in the gate-level netlist. We also recognize and process constraint conflicts efficiently. Our algorithm produces a mapped circuit with the optimal mapping depth under timing constraints. To the best of our knowledge, this is the first FPGA mapping algorithm working with multi-clock domains. Experiments show that our algorithm is able to improve circuit performance by 16.8% on average after placement and routing for a set of benchmarks with multi-cycle paths, comparing to a previously published depth-optimal algorithm that does not consider multi-cycle paths.

References

[1]

M. Hutton et al. Efficient static timing analysis and applications using edge masks. In FPGA, pages 174--183, 2005.

Digital Library

[2]

J. Benkoski et al. Timing verification using statically sensitizable paths. TCAD, 9(10):1073--1084, 1990.

[3]

D. H. C. Du, S. H. C. Yen, and S. Ghanta. On the General False Path Problem in Timing Analysis. In DAC, pages 555--560, 1989.

Digital Library

[4]

S. Perremans, L. Claesen, and H. De Man. Static timing analysis of dynamically sensitizable paths. In DAC, pages 568--573, 1989.

Digital Library

[5]

P. C. McGeer and R. K. Brayton. Efficient algorithms for computing the longest viable path in a combinational network. In DAC, pages 561--567, 1989.

Digital Library

[6]

D. Brand and V. S. Iyengar. Timing analysis using functional analysis. Technical report, BM Thomas J. Watson Res. Center, 1986.

[7]

H.-C. Chen and D. H. C. Du. Path sensitization in critical path problem. TCAD, 12(2):196--207, 1993.

Digital Library

[8]

A. P. Gupta and D. P. Siewiorek. Automated Multi-Cycle Symbolic Timing Verification of Microprocessor-based Designs. In DAC, pages 113--119, 1994.

Digital Library

[9]

K. Nakamura et al. Waiting false path analysis of sequential logic circuits for performance optimization. In ICCAD, pages 392--395, 1998.

Digital Library

[10]

K. Nakamura et al. Multi-clock path analysis using propositional satisfiability. In ASPDAC, pages 81--86, 2000.

Digital Library

[11]

K. P. Belkhale and A. J. Suess. Timing analysis with known false sub graphs. In ICCAD, pages 736--739, 1995.

Digital Library

[12]

E. Goldberg and A. Saldanha. Timing analysis with implicitly specified false paths. In VLSI Design, pages 518--522, 2000.

Digital Library

[13]

D. Blaauw, R. Panda, and A. Das. Removing user-specified false paths from timing graphs. In DAC, pages 270--273, 2000.

Digital Library

[14]

S. Zhou et al. Efficient static timing analysis using a unified framework for false paths and multi-cycle paths. In ASPDAC, pages 24--27, 2006.

Digital Library

[15]

Altera StratixII Device. {online}http://www.altera.com/products/devices/stratix2/st2-index.jsp

[16]

Altera Quartus II Software. {online}http://www.altera.com/products/software/products/quartus2/qts-index.html

[17]

Xilinx ISE Software. {online}http://www.xilinx.com/ise/logicdesign_prod/foundation.htm

[18]

D. Chen and J. Cong. DAOmap: A Depth-optimal Area Optimization Mapping Algorithm for FPGA Designs. In ICCAD, Nov. 2004.

Digital Library

[19]

J. Lamoureux and S. J. E. Wilton. On the Interaction between Power-Aware CAD Algorithms for FPGAs. In ICCAD, 2003.

Digital Library

[20]

V. Manohararajah, S. D. Brown, and Z. G. Vranesic. Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping. TCAD, 25(11):2331--2340, 2006.

Digital Library

[21]

A. Mishchenko, S. Chatterjee, and R. K. Brayton. Improvements to Technology Mapping for LUT-Based FPGAs. TCAD, 26(2):240--253, 2007.

Digital Library

[22]

P. Ashar, S. Dey, and S. Malik. Exploiting multicycle false paths in the performance optimization of sequential logic circuits. TCAD, 14(9):1067--1075, 1995.

Digital Library

Cited By

Lucas GDong CChen DCheung PWawrzynek J(2010)Variation-aware placement for FPGAs with multi-cycle statistical timing analysisProceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1723112.1723143(177-180)Online publication date: 21-Feb-2010
https://dl.acm.org/doi/10.1145/1723112.1723143
Lucas GDong CChen D(2010)Variation-aware placement with multi-cycle statistical timing analysis for FPGAsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.205641129:11(1818-1822)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/TCAD.2010.2056411

Timing constraint-driven technology mapping for FPGAs considering false paths and multi-clock domains
1. Hardware

Recommendations

Co-synthesis of data paths and clock control paths for minimum-period clock gating
DATE '13: Proceedings of the Conference on Design, Automation and Test in Europe

Although intentional clock skew can be utilized to reduce the clock period, its application in gated clock designs has not been well studied. A gated clock design includes both data paths and clock control paths, but conventional clock skew scheduling ...
Bitstream relocation with local clock domains for partially reconfigurable FPGAs
DATE '09: Proceedings of the Conference on Design, Automation and Test in Europe

Partial Reconfiguration (PR) of FPGAs presents many opportunities for application design flexibility, enabling tasks to dynamically swap in and out of the FPGA without entire system interruption. However, mapping a task to any available PR region (PRR) ...
Clock power reduction for virtex-5 FPGAs
FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays

Clock network power in field-programmable gate arrays (FPGAs) is considered and two complementary approaches for clock power reduction in the Xilinx Virtex-5 FPGA are presented. The approaches are unique in that they leverage specific architectural ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

November 2007

933 pages

ISBN:1424413826

General Chair:
Georges Gielen
ESAT-MICAS, Katholieke Univ. Leuven, Leuven, Belgium

Sponsors

CEDA: Council on Electronic Design Automation
SIGDA: ACM Special Interest Group on Design Automation
IEEE CASS/CANDE
IEEE-CS\DATC: IEEE Computer Society

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

Research-article

Conference

ICCAD07

Sponsor:

CEDA
SIGDA
IEEE-CS\DATC

ICCAD07: The International Conference on Computer-Aided Design 2007

November 5 - 8, 2007

California, San Jose

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
227
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lucas GDong CChen DCheung PWawrzynek J(2010)Variation-aware placement for FPGAs with multi-cycle statistical timing analysisProceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1723112.1723143(177-180)Online publication date: 21-Feb-2010
https://dl.acm.org/doi/10.1145/1723112.1723143
Lucas GDong CChen D(2010)Variation-aware placement with multi-cycle statistical timing analysis for FPGAsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.205641129:11(1818-1822)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/TCAD.2010.2056411

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.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten