skip to main content
10.1145/275107.275116acmconferencesArticle/Chapter ViewAbstractPublication PagesfpgaConference Proceedingsconference-collections
Article
Free access

Boolean matching for complex PLBs in LUT-based FPGAs with application to architecture evaluation

Published: 01 March 1998 Publication History

Abstract

In this paper, we developed Boolean matching techniques for complex programmable logic blocks (PLBs) in LUT-based FPGAs. A complex PLB can not only be used as a K-input LUT, but also can implement some wide functions of more than K variables. We apply previous and develop new functional decomposition methods to match wide functions to PLBs. We can determine exactly whether a given wide function can be implemented with a XC4000 CLB or other three PLB architectures (including the XC5200 CLB). We evaluate functional capabilities of the four PLB architectures on implementing wide functions in MCNC benchmarks. Experiments show that the XC4000 CLB can be used to implement up to 98% of 6-cuts and 88% of 7-cuts in MCNC benchmarks, while two of the other three PLB architectures have a smaller cost in terms of logic capability per silicon area. Our results are useful for designing future logic unit architectures in LUT based FPGAs.

References

[1]
Ashenhurst, R. L., "The Decomposition of Switching Functions," Proc. Int'l Syrup. on Theory of Switching Functions, 1959.
[2]
Bryant, R. E., "Graph-based Algorithms for Boolean Function Manipulation," IEEE Trans. on Computers, Vol. C-35, pp. 677-691, Aug. 1986.
[3]
Chang, S.-C. and M. Marek-Sadowska, "Technology Mapping via Transformations of Function Graphs," Proc. IEEE Int'l Conf. on Computer Design, pp. 159-162, Oct. 1992.
[4]
Cong, J. and Y. Ding, "Combinational Logic Synthesis for LUT Based Field Programmable Gate Arrays," A CM Trans. on Design Automation of Electronic Systems, Vol. 1, 2, pp. 145-204, 1996.
[5]
Cong, J. and Y.-Y. Hwang, "Partially-Dependent Functional Decomposition with Applications in FPGA Synthesis and Mapping," Proc. A CM 5th Int'l Syrup. on FPGA, pp. 35-42, Feb. 1997.
[6]
Cong, J., J. Peck, and Y. Ding, "RASP: A General Logic Synthesis System for SRAM-based FPGAs," Proc. ACM 4th Int'l Syrup. on FPGA, Feb. 1996.
[7]
Curtis, H. A., ';A Generalized Tree Circuit," Journal Of the ACM, Vol. 8(4) pp. 484-496, 1961.
[8]
Huang, J.-D., J.-Y. Jou, and W.-Z. Shen, "Compatible Class Encoding in Roth-Karp Decomposition for Two-Output LIlT Architecture," Proc. IEEE Int'l Conf. on Computer-Aided Design, pp. 359-363, Nov. 1995.
[9]
Lai, Y.-T., K.-R. R. Pan, and M. Pedram, "FPGA Synthesis using Function Decomposition," Proc. Int'l Conf. on Computer Design: VLSI in Computers, pp. 30-35, Oct. 1994.
[10]
Legl, C., B. Wurth, and K. Eckl, "An Implicit Algorithm for Support Minimization during Functional Decomposition," Proc. European Design and Test Conf., March 1996.
[11]
Rudell, R., Private Communication 1996.
[12]
Sasao, T. and J. T. Butler, "On Bi-Decompositions of Logic Functions," Proc. Int'l Workshop on Logic Synthesis, 1997.
[13]
Wurth, B., K. Eckl, and K. Antreich, "Functional Multiple-Output Decomposition: Theory and an implicit Algorithm," Proc. A CM/IEEE Design Automation Conf., pp. 54--59, Jun. 1995.

Cited By

View all
  • (2016)Accelerating SAT-Based Boolean Matching for Heterogeneous FPGAs Using One-Hot Encoding and CEGAR TechniqueIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E99.A.1374E99.A:7(1374-1380)Online publication date: 2016
  • (2015)Accelerating SAT-based Boolean matching for heterogeneous FPGAs using one-hot encoding and CEGAR techniqueThe 20th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2015.7059014(255-260)Online publication date: Jan-2015
  • (2014)From design to design automationProceedings of the 2014 on International symposium on physical design10.1145/2560519.2568052(121-126)Online publication date: 30-Mar-2014
  • Show More Cited By

Index Terms

  1. Boolean matching for complex PLBs in LUT-based FPGAs with application to architecture evaluation

          Recommendations

          Comments

          Information & Contributors

          Information

          Published In

          cover image ACM Conferences
          FPGA '98: Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays
          March 1998
          262 pages
          ISBN:0897919785
          DOI:10.1145/275107
          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: 01 March 1998

          Permissions

          Request permissions for this article.

          Check for updates

          Qualifiers

          • Article

          Conference

          FPGA98
          Sponsor:
          FPGA98: 1998 International Symposium on Field Programmable Gate Arrays
          February 22 - 25, 1998
          California, Monterey, USA

          Acceptance Rates

          Overall Acceptance Rate 125 of 627 submissions, 20%

          Upcoming Conference

          FPGA '25

          Contributors

          Other Metrics

          Bibliometrics & Citations

          Bibliometrics

          Article Metrics

          • Downloads (Last 12 months)51
          • Downloads (Last 6 weeks)12
          Reflects downloads up to 17 Jan 2025

          Other Metrics

          Citations

          Cited By

          View all
          • (2016)Accelerating SAT-Based Boolean Matching for Heterogeneous FPGAs Using One-Hot Encoding and CEGAR TechniqueIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E99.A.1374E99.A:7(1374-1380)Online publication date: 2016
          • (2015)Accelerating SAT-based Boolean matching for heterogeneous FPGAs using one-hot encoding and CEGAR techniqueThe 20th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2015.7059014(255-260)Online publication date: Jan-2015
          • (2014)From design to design automationProceedings of the 2014 on International symposium on physical design10.1145/2560519.2568052(121-126)Online publication date: 30-Mar-2014
          • (2008)Scalable Synthesis and Clustering Techniques Using Decision DiagramsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.91554527:3(423-435)Online publication date: 1-Mar-2008
          • (2006)Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mappingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.94530320:9(1077-1090)Online publication date: 1-Nov-2006
          • (2004)Efficient Realization of Parity Prediction Functions in FPGAsJournal of Electronic Testing: Theory and Applications10.1023/B:JETT.0000042513.15382.e720:5(489-499)Online publication date: 1-Oct-2004
          • (2003)A novel technology mapping method for AND/XOR expressions33rd International Symposium on Multiple-Valued Logic, 2003. Proceedings.10.1109/ISMVL.2003.1201397(133-138)Online publication date: 2003
          • (2003)A new partitioning method for LUT-based FPGASCCECE 2003 - Canadian Conference on Electrical and Computer Engineering. Toward a Caring and Humane Technology (Cat. No.03CH37436)10.1109/CCECE.2003.1226354(103-106)Online publication date: 2003
          • (2002)Interconnect enhancements for a high-speed PLD architectureProceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays10.1145/503048.503050(3-10)Online publication date: 24-Feb-2002
          • (2002)Efficient Decomposition Techniques for FPGAsHigh Performance Computing — HiPC 200210.1007/3-540-36265-7_59(630-639)Online publication date: 18-Dec-2002
          • Show More Cited By

          View Options

          View options

          PDF

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader

          Login options

          Media

          Figures

          Other

          Tables

          Share

          Share

          Share this Publication link

          Share on social media