article

Technology mapping and architecture evalution for k/m-macrocell-based FPGAs

Authors:

Xin YuanAuthors Info & Claims

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

Pages 3 - 23

https://doi.org/10.1145/1044111.1044113

Published: 01 January 2005 Publication History

Abstract

In this article, we study the technology mapping problem for a novel field-programmable gate array (FPGA) architecture that is based on k-input single-output programmable logic array- (PLA-) like cells, or, k/m-macrocells. Each cell in this architecture can implement a single output function of up to k inputs and up to m product terms. We develop a very efficient technology mapping algorithm, k_m_flow, for this new type of architecture. The experimental results show that our algorithm can achieve depth-optimality on almost all the testcases in a set of 16 Microelectronics Center of North Carolina (MCNC) benchmarks. Furthermore it is shown that on this set of benchmarks, with only a relatively small number of product terms (m ≤ k + 3), the k/m-macrocell-based FPGAs can achieve the same or similar mapping depth compared with the traditional k-input single-output lookup table- (k-LUT-) based FPGAs. We also investigate the total area and delay of k/m-macrocell-based FPGAs and compare them with those of the commonly used 4-LUT-based FPGAs. The experimental results show that k/m-macrocell-based FPGAs can outperform 4-LUT-based FPGAs in terms of both delay and area after placement and routing by VPR on this set of benchmarks.

References

[1]

Altera Corp. 2000. MAX 700B, Programmable Logic Device Family. San Jose, CA. Web site: www.altera.com.

[2]

Altera Corp. 2001. APEX II, Programmable Logic Device Family. San Jose, CA. Web site: www. altera.com.

[3]

Anderson, J. H. and Brown, S. D. 1998. Technology mapping for large complex PLDs. In Proceedings of the Design Automation Conference. 698--703.

[4]

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

[5]

Brayton, R., Sangiovanni-Vincentelli, A., Hachtel, G., and McMullin, C. 1984. Logic Minimization Algorithms for Digital Circuits. Kluwer, Norwell, MA.

[6]

Cong, J., Chen, D., Ercegovac, M., and Huang, Z. 2001. Performance-driven mapping for CPLA architecture. In Proceedings of the ACM International Symposium on FPGA. 39--47.

[7]

Cong, J. and Ding, Y. 1994. An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 13, 1, 1--12.

Digital Library

[8]

Cong, J. and Ding, Y. 1996. Combinational logic synthesis for LUT based field programmable gate arrays. ACM Trans. Des. Automat. Electron. Syst. 1, 2, 145--204.

Digital Library

[9]

Cong, J., Huang, H., and Yuan, X. 2000. Technology mapping for k/m-macrocell based FPGAs. In Proceedings of the ACM International Symposium on FPGA. 51--59.

[10]

Cong, J. and Hwang, Y. 1996. Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA. In Proceedings of the Design Automation Conf. 726--729.

[11]

Cong, J., Peck, J., and Ding, Y. 1996. RASP: A general logic synthesis system for SRAM-based FPGAs. In Proceedings of the ACM International Symposium on FPGA. 137--143.

[12]

Cong, J., Wu, C., and Ding, Y. 1999. Cut ranking and pruning: Enabling a general and efficient FPGA mapping solution. In Proceedings of the ACM International Symposium on FPGA. 29--35.

[13]

Cypress Semiconductor Corp. 2000. The Cypress Data Book. San Jose, CA. Web site: www. cypress.com.

[14]

Francis, R. J., Rose, J., and Vranesic, Z. G. 1991a. Chortle-CRF: Fast technology mapping for lookup table-based FPGAs. In Proceedings of the Design Automation Conference. 227--233.

[15]

Francis, R. J., Rose, J., and Vranesic, Z. G. 1991b. Technology mapping of lookup table-based FPGAs for performance. In Proceedings of the International Conference on Computer Aided Design. 568--571.

[16]

Hasan, Z., Harrison, D., and Ciesielski, M. 1992. A fast partition method for PLA-based FPGAs. IEEE Des. Test Comput. 9, 4, 34--39.

[17]

Kaviani, A. and Brown, S. 1999. The hybrid field-programmable architecture. IEEE Des. Test Comput. 16, 74--83.

[18]

Kaviani, A. S. 1999. Novel architecture and synthesis methods for high capacity field programmable devices. Ph.D. dissertation. University of Toronto, Toronto, Ont., Canada.

[19]

Kouloheris, J. L. 1993. Empirical study of the effect of cell granularity on FPGA density and performance. Ph.D. dissertation. Stanford University, Stanford, CA.

[20]

Kouloheris, J. L. and Gamal, A. E. 1992. PLA-based FPGA area versus cell granularity. In Proceedings of the IEEE Custom Integrated Circuits Conference. 4.3/1--4.

[21]

Krishnamoorthy, S. and Tessier, R. May 2003. Technology mapping algorithms for hybrid FPGAs containing lookup tables and PLAs. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 22, 5, 545--559.

Digital Library

[22]

Lattice Semiconductor Corp. 2000. The Lattice Data Book. Hillsboro, OR. Web site: www. latticesemi.com.

[23]

Rose, J., Francis, R. J., Lewis, D., and Chow, P. Ct. 1990. Architecture of field programmable gate arrays: The effect of logic block functionality on area efficiency. IEEE J. Solid State Circ. 25, 5, 1217--1225.

[24]

Xilinx Inc. 2001. Virtex-II Field-Programmable Gate Arrays. San Jose, CA. Web site: www.xilinx. com.

Cited By

Eslami FWilton S(2018)Rapid Triggering Capability Using an Adaptive Overlay during FPGA DebugACM Transactions on Design Automation of Electronic Systems10.1145/324104523:6(1-25)Online publication date: 6-Dec-2018
https://dl.acm.org/doi/10.1145/3241045
Luo TLiang HZhang WHe BMaskell D(2017)A Hybrid Logic Block Architecture in FPGA for Holistic EfficiencyIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2016.255155564:1(71-75)Online publication date: Jan-2017
https://doi.org/10.1109/TCSII.2016.2551555
Ebrahimi ZKhaleghi BAsadi H(2017)PEAFIEEE Transactions on Computers10.1109/TC.2016.263614166:6(982-995)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TC.2016.2636141
Show More Cited By

Index Terms

Technology mapping and architecture evalution for k/m-macrocell-based FPGAs
1. Hardware
  1. Integrated circuits
    1. Logic circuits
  2. Very large scale integration design
    1. Application-specific VLSI designs

Recommendations

Technology Mapping into General Programmable Cells
FPGA '15: Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Field-Programmable Gate Arrays (FPGA) implement logic functions using programmable cells, such as K-input lookup-tables (K-LUTs). A K-LUT can implement any Boolean function with K inputs and one output. Methods for mapping into K-LUTs are extensively ...
Improvements to technology mapping for LUT-based FPGAs
FPGA '06: Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays

The paper presents several improvements to state-of-the-art in FPGA technology mapping exemplified by a recent advanced technology mapper DAOmap [Chen and Cong, ICCAD '04]. Improved cut enumeration computes all K-feasible cuts without pruning for up to ...
Dual-output LUT merging during FPGA technology mapping
ICCAD '20: Proceedings of the 39th International Conference on Computer-Aided Design

Modern commercial Field-Programmable Gate Array (FPGA) architectures support dual-output look-up tables (LUTs). If the number of total inputs in two small LUTs do not exceed the constraint, e.g., 5 in Xilinx UltraScale+ series, we can pack them into one ...

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 10, Issue 1

January 2005

186 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1044111

Issue’s Table of Contents

Copyright © 2005 ACM.

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

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 January 2005

Published in TODAES Volume 10, Issue 1

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

21
Total Citations
View Citations
604
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Eslami FWilton S(2018)Rapid Triggering Capability Using an Adaptive Overlay during FPGA DebugACM Transactions on Design Automation of Electronic Systems10.1145/324104523:6(1-25)Online publication date: 6-Dec-2018
https://dl.acm.org/doi/10.1145/3241045
Luo TLiang HZhang WHe BMaskell D(2017)A Hybrid Logic Block Architecture in FPGA for Holistic EfficiencyIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2016.255155564:1(71-75)Online publication date: Jan-2017
https://doi.org/10.1109/TCSII.2016.2551555
Ebrahimi ZKhaleghi BAsadi H(2017)PEAFIEEE Transactions on Computers10.1109/TC.2016.263614166:6(982-995)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TC.2016.2636141
Chin SLuu JHuda SAnderson J(2016)Hybrid LUT/Multiplexer FPGA Logic ArchitecturesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2015.245165824:4(1280-1292)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1109/TVLSI.2015.2451658
Perera DLi K(2013)Analysis of single-chip hardware support for mobile and embedded applications2013 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)10.1109/PACRIM.2013.6625505(369-376)Online publication date: Aug-2013
https://doi.org/10.1109/PACRIM.2013.6625505
Chin SAnderson J(2013)A case for hardened multiplexers in FPGAs2013 International Conference on Field-Programmable Technology (FPT)10.1109/FPT.2013.6718328(42-49)Online publication date: Dec-2013
https://doi.org/10.1109/FPT.2013.6718328
Purnaprajna MIenne P(2013)A Case for Heterogeneous Technology-MappingProceedings of the 2013 IEEE 21st Annual International Symposium on Field-Programmable Custom Computing Machines10.1109/FCCM.2013.19(53-56)Online publication date: 28-Apr-2013
https://dl.acm.org/doi/10.1109/FCCM.2013.19
Parandeh-Afshar HBenbihi HNovo DIenne PCompton KHutchings B(2012)Rethinking FPGAsProceedings of the ACM/SIGDA international symposium on Field Programmable Gate Arrays10.1145/2145694.2145715(119-128)Online publication date: 22-Feb-2012
https://dl.acm.org/doi/10.1145/2145694.2145715
Po-Yang Hsu Ping-Chuan Lu Yi-Yu Liu (2010)An efficient hybrid LUT/SOP reconfigurable architectureProceedings of 2010 International Symposium on VLSI Design, Automation and Test10.1109/VDAT.2010.5496718(173-176)Online publication date: Apr-2010
https://doi.org/10.1109/VDAT.2010.5496718
Parandeh-Afshar HVerma ABrisk PIenne P(2010)Improving FPGA performance for carry-save arithmeticIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2009.201438018:4(578-590)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1109/TVLSI.2009.2014380
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents