A Survey of Majority Logic Designs in Emerging Nanotechnologies for Computing
Authors: 
Tingting Zhang, Honglan Jiang, Weiqiang Liu, Fabrizio Lombardi, Leibo Liu, Seok-Bum Ko, Jie HanAuthors Info & Claims
Pages 732 - 739
Abstract
As Moore's law is coming to an end, research on technologies alternative to the complementary metal-oxide semiconductor (CMOS) has been extensively pursued over the last few decades. Many emerging nanotechnologies assemble circuits based on majority logic. It is generally known that majority logic is more expressive and hardware efficient than Boolean logic, however majority logic presents unique challenges at many levels such as arithmetic design and synthesis. With the rediscovery of majority logic as a computational primitive in the post-CMOS era, this article briefly reviews recent studies from various perspectives to highlight accomplishments and open problems across many domains of majority logic design.
References
[1]
R. H. Dennard, J. Cai, and A. Kumar, “A perspective on today's scaling challenges and possible future directions,” in Handbook of Thin Film Deposition. New York, NY, USA: Elsevier, 2018, pp. 3–18.
[2]
B. Parhami, D. Abedi, and G. Jaberipur, “Majority-logic, its applications, and atomic-scale embodiments,” Comput. Elect. Eng., vol. 83, 2020, Art. no.
[3]
A. Imre, G. Csaba, L. Ji, A. Orlov, G. Bernstein, and W. Porod, “Majority logic gate for magnetic quantum-dot cellular automata,” Science, vol. 311, no. 5758, pp. 205–208, 2006.
[4]
M. Vacca, M. Graziano, and M. Zamboni, “Majority voter full characterization for nanomagnet logic circuits,” IEEE Trans. Nanotechnol., vol. 11, no. 5, pp. 940–947, Sep. 2012.
[5]
A. Mahmoud et al., “Introduction to spin wave computing,” J. Appl. Phys., vol. 128, no. 16, 2020, Art. no.
[6]
R. Zhang, K. Walus, W. Wang, and G. A. Jullien, “A method of majority logic reduction for quantum cellular automata,” IEEE Trans. Nanotechnol., vol. 3, no. 4, pp. 443–450, Dec. 2004.
[7]
M. R. Azghadi, O. Kavehie, and K. Navi, “A novel design for quantum-dot cellular automata cells and full adders,” J. Appl. Sci., vol. 7, no. 22, pp. 3460–3468, 2007.
[8]
V. Jamshidi, “A VLSI majority-logic device based on spin transfer torque mechanism for brain-inspired computing architecture,” IEEE Trans. Very Large Scale Integration, vol. 28, no. 8, pp. 1858–1866, Aug. 2020.
[9]
S. Dutta et al., “Proposal for nanoscale cascaded plasmonic majority gates for non-Boolean computation,” Sci. Rep., vol. 7, no. 1, 2017, Art. no.
[10]
J. Reuben, “Binary addition in resistance switching memory array by sensing majority,” Micromachines, vol. 11, no. 5, 2020, Art. no.
[11]
V. Pudi and K. Sridharan, “Low complexity design of ripple carry and brent-kung adders in QCA,” IEEE Trans. Nanotechnol., vol. 11, no. 1, pp. 105–119, Jan. 2012.
[12]
K. Walus, T. J. Dysart, G. A. Jullien, and R. A. Budiman, “QCADesigner: A rapid design and simulation tool for quantum-dot cellular automata,” IEEE Trans. Nanotechnol., vol. 3, no. 1, pp. 26–31, Mar. 2004.
[13]
G. Csaba, A. Imre, G. H. Bernstein, W. Porod, and V. Metlushko, “Nanocomputing by field-coupled nanomagnets,” IEEE Trans. Nanotechnol., vol. 1, no. 4, pp. 209–213, Dec. 2002.
[14]
M. T. Alam, M. J. Siddiq, G. H. Bernstein, M. Niemier, W. Porod, and X. S. Hu, “On-chip clocking for nanomagnet logic devices,” IEEE Trans. Nanotechnol., vol. 9, no. 3, pp. 348–351, May 2010.
[15]
O. Zografos et al., “Design and benchmarking of hybrid CMOS-spin wave device circuits compared to 10 nm CMOS,” in Proc. IEEE 15th Int. Conf. Nanotechnol., 2015, pp. 686–689.
[16]
M. G. Mankalale and S. S. Sapatnekar, “Optimized standard cells for all-spin logic,” ACM J. Emerg. Technol. Comput. Syst., vol. 13, no. 2, pp. 1–22, 2016.
[17]
J. Reuben, D. Fey, and C. Wenger, “A modeling methodology for resistive RAM based on stanford-pku model with extended multilevel capability,” IEEE Trans. Nanotechnol., vol. 18, pp. 647–656, 2019.
[18]
J. Reuben, “Rediscovering majority logic in the post-CMOS era: A perspective from in-memory computing,” J. Low Power Electron. Appl., vol. 10, no. 3, 2020, Art. no.
[19]
T. Oya, T. Asai, T. Fukui, and Y. Amemiya, “A majority-logic device using an irreversible single-electron box,” IEEE Trans. Nanotechnol., vol. 2, no. 1, pp. 15–22, Mar. 2003.
[20]
M. H. Sulieman and V. Beiu, “On single-electron technology full adders,” IEEE Trans. Nanotechnol., vol. 4, no. 6, pp. 669–680, Nov. 2005.
[21]
H. A. Fahmy and R. A. Kiehl, “Complete logic family using tunneling-phase-logic devices,” in Proc. IEEE 11th Int. Conf. Microelectronics, 1999, pp. 153–156.
[22]
E. Testa, M. Soeken, L. G. Amar, and G. De Micheli, “Logic synthesis for established and emerging computing,” Proc. IEEE, vol. 107, no. 1, pp. 165–184, Jan. 2019.
[23]
L. Hellerman, “A catalog of three-variable or-invert and and-invert logical circuits,” IEEE Trans. Electron. Comput., vol. EC-1, no. 3, pp. 198–223, Jun. 1963.
[24]
J. Cong and K. Minkovich, “Optimality study of logic synthesis for lut-based FPGAs,” in Proc ACM/SIGDA 14th Int. Symp. Field Programmable Gate Arrays, 2006, pp. 33–40.
[25]
W. L. Neto et al., “Improving LUT-based optimization for ASICs,” in Proc. IEEE/ACM 59th Des. Automat. Conf., 2022, pp. 421–426.
[26]
L. Amaru, P.-E. Gaillardon, and G. De Micheli, “Majority-inverter graph: A new paradigm for logic optimization,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 35, no. 5, pp. 806–819, May 2016.
[27]
W. J. Haaswijk, M. Soeken, L. Amaru, P.-E. Gaillardon, and G. De Micheli, “LUT mapping and optimization for majority-inverter graphs,” in Proc. 25th Int. Workshop Log. Synth., 2016, pp. 1–8.
[28]
K. Walus, G. Schulhof, G. Jullien, R. Zhang, and W. Wang, “Circuit design based on majority gates for applications with quantum-dot cellular automata,” in Proc. IEEE Conf. Rec. 38th Asilomar Conf. Signals, Syst. Comput., 2004, pp. 1354–1357.
[29]
R. Zhang, P. Gupta, and N. K. Jha, “Synthesis of majority and minority networks and its applications to QCA, TPL and SET based nanotechnologies,” in Proc. IEEE 18th Int. Conf. VLSI Des. Held Jointly With 4th Int. Conf. Embedded Syst. Des., 2005, pp. 229–234.
[30]
K. Kong, Y. Shang, and R. Lu, “An optimized majority logic synthesis methodology for quantum-dot cellular automata,” IEEE Trans. Nanotechnol., vol. 9, no. 2, pp. 170–183, Mar. 2010.
[31]
P. Wang, M. Niamat, S. Vemuru, M. Alam, and T. Killian, “Comprehensive majority/minority logic synthesis method,” in Proc. IEEE 13th Int. Conf. Nanotechnol., 2013, pp. 694–697.
[32]
P. Wang, M. Y. Niamat, S. R. Vemuru, M. Alam, and T. Killian, “Synthesis of majority/minority logic networks,” IEEE Trans. Nanotechnol., vol. 14, no. 3, pp. 473–483, May 2015.
[33]
V. K. Mishra and H. Thapliyal, “Heuristic based majority/minority logic synthesis for emerging technologies,” in Proc. IEEE 30th Int. Conf. VLSI Des. 16th Int. Conf. Embedded Syst., 2017, pp. 295–300.
[34]
L. Amarú, P.-E. Gaillardon, and G. De Micheli, “Boolean logic optimization in majority-inverter graphs,” in Proc. 52nd Ann. Des. Automat. Conf., 2015, pp. 1–6.
[35]
M. Soeken, L. G. Amarù, P.-E. Gaillardon, and G. De Micheli, “Optimizing majority-inverter graphs with functional hashing,” in Proc. IEEE Des. Automat. Test Eur. Conf. Exhib., 2016, pp. 1030–1035.
[36]
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 Des. Integr. Circuits Syst., vol. 36, no. 11, pp. 1842–1855, Nov. 2017.
[37]
H. Riener et al., “Scalable generic logic synthesis: One approach to rule them all,” in Proc. 56th Ann. Des. Automat. Conf., 2019, pp. 1–6.
[38]
H. Riener, E. Testa, L. Amaru, M. Soeken, and G. De Micheli, “Size optimization of migs with an application to QCA and STMG technologies,” in Proc. IEEE/ACM 14th Int. Symp. Nanoscale Architectures, 2018, pp. 157–162.
[39]
W. Haaswijk, M. Soeken, L. Amarú, P.-E. Gaillardon, and G. De Micheli, “A novel basis for logic rewriting,” in Proc. IEEE 22nd Asia South Pacific Des. Automat. Conf., 2017, pp. 151–156.
[40]
L. Amarú, P.-E. Gaillardon, A. Chattopadhyay, and G. De Micheli, “A sound and complete axiomatization of majority-$ n$ logic,” IEEE Trans. Comput., vol. 65, no. 9, pp. 2889–2895, Sep. 2016.
[41]
A. Neutzling, F. S. Marranghello, J. M. Matos, A. Reis, and R. P. Ribas, “maj-$ n$ logic synthesis for emerging technology,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 39, no. 3, pp. 747–751, Mar. 2020.
[42]
Z. Chu, W. Haaswijk, M. Soeken, Y. Xia, L. Wang, and G. De Micheli, “Exact synthesis of Boolean functions in majority-of-five forms,” in Proc. IEEE Int. Symp. Circuits Syst., 2019, pp. 1–5.
[43]
E. C. Ferraz and A. C. R. D. Silva, “Linear optimization models for maj-3 and maj-5 exact synthesis,” IEEE Access, vol. 10, pp. 130518–130531, 2022.
[44]
M. Ajtai, J. Komlós, and E. Szemerédi, “An $o(nlogn$) sorting network,” in Proc. 15th Ann. ACM Symp. Theory comput., 1983, pp. 1–9.
[45]
D. Dor and U. Zwick, “Selecting the median,” SIAM J. Comput., vol. 28, no. 5, pp. 1722–1758, 1999.
[46]
E. Testa, M. Soeken, L. G. Amarù, W. Haaswijk, and G. De Micheli, “Mapping monotone Boolean functions into majority,” IEEE Trans. Comput., vol. 68, no. 5, pp. 791–797, May 2019.
[47]
A. Chattopadhyay, D. Bhattacharjee, and S. Maitra, “Improved linear decomposition of majority and threshold Boolean functions,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 42, no. 11, pp. 3951–3957, Nov., 2023.
[48]
E. Testa et al., “Inversion optimization in majority-inverter graphs,” in Proc. IEEE Int. Symp. Nanoscale Architectures, 2016, pp. 15–20.
[49]
E. Testa et al., “Inverter propagation and fan-out constraints for beyond-CMOS majority-based technologies,” in Proc. IEEE Comput. Soc. Ann. Symp. VLSI, 2017, pp. 164–169.
[50]
E. Testa, M. Soeken, O. Zografos, F. Catthoor, and G. De Micheli, “Exact synthesis for logic synthesis applications with complex constraints,” in Proc. 26th Int. Workshop Log. Synth., 2017, pp. 1–7.
[51]
F. S. Torres, R. Wille, P. Niemann, and R. Drechsler, “An energy-aware model for the logic synthesis of quantum-dot cellular automata,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 37, no. 12, pp. 3031–3041, Dec. 2018.
[52]
R. K. Nath, B. Sen, and B. K. Sikdar, “Optimal synthesis of QCA logic circuit eliminating wire-crossings,” IET Circuits Devices Syst., vol. 11, no. 3, pp. 201–208, 2017.
[53]
D. Bhattacharjee, L. Amaŕu, and A. Chattopadhyay, “Technology-aware logic synthesis for ReRAM based in-memory computing,” in Proc. IEEE Des., Automat. Test Europe Conf. Exhib., 2018, pp. 1435–1440.
[54]
J. Han and M. Orshansky, “Approximate computing: An emerging paradigm for energy-efficient design,” in Proc. IEEE 18th Eur. Test Symp., 2013, pp. 1–6.
[55]
T. Zhang et al., “Majority logic-based approximate multipliers for error-tolerant applications,” in Approximate Computing. Berlin, Germany: Springer, 2022, pp. 119–146.
[56]
H. Cho and E. E. Swartzlander, “Adder designs and analyses for quantum-dot cellular automata,” IEEE Trans. Nanotechnol., vol. 6, no. 3, pp. 374–383, May 2007.
[57]
S. Perri and P. Corsonello, “New methodology for the design of efficient binary addition circuits in QCA,” IEEE Trans. Nanotechnol., vol. 11, no. 6, pp. 1192–1200, Nov. 2012.
[58]
J. Maharaj and S. Muthurathinam, “Efficient majority logic subtractor design using multilayer crossover in quantum-dot cellular automata,” J. Nanophotonics, vol. 14, no. 3, pp. 36011–36011, 2020.
[59]
B. Aravinth and L. J. A. Marcilin, “Implementation of coplanar approximate adders in QCA,” in Proc. IEEE Int. Conf. Wireless Commun., Signal Process. Netw., 2016, pp. 680–684.
[60]
M. Parameshwara and N. Maroof, “An area-efficient majority logic-based approximate adders with low delay for error-resilient applications,” Circuits, Syst. Signal Process., vol. 41, no. 9, pp. 4977–4997, 2022.
[61]
C. Labrado, H. Thapliyal, and F. Lombardi, “Design of majority logic based approximate arithmetic circuits,” in Proc. IEEE Int. Symp. Circuits Syst., 2017, pp. 1–4.
[62]
T. Zhang, W. Liu, E. McLarnon, M. O'Neill, and F. Lombardi, “Design of majority logic (ML) based approximate full adders,” in Proc. IEEE Int. Symp. Circuits Syst., 2018, pp. 1–5.
[63]
H. Cho and E. E. Swartzlander, “Adder and multiplier design in quantum-dot cellular automata,” IEEE Trans. Comput., vol. 58, no. 6, pp. 721–727, Jun. 2009.
[64]
W. Liu, T. Zhang, E. McLarnon, M. O'Neill, P. Montuschi, and F. Lombardi, “Design and analysis of majority logic-based approximate adders and multipliers,” IEEE Trans. Emerg. Topics Comput., vol. 9, no. 3, pp. 1609–1624, Jul.–Sep. 2021.
[65]
S. Perri, F. Spagnolo, F. Frustaci, and P. Corsonello, “Accuracy improved low-energy multi-bit approximate adders in QCA,” IEEE Trans. Circuits Syst. II: Express Briefs, vol. 26, no. 7, pp. 3456–3460, Nov. 2021.
[66]
Z. Chu, C. Shang, T. Zhang, Y. Xia, L. Wang, and W. Liu, “Efficient design of majority-logic-based approximate arithmetic circuits,” IEEE Trans. Very Large Scale Integration Syst, vol. 30, no. 12, pp. 1827–1839, Dec. 2022.
[67]
J. Liang, J. Han, and F. Lombardi, “New metrics for the reliability of approximate and probabilistic adders,” IEEE Trans. Comput., vol. 62, no. 9, pp. 1760–1771, Sep. 2013.
[68]
C. Shang and Z. Chu, “Design of majority logic based 4-bit approximate subtractors and its application in divider,” in Proc. IEEE 14th Int. Conf. ASIC, 2021, pp. 1–4.
[69]
W.-C. Yeh and C.-W. Jen, “High-speed Booth encoded parallel multiplier design,” IEEE Trans. Comput., vol. 49, no. 7, pp. 692–701, Jul. 2000.
[70]
P. Behrooz, “Computer arithmetic: Algorithms and hardware designs,” Oxford Univ. Press, vol. 19, pp. 512583–512585, 2000.
[71]
C. S. Wallace, “A suggestion for a fast multiplier,” IEEE Trans. Comput., vol. EC-13, no. 1, pp. 14–17, Feb. 1964.
[72]
L. Dadda, “Some schemes for parallel multipliers,” Alta Frequenza, vol. 34, pp. 349–356, 1965.
[73]
T. Zhang, W. Liu, J. Han, and F. Lombardi, “Design and analysis of majority logic based approximate radix-4 Booth encoders,” in Proc. IEEE/ACM Int. Symp. Nanoscale Architectures, 2019, pp. 1–6.
[74]
T. Zhang et al., “Design of majority logic-based approximate Booth multipliers for error-tolerant applications,” IEEE Trans. Nanotechnol., vol. 21, pp. 81–89, 2022.
[75]
T. Zhang, H. Jiang, W. Liu, F. Lombardi, L. Liu, and J. Han, “Majority logic-based approximate recording adders for high-radix booth multipliers,” in Proc. IEEE 22nd Int. Conf. Nanotechnol., 2022, pp. 519–522.
[76]
M. H. Moaiyeri, F. Sabetzadeh, and S. Angizi, “An efficient majority-based compressor for approximate computing in the nano era,” Microsyst. Technol., vol. 24, no. 3, pp. 1589–1601, 2018.
[77]
M. Taheri, A. Arasteh, S. Mohammadyan, A. Panahi, and K. Navi, “A novel majority based imprecise 4: 2 compressor with respect to the current and future vlsi industry,” Microprocessors Microsystems, vol. 73, 2020, Art. no.
[78]
F. Sabetzadeh, M. H. Moaiyeri, and M. Ahmadinejad, “A majority-based imprecise multiplier for ultra-efficient approximate image multiplication,” IEEE Trans. Circuits Syst. I: Reg. article, vol. 66, no. 11, pp. 4200–4208, Nov. 2019.
[79]
S. Angizi, H. Jiang, R. F. DeMara, J. Han, and D. Fan, “Majority-based spin-CMOS primitives for approximate computing,” IEEE Trans. Nanotechnol., vol. 17, no. 4, pp. 795–806, Jul. 2018.
[80]
Y. Zhang, C. He, T. Zhang, J. Han, and G. Xie, “Design and analysis of a majority logic based imprecise 6–2 compressor for approximate multipliers,” in Proc. IEEE 22nd Int. Conf. Nanotechnol., 2022, pp. 291–294.
[81]
H. Jiang, S. Angizi, D. Fan, J. Han, and L. Liu, “Non-volatile approximate arithmetic circuits using scalable hybrid spin-CMOS majority gates,” IEEE Trans. Circuits Syst. I: Reg. article, vol. 68, no. 3, pp. 1217–1230, Mar. 2021.
[82]
J. Han, E. R. Boykin, H. Chen, J. Liang, and J. A. B. Fortes, “On the reliability of computational structures using majority logic,” IEEE Trans. Nanotechnol., vol. 10, no. 5, pp. 1099–1112, Sep. 2011.
[83]
S. Roy and V. Beiu, “Majority multiplexing-economical redundant fault-tolerant designs for nanoarchitectures,” IEEE Trans. Nanotechnol., vol. 4, no. 4, pp. 441–451, Jul. 2005.
[84]
W. Ibrahim, V. Beiu, and M. H. Sulieman, “On the reliability of majority gates full adders,” IEEE Trans. Nanotechnol., vol. 7, no. 1, pp. 56–67, Jan. 2008.
[85]
J. Han and P. Jonker, “A system architecture solution for unreliable nanoelectronic devices,” IEEE Trans. Nanotechnol., vol. 1, no. 4, pp. 201–208, Dec. 2002.
[86]
M. Momenzadeh, J. Huang, M. B. Tahoori, and F. Lombardi, “On the evaluation of scaling of QCA devices in the presence of defects at manufacturing,” IEEE Trans. Nanotechnol., vol. 4, no. 6, pp. 740–743, Nov. 2005.
Index Terms
- A Survey of Majority Logic Designs in Emerging Nanotechnologies for Computing
Index terms have been assigned to the content through auto-classification.
Recommendations
Majority-based reversible logic gates
Reversible logic plays an important role in the synthesis of circuits for quantum computing. In this paper, we introduce families of reversible gates based on the majority Boolean function (MBF) and we prove their properties in reversible circuit ...
Majority Logic Formulations for Parallel Adder Designs at Reduced Delay and Circuit Complexity
The design of high-performance adders has experienced a renewed interest in the last few years; among high performance schemes, parallel prefix adders constitute an important class. They require a logarithmic number of stages and are typically realized ...
Adder designs using reversible logic gates
A new reversible logic gate was proposed in Ref. [1]. This gate can be used to implement any classical Boolean logic function. This paper shows the application of the reversible gate in implementing ripple carry, carry skip and carry look-ahead adders. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1536-125X © 2023 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: 20 October 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in