More Web Proxy on the site http://driver.im/

research-article

Advanced Functional Decomposition Using Majority and Its Applications

Authors:

Mathias Soeken,

Giovanni De MicheliAuthors Info & Claims

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 39, Issue 8

Pages 1621 - 1634

https://doi.org/10.1109/TCAD.2019.2925392

Published: 01 August 2020 Publication History

Abstract

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and the 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such a decomposition can extend the capabilities of current logic decompositions, but only found limited attention in the previous work. Our algorithm make use of a decomposition rule based on MAJ. Combined with disjoint-support decomposition, the algorithm can factorize XOR-majority graphs (XMGs), a recently proposed data structure which has XOR, MAJ, and inverters as only logic primitives. XMGs have been applied in various applications, including: 1) exact-synthesis-aware rewriting; 2) preoptimization for 6-input look-up table (6-LUT) mapping; and 3) synthesis of quantum circuits. An experimental evaluation shows that our algorithm leads to better XMGs compared to state-of-the-art algorithms based on XMGs, which positively affects all of these three applications. As one example, our experiments show that the proposed method achieves an average of 10% and 26% reduction on the LUTs size/depth product applied to the EPFL arithmetic and random control benchmarks after technology mapping, respectively.

References

[1]

M. M. Waldrop, “The chips are down for Moore’s law,” Nat. News, vol. 530, no. 7589, pp. 144–147, 2016.

[2]

L. Amarú, P.-E. Gaillardon, S. Mitra, and G. De Micheli, “New logic synthesis as nanotechnology enabler,” Proc. IEEE, vol. 103, no. 11, pp. 2168–2195, Nov. 2015.

[3]

L. Amarú, P.-E. Gaillardon, and G. De Micheli, “BDS-MAJ: A BDD-based logic synthesis tool exploiting majority logic decomposition,” in Proc. DAC, 2013, pp. 1–6.

[4]

I. Amlani, A. O. Orlov, G. Toth, G. H. Bernstein, C. S. Lent, and G. L. Snider, “Digital logic gate using quantum-dot cellular automata,” Science, vol. 284, no. 5412, pp. 289–291, 1999.

[5]

T. Schneider, A. A. Serga, B. Leven, B. Hillebrands, R. L. Stamps, and M. P. Kostylev, “Realization of spin-wave logic gates,” Appl. Phys. Lett., vol. 92, no. 2, 2008, Art. no.

[6]

A. Imre, G. Csaba, L. Ji, A. Orlov, G. H. Bernstein, and W. Porod, “Majority logic gate for magnetic quantum-dot cellular automata,” Science, vol. 311, no. 5758, pp. 205–208, 2006.

[7]

M. Soeken, M. Roetteler, N. Wiebe, and G. De Micheli, “Design automation and design space exploration for quantum computers,” in Proc. DATE, 2017, pp. 470–475.

[8]

C.-C. Tsai and M. Marek-Sadowska, “Multilevel logic synthesis for arithmetic functions,” in Proc. DAC, 1996, pp. 242–247.

[9]

L. Amarù, P.-E. Gaillardon, and G. De Micheli, “Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization,” in Proc. DAC, 2014, pp. 1–6.

[10]

A. Mishchenko, S. Chatterjee, and R. Brayton, “DAG-aware AIG rewriting: A fresh look at combinational logic synthesis,” in Proc. DAC, 2006, pp. 532–535.

[11]

L. G. Amarù, P.-E. Gaillardon, and G. De Micheli, “Majority-inverter graph: A new paradigm for logic optimization,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 35, no. 5, pp. 806–819, May 2016.

Digital Library

[12]

W. Haaswijk, M. Soeken, L. Amarù, P.-E. Gaillardon, and G. De Micheli, “A novel basis for logic rewriting,” in Proc. ASPDAC, 2017, pp. 151–156.

[13]

E. A. Ernst, “Optimal combinational multi-level logic synthesis,” Ph.D. dissertation, Dept. Comput. Sci. Eng., Univ. Michigan, Ann Arbor, MI, USA, 2009.

[14]

N. Li and E. Dubrova, “AIG rewriting using 5-input cuts,” in Proc. ICCD, 2011, pp. 429–430.

[15]

W. J. Haaswijk, M. Soeken, L. Amaru, P.-E. Gaillardon, and G. De Micheli, “LUT mapping and optimization for majority-inverter graphs,” in Proc. IWLS, 2016, pp. 1–8.

[16]

M. Soeken, L. G. Amarù, P.-E. Gaillardon, and G. De Micheli, “Optimizing majority-inverter graphs with functional hashing,” in Proc. DATE, 2016, pp. 1030–1035.

[17]

M. Soeken, G. De Micheli, and A. Mishchenko, “Busy man’s synthesis: Combinational delay optimization with SAT,” in Proc. DATE, 2017, pp. 830–835.

[18]

W. J. Haaswijk, A. Mischenko, M. Soeken, and G. De Micheli, “SAT based exact synthesis using DAG topology families,” in Proc. DAC, 2018, Art. no.

[19]

V. N. Kravets and K. A. Sakallah, “Constructive library-aware synthesis using symmetries,” in Proc. DATE, 2000, pp. 208–215.

[20]

Z. Chu, M. Soeken, Y. Xia, and G. De Micheli, “Functional decomposition using majority,” in Proc. ASPDAC, 2018, pp. 676–681.

[21]

V. Bertacco and M. Damiani, “The disjunctive decomposition of logic functions,” in Proc. ICCAD, 1997, pp. 78–82.

[22]

R. L. Ashenhurst, The Decomposition of Switching Functions, vol. 29, Comput. Lab, Harvard Univ., Cambridge, MA, USA, pp. 74–116, 1959.

[23]

H. A. Curtis, A New Approach to the Design of Switching Circuits. New York, NY, USA: van Nostrand, 1962.

[24]

R. M. Karp, “Functional decomposition and switching circuit design,” J. Soc. Ind. Appl. Math., vol. 11, no. 2, pp. 291–335, 1963.

[25]

A. Mishchenko, “Enumeration of irredundant circuit structures,” in Proc. IWLS, 2014, pp. 1–7.

[26]

A. Mishchenko, R. K. Brayton, and S. Chatterjee, “Boolean factoring and decomposition of logic networks,” in Proc. ICCAD, 2008, pp. 38–44.

[27]

A. Mishchenko, S. Cho, S. Chatterjee, and R. K. Brayton, “Combinational and sequential mapping with priority cuts,” in Proc. ICCAD, 2007, pp. 354–361.

[28]

A. Mishchenko, S. Chatterjee, and R. K. Brayton, “Improvements to technology mapping for LUT-based FPGAs,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 26, no. 2, pp. 240–253, Feb. 2007.

Digital Library

[29]

V. Bertacco, S. Minato, P. Verplaetse, L. Benini, and G. De Micheli, “Decision diagrams and pass transistor logic synthesis,” in Proc. IWLS, 1997, pp. 1–12.

[30]

C. Yang and M. Ciesielski, “BDS: A BDD-based logic optimization system,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 21, no. 7, pp. 866–876, Jul. 2002.

Digital Library

[31]

S.-I. Minato and G. De Micheli, “Finding all simple disjunctive decompositions using irredundant sum-of-products forms,” in Proc. ICCAD, 1998, pp. 111–117.

[32]

A. Mishchenko and R. Brayton, “Faster logic manipulation for large designs,” in Proc. IWLS, 2013, pp. 1–6.

[33]

V. Callegaro, F. S. Marranghello, M. G. A. Martins, R. P. Ribas, and A. I. Reis, “Bottom-up disjoint-support decomposition based on cofactor and Boolean difference analysis,” in Proc. ICCD, 2015, pp. 680–687.

[34]

Y. Tohma, “Decompositions of logical functions using majority decision elements,” IEEE Trans. Electron. Comput., vol. EC-13, no. 6, pp. 698–705, Dec. 1964.

[35]

S. B. Akers, “Synthesis of combinational logic using three-input majority gates,” in Proc. 3rd Annu. Symp. Switch. Circuit Theory Logical Design, 1962, pp. 149–158.

[36]

V. N. Kravets and K. A. Sakallah, “Resynthesis of multi-level circuits under tight constraints using symbolic optimization,” in Proc. ICCAD, 2002, pp. 687–693.

[37]

M. Soeken, P. Raiola, B. Sterin, B. Becker, G. De Micheli, and M. Sauer, “SAT-based combinational and sequential dependency computation,” in Proc. Haifa Verification Conf., 2016, pp. 1–17.

[38]

S. R. Das, P. K. Srimani, and C. R. Datta, “On multiple fault analysis in combinational circuits by means of Boolean difference,” Proc. IEEE, vol. 64, no. 9, pp. 1447–1449, Sep. 1976.

[39]

R. A. Smith, “Minimal three-variable NOR and NAND logic circuits,” IEEE Trans. Electron. Comput., vol. EC-14, no. 1, pp. 79–81, Feb. 1965.

[40]

R. Brayton and A. Mishchenko, “ABC: An academic industrial-strength verification tool,” in Proc. CAV, 2010, pp. 24–40.

[41]

M. Soeken, L. G. Amaru, P.-E. Gaillardon, and G. De Micheli, “Exact synthesis of majority-inverter graphs and its applications,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 36, no. 11, pp. 1842–1855, Nov. 2017.

[42]

A. Kojevnikov, A. S. Kulikov, and G. Yaroslavtsev, “Finding efficient circuits using SAT-solvers,” in Proc. Int. Conf. Theory Appl. Satisfiability Test. (SAT), 2009, pp. 32–44.

[43]

N. Eén, “Practical SAT—A tutorial on applied satisfiability solving,” in Proc. Formal Methods Comput.-Aided Design (FMCAD), 2007.

[44]

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 6: Satisfiability. Boston, MA, USA: Addison-Wesley, 2015.

Digital Library

[45]

E. Goto and H. Takahasi, “Some theorems useful in threshold logic for enumerating Boolean functions,” in Proc. Int. Feder. Inf. Process. Congr., 1962, pp. 747–752.

[46]

W. Haaswijk, E. Testa, M. Soeken, and G. De Micheli, “Classifying functions with exact synthesis,” in Proc. ISMVL, 2017, pp. 272–277.

[47]

G. D. Micheli, Synthesis and Optimization of Digital Circuits. New Delhi, India: McGraw-Hill Higher Educ., 1994.

Digital Library

[48]

K. L. Kodandapani and S. C. Seth, “On combinational networks with restricted fan-out,” IEEE Trans. Comput., vol. C-27, no. 4, pp. 309–318, Apr. 1978.

Digital Library

[49]

A. Mishchenko, “An approach to disjoint-support decomposition of logic functions,” Dept. Elect. Comput. Eng., Portland State Univ., Portland, OR, USA, Rep., 2001. [Online]. Available: https://people.eecs.berkeley.edu/~alanmi/publications/2001/tech01_dsd.pdf

[50]

G. Liu and Z. Zhang, “A parallelized iterative improvement approach to area optimization for LUT-based technology mapping,” in Proc. FPGA, 2017, pp. 147–156.

[51]

S. Bravyi and A. Kitaev, “Universal quantum computation with ideal Clifford gates and noisy ancillas,” Phys. Rev. A, vol. 71, no. 2, 2005, Art. no.

Cited By

Pan HXia YWang LChu Z(2024)Semi-Tensor Product-Based Exact Synthesis for Logic RewritingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333727943:4(1093-1106)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TCAD.2023.3337279
Mishra ROkade MMahapatraRuby K(2023)Novel Substitution Box Architectural Synthesis for Lightweight Block CiphersIEEE Embedded Systems Letters10.1109/LES.2023.324929116:2(90-93)Online publication date: 27-Feb-2023
https://dl.acm.org/doi/10.1109/LES.2023.3249291
Tian HChu Z(2021)Inversion Optimization Strategy Based on Primitives with Complement AttributesJournal of Computer Science and Technology10.1007/s11390-021-0898-736:5(1145-1154)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s11390-021-0898-7
Show More Cited By

Index Terms

Advanced Functional Decomposition Using Majority and Its Applications
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

Index terms have been assigned to the content through auto-classification.

Recommendations

Functional decomposition using majority
ASPDAC '18: Proceedings of the 23rd Asia and South Pacific Design Automation Conference

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and a 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such ...
Functional decomposition using majority
2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC)
Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and a 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such ...
Fast Fourier transform using matrix decomposition

To reduce both the multiplicative complexity and total number of operations, this paper introduces a modeling scheme of the fast Fourier transform (FFT) to decompose the discrete Fourier transform (DFT) matrix recursively into a set of sparse matrices. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Volume 39, Issue 8

Aug. 2020

200 pages

ISSN:0278-0070

Issue’s Table of Contents

0278-0070 © 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Press

Publication History

Published: 01 August 2020

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pan HXia YWang LChu Z(2024)Semi-Tensor Product-Based Exact Synthesis for Logic RewritingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333727943:4(1093-1106)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TCAD.2023.3337279
Mishra ROkade MMahapatraRuby K(2023)Novel Substitution Box Architectural Synthesis for Lightweight Block CiphersIEEE Embedded Systems Letters10.1109/LES.2023.324929116:2(90-93)Online publication date: 27-Feb-2023
https://dl.acm.org/doi/10.1109/LES.2023.3249291
Tian HChu Z(2021)Inversion Optimization Strategy Based on Primitives with Complement AttributesJournal of Computer Science and Technology10.1007/s11390-021-0898-736:5(1145-1154)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s11390-021-0898-7
Chu ZShi LWang LXia Y(2019)Multi-objective algebraic rewriting in XOR-majority graphsIntegration, the VLSI Journal10.1016/j.vlsi.2019.08.00569:C(40-49)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1016/j.vlsi.2019.08.005

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents