article

Free access

Optimal clock period FPGA technology mapping for sequential circuits

Editor:

C. L. Liu Authors:

C. L. LiuAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 3, Issue 3

Pages 437 - 462

https://doi.org/10.1145/293625.293632

Published: 01 July 1998 Publication History

Abstract

We study the technology mapping problem for sequential circuits for look-up table (LUT) based field programmable gate arrays (FPGAs). Existing approaches to the problem simply remove the flip-flops (FFs), then map the remaining combinational logic, and finally put the FFs back. These approaches ignore the sequential nature of a circuit and assume the positions of the FFs are fixed. However, FFs in a sequential circuit can be reposistioned by a functionality-preserving transformation called retiming. As a result, existing approaches can only consider a very small portion of the available solution space. We propose in this paper a novel approach to the technology mapping problem. In our approach, retiming is integrated into the technology mapping process so as to consider the full solution space. We then present a polynomial technology mapping algorithm that, for a given circuit, produces a mapping solution with the minimum clock period among all possible ways of retiming. The effectiveness of the algorithm is also demonstrated experimentally.

References

[1]

ALTERA. 1995. Data Book. Altera, San Jose, CA.

[2]

BHAT, N., AND HILL, D. 1992. Routable technology mapping for FPGAs. In Proceedings of the ACM/SIGDA Workshop on FPGAs, 143-148.

[3]

CONG, g., AND DING, Y. 1993. Beyond the combinational limit in depth minimization for LUT-based FPGA designs. In Proceedings of the Digest IEEE /ACM International Conference on Computer-Aided Design 110-114.

[4]

CONG, g., AND DING, Y. 1994. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. on Computer-Aided Design 13, 1-11.

[5]

CONG, J., AND DING, Y. 1994. On area/depth trade-off in LUT-based FPGA technology mapping. IEEE Trans. on VLSI Systems 2, 137-148.

[6]

CONG, J., AND WU, C. 1996. An improved algorithm for performance optimal technology mapping with retiming in LUT-based FPGA design. In Proceedings of the International Conference on Computer Design, 572-578.

[7]

CONG, J., AND WU, C. 1997. Performance-driven FPGA synthesis with retiming and pipelining for sequential circuits. In Proceedings of the ACM/IEEE Design Automation Conference.

[8]

CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. McGraw-Hill Book Company, New York.

[9]

FARRAHI, A. H., AND SARRAFZADEH, M. 1994. Complexity of the lookup-table minimization problem for FPGA technology mapping. IEEE Trans. on Computer-Aided Design 13, 1319- 1332.

[10]

FRANCIS, R. J., ROSE, J., AND CHUNG, K. 1990. Chortle: A technology mapping for lookup table-based field programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference, 613-619.

[11]

FRANCIS, R. J., ROSE, J., AND VRANESIC, Z. 1991. Chortle-crf: Fast technology mapping for lookup table-based FPGAs. In Proceedings of the ACM/IEEE Design Automation Conference, 227-233.

[12]

FRANCIS, R. J., ROSE, J., AND VRANESIC, Z. 1991. Technology mapping for lookup table-based FPGAs for performance. In Digest of the IEEE /ACM International Conference on Computer- Aided Design, 568-571.

[13]

KARPLUS, K. 1991. Xmap: A technology mapper for table-lookup FPGAs. In Proceedings of the ACM/IEEE Design Automation Conference, 240-243.

[14]

LEISERSON, C. E., AND SAXE, J. B. 1991. Retiming synchronous circuitry. Algorithmica 6, 5-35.

[15]

MATHUR, A., AND LIU, C.L. 1994. Performance driven technology mapping for lookup-table based FPGAs using the general delay model. In Proceedings of the ACM/SIGDA Workshop on Field Programmable Gate Arrays.

[16]

AT&T MICROELECTRONICS. 1995. AT& T Field-Programmable Gate Arrays Data Book. AT&T Microelectronics.

[17]

MURGAI, R., BRAYTON, R., AND SANGIOVANNI-VINCENTELLI, A. 1993. Sequential synthesis for table look up programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference, 224-229.

[18]

MURGAI, R., NISHIZAKI, Y., SHENOY, N., BRAYTON, R., AND SANGIOVANNI-VINCENTELLI, A. 1990. Logic synthesis algorithms for table look up programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference, 620-625.

[19]

MURGAI, R., SHENOY, N., BRAYTON, R., AND SANGIOVANNI-VINCENTELLI, A. 1991. Improved logic synthesis algorithms for table look up architectures. In Digest of the IEEE/ACM International Conference on Computer-Aided Design, 564-567.

[20]

PAN, P. To appear. Continuous retiming: algorithms and applications. In International Conference on Computer Design (ICCD).

[21]

PAN, P., AND LIU, C.L. 1996. Optimal clock period FPGA technology mapping for sequential circuits. In Proceedings of the ACM/IEEE Design Automation Conference (DAC), 720-725.

[22]

PAN, P., AND LIU, C. L. 1996. Technology mapping of sequential circuits for LUT-based FPGAs for performance. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 58-64.

[23]

SAWKAR, P., AND THOMAS, D. 1992. Area and delay mapping for table-look-up based field programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference, 368-373.

[24]

SAWKAR, P., AND THOMAS, D. 1993. Performance directed technology mapping for look-up table based FPGAs. In Proceedings of the ACM/IEEE Design Automation Conference, 208-212.

[25]

SCHLAG, M., KONG, g., AND CHAN, P. 1994. Routability-driven technology mapping for lookup table-based FPGA's. IEEE Trans. on Computer-Aided Design 13, 13-26.

[26]

SENTOVICH, E. M., ET AL. 1992. Sequential circuit design using synthesis and optimization. In Proceedings of the International Conference on Computer Design, 328-333.

[27]

WEINMANN, U., AND ROSENSTIEL, W. 1993. Technology mapping for sequential circuits based on retiming techniques. In Proceedings of the European Design Automation Conference, 318-323.

[28]

Woo, N.-S. 1991. A heuristic method for FPGA technology mapping based on the edge visibility. In Proceedings of the ACM/IEEE Design Automation Conference, 248-251.

[29]

XILINX. 1993. The Programmable Gate Arrays Data Book. Xilinx, San Jose, CA.

[30]

YANG, H., AND WONG, D. F. 1994. Edge-Map: Optimal performance driven technology mapping for iterative LUT based FPGA designs. In Digest of the IEEE/ACM International Conference on Computer-Aided Design, 150-155.

Cited By

Appiah OHayfron-Acquah JAsante M(2019)Real-Time Motion Detection and Surveillance using Approximation of Image Pre-processing Algorithms2019 IEEE AFRICON10.1109/AFRICON46755.2019.9133920(1-8)Online publication date: Sep-2019
https://doi.org/10.1109/AFRICON46755.2019.9133920
Chen DCong JPan P(2018)FPGA Design Automation: A SurveyFoundations and Trends in Electronic Design Automation10.1561/10000000031:3(139-169)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.1561/1000000003
Pan P(2016)Sequential Circuit Technology MappingEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_364(1952-1956)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_364
Show More Cited By

Index Terms

Optimal clock period FPGA technology mapping for sequential circuits
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
    2. Logic synthesis
      1. Circuit optimization
  2. Integrated circuits
    1. Logic circuits
      1. Sequential circuits

Recommendations

Retiming-based factorization for sequential logic optimization

Current sequential optimization techniques apply a variety of logic transformations that mainly target the combinational logic component of the circuit. Retiming is typically applied as a postprocessing step to the gate-level implementation obtained ...
Optimal clock period clustering for sequential circuits with retiming
ICCD '97: Proceedings of the 1997 International Conference on Computer Design (ICCD '97)

We consider the problem of clustering sequential circuits subject to a bound on the area of each cluster, with the objective of minimizing clock period. Current algorithms address combinational circuits only, and treat a sequential circuit as a special ...
Decomposition and technology mapping of speed-independent circuits using Boolean relations
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

Presents a new technique for the decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 3, Issue 3

July 1998

206 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/293625

Editor:
C. L. Liu
Univ. of Illinois at Urbana-Champaign, Urbana

Issue’s Table of Contents

Copyright © 1998 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 July 1998

Published in TODAES Volume 3, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
591
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)4

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Appiah OHayfron-Acquah JAsante M(2019)Real-Time Motion Detection and Surveillance using Approximation of Image Pre-processing Algorithms2019 IEEE AFRICON10.1109/AFRICON46755.2019.9133920(1-8)Online publication date: Sep-2019
Chen DCong JPan P(2018)FPGA Design Automation: A SurveyFoundations and Trends in Electronic Design Automation10.1561/10000000031:3(139-169)Online publication date: 13-Dec-2018
Pan P(2016)Sequential Circuit Technology MappingEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_364(1952-1956)Online publication date: 22-Apr-2016
Pan P(2014)Sequential Circuit Technology MappingEncyclopedia of Algorithms10.1007/978-3-642-27848-8_364-2(1-5)Online publication date: 30-Dec-2014
Dong XLemieux G(2009)PGR: Period and glitch reduction via clock skew scheduling, delay padding and GlitchLess2009 International Conference on Field-Programmable Technology10.1109/FPT.2009.5377666(88-95)Online publication date: Dec-2009
Cong JPan P(2008)Technology MappingReconfigurable Computing10.1016/B978-012370522-8.50019-4(277-296)Online publication date: 2008
Pan P(2008)Sequential Circuit Technology MappingEncyclopedia of Algorithms10.1007/978-0-387-30162-4_364(820-824)Online publication date: 2008
Hauck SDeHon A(2007)Reconfigurable ComputingundefinedOnline publication date: 2-Nov-2007
Hämäläinen TKuusilinna KSaarinen JLahtinen V(2001)Finite state machine encoding for VHDL synthesisIEE Proceedings - Computers and Digital Techniques10.1049/ip-cdt:20010210148:1(23-30)Online publication date: 1-Jan-2001
Pan P(1999)Performance-driven integration of retiming and resynthesisProceedings of the 36th annual ACM/IEEE Design Automation Conference10.1145/309847.309921(243-246)Online publication date: 1-Jun-1999
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents