The physical limitations of complementary metal-oxide semiconductor？(CMOS) technology have led many researchers to consider other alternative technologies. Quantum-dot cellular automate (QCA), single electron tunneling (SET), tunneling phase logic (TPL), spintronic devices, etc., are some of the nanotechnologies that are being considered as possible replacements for CMOS. In these nanotechnologies, the basic logic units used to implement circuits are majority and/or minority gates. Several majority/minority logic circuit synthesis methods have been proposed. In this paper, we give a comparative study of the existing majority/minority logic circuit synthesis methods that are capable of synthesizing multi-input multi-output Boolean functions. Each of these methods is discussed in detail. The optimization priorities given to different factors such as gates, levels, inverters, etc., vary with technologies. Based on these optimization factors, the results obtained from different synthesis methods are compared. The paper also analyzes the optimization capabilities of different methods and discusses directions for future research in the synthesis of majority/minority logic networks.
References
[1]
2013 International Technology Roadmap for Semiconductors (ITRS).
http://www.semiconductors.org
[2]
Lent, C.S., Tougaw, P.D., Porod, W. and Bernstein, G.H. (1993) Quantum Cellular Automata. Nanotechnology, 4, 49. https://doi.org/10.1088/0957-4484/4/1/004
[3]
Tougaw, P.D. and Lent, C.S. (1994) Logical Devices Implemented Using Quantum Cellular Automata. Journal of Applied Physics, 75, 1818-1825.
https://doi.org/10.1063/1.356375
[4]
Lent, C.S. and Tougaw, P.D. (1997) A Device Architecture for Computing with Quantum Dots. Proceedings of the IEEE, 85, 541-557.
https://doi.org/10.1109/5.573740
[5]
Porod, W. (1997) Quantum-Dot Devices and Quantum-Dot Cellular Automata. International Journal of Bifurcation and Chaos, 7, 2199-2218.
https://doi.org/10.1142/S0218127497001606
[6]
Snider, G., Orlov, A., Amlani, I., Zuo, X., Bernstein, G., Lent, C., Merz, J. and Porod, W. (1999) Quantum-Dot Cellular Automata: Review and Recent Experiments. Journal of Applied Physics, 85, 4283-4285. https://doi.org/10.1063/1.370344
[7]
Walus, K., Jullien, G.A. and Dimitrov, V.S. (2003) Computer Arithmetic Structures for Quantum Cellular Automata. Conference Record of the 37th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 9-12 November 2003, 1435-1439. https://doi.org/10.1109/ACSSC.2003.1292223
[8]
Oya, T., Asai, T., Fukui, T. and Amemiya, Y. (2002) A Majority-Logic Nanodevice Using a Balanced Pair of Single-Electron Boxes. Journal of Nanoscience and Nanotechnology, 2, 333-342. https://doi.org/10.1166/jnn.2002.108
[9]
Oya, T., Asai, T., Fukui, T. and Amemiya, Y. (2003) A Majority-Logic Device Using an Irreversible Single-Electron Box. IEEE Transactions on Nanotechnology, 2, 15-22.
https://doi.org/10.1109/TNANO.2003.808507
[10]
Fahmy, H.A.H. and Kiehl, R.A. (1999) Complete Logic Family Using Tunneling- Phase-Logic Devices. Proceedings of the International Conference on Microelectronics, Kuwait City, November 1999, 153-156.
[11]
Nikonov, D.E. and Young, I.A. (2013) Overview of Beyond-CMOS Devices and a Uniform Methodology for Their Benchmarking. Proceedings of the IEEE, 101, 2498-2533. https://doi.org/10.1109/JPROC.2013.2252317
[12]
Miller, H.S. and Winder, R.O. (1962) Majority-Logic Synthesis by Geometric Methods. IRE Transactions on Electronic Computers, EC-11, 89-90.
https://doi.org/10.1109/TEC.1962.5219329
[13]
Akers, S.B. (1962) Synthesis of Combinational Logic Using Three-Input Majority Gates. Proceedings of the Third Annual Symposium on Switching Circuit Theory and Logical Design, Chicago, IL, 7-12 October 1962, 149-158.
https://doi.org/10.1109/FOCS.1962.16
[14]
Muroga, S. (1971) Threshold Logic and Its Applications. Wiley, New York.
[15]
Rumi, Z., Walus, K., Wang, W. and Jullien, G.A. (2004) A Method of Majority Logic Reduction for Quantum Cellular Automata. IEEE Transactions on Nanotechnology, 3, 443-450. https://doi.org/10.1109/TNANO.2004.834177
[16]
Walus, K., Schulhof, G., Jullien, G.A., Zhang, R. and Wang, W. (2004) Circuit Design Based on Majority Gates for Applications with Quantum-Dot Cellular Automata. Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 7-10 November 2004, 1354-1357.
[17]
Bonyadi, M.R., Azghadi, S.M.R., Rad, N.M., Navi, K. and Afjei, E. (2007) Logic Optimization for Majority Gate-Based Nanoelectronic Circuits Based on Genetic Algorithm. International Conference on Electrical Engineering, ICEE’07, Lahore, 11-12 April 2007, 1-5.
[18]
Rai, S. (2008) Majority Gate Based Design for Combinational Quantum Cellular Automata (QCA) Circuits. 40th Southeastern Symposium on System Theory, New Orleans, LA, 16-18 March 2008, 222-224.
https://doi.org/10.1109/SSST.2008.4480225
[19]
Huo, Z., Zhang, Q., Haruehanroengra, S. and Wang, W. (2006) Logic Optimization for Majority Gate-Based Nanoelectronic Circuits. 2006 IEEE International Symposium on Circuits and Systems, Island of Kos, 21-24 May 2006, 1307-1310.
[20]
Zhang, R., Gupta, P. and Jha, N.K. (2007) Majority and Minority Network Synthesis with Application to QCA-, SET-, and TPL-Based Nanotechnologies. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26, 1233-1245.
https://doi.org/10.1109/TCAD.2006.888267
[21]
Kong, K., Shang, Y. and Lu, R. (2010) An Optimized Majority Logic Synthesis Methodology for Quantum-Dot Cellular Automata. IEEE Transactions on Nanotechnology, 9, 170-183. https://doi.org/10.1109/TNANO.2009.2028609
[22]
Wang, P., Niamat, M. and Vemuru, S. (2013) Minimal Majority Gate Mapping of Four-Variable Functions for Quantum-Dot Cellular Automata. In: Iniewski, K., Ed., Nanoelectronic Device Applications Handbook, CRC Press, Boca Raton, Florida, 263-280.
[23]
Mitchell, M. (1998) An Introduction to Genetic Algorithms. MIT Press, Cambridge, Massachusetts.
[24]
Holland, J.H. (1992) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. U Michigan Press, Ann Arbor, Michigan.
[25]
Sentovich, E.M., Singh, K.J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P.R., Brayton, R.K. and Sangiovanni-Vincentelli, A. (1992) SIS: A System for Sequential Circuit Synthesis. Technical Report No. UCB/ERL M92/41. University of California, Berkeley.
[26]
Wang, P., Niamat, M.Y., Vemuru, S.R., Alam, M. and Killian, T. (2015) Synthesis of Majority/Minority Logic Networks. IEEE Transactions on Nanotechnology, 14, 473-483. https://doi.org/10.1109/TNANO.2015.2408330
[27]
Orlov, A.O., Amlani, I., Toth, G., Lent, C.S., Bernstein, G.H. and Snider, G.L. (1999) Experimental Demonstration of a Binary Wire for Quantum-Dot Cellular Automata. Applied Physics Letters, 74, 2875-2877. https://doi.org/10.1063/1.124043
[28]
Orlov, A.O., Amlani, I., Kummamuru, R.K., Ramasubramaniam, R., Toth, G., Lent, C.S., Bernstein, G.H. and Snider, G.L. (2000) Experimental Demonstration of Clocked Single-Electron Switching in Quantum-Dot Cellular Automata. Applied Physics Letters, 77, 295-297. https://doi.org/10.1063/1.126955
[29]
Nikonov, D.E., Bourianoff, G.I. and Ghani, T. (2011) Proposal of a Spin Torque Majority Gate Logic. IEEE Electron Device Letters, 32, 1128-1130.
https://doi.org/10.1109/LED.2011.2156379
[30]
Bourianoff, G.I. and Nikonov, D.E. (2011) Recent Progress, Opportunities and Challenges for Beyond CMOS Information Processing Technologies. ECS Transactions, 35, 43-53. https://doi.org/10.1149/1.3568847
[31]
Behin-Aein, B., Datta, D., Salahuddin, S. and Datta, S. (2010) Proposal for an All-Spin Logic Device with Built-In Memory. Nature Nanotechnology, 5, 266-270.
https://doi.org/10.1038/nnano.2010.31
[32]
Behin-Aein, B., Sarkar, A., Srinivasan, S. and Datta, S. (2011) Switching Energy-Delay of All Spin Logic Devices. Applied Physics Letters, 98, Article ID: 123510.
https://doi.org/10.1063/1.3567772
[33]
Mankalale, M.G. and Sapatnekar, S.S. (2016) Optimized Standard Cells for All-Spin Logic. ACM Journal on Emerging Technologies in Computing Systems (JETC), 13, 21. https://doi.org/10.1145/2967612
[34]
Krivorotov, I. and Markovic, D. (2011) STT Oscillators/Memory. MIND Annual Review and NRI Benchmarking Workshop, Notre Dame, IN, USA, 16-18.
[35]
Khitun, A. and Wang, K.L. (2005) Nano Scale Computational Architectures with Spin Wave Bus. Superlattices and Microstructures, 38, 184-200.
https://doi.org/10.1016/j.spmi.2005.07.001
[36]
Bernstein, K., Cavin, R.K., Porod, W., Seabaugh, A. and Welser, J. (2005) Device and Architecture Outlook for beyond CMOS Switches. Proceedings of the IEEE, 98, 2169-2184. https://doi.org/10.1109/JPROC.2010.2066530
[37]
Klingler, S., Pirro, P., Bracher, T., Leven, B., Hillebrands, B. and Chumak, A.V. (2014) Design of a Spin-Wave Majority Gate Employing Mode Selection. Applied Physics Letters, 105, Article ID: 152410. https://doi.org/10.1063/1.4898042
[38]
Zografos, O., Raghavan, P., Amaru, L., Soree,′ B., Lauwereins, R., Radu, I., Verkest, D. and Thean, A. (2014) System-Level Assessment and Area Evaluation of Spin Wave Logic Circuits. 2014 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH), Paris, 8-10 July 2014, 25-30.
https://doi.org/10.1109/NANOARCH.2014.6880475
[39]
Khitun, A. and Wang, K.L. (2011) Non-Volatile Magnonic Logic Circuits Engineering. Journal of Applied Physics, 110, Article ID: 034306.
https://doi.org/10.1063/1.3609062
[40]
Kostylev, M., Serga, A., Schneider, T., Leven, B. and Hillebrands, B. (2005) Spin- Wave Logical Gates. Applied Physics Letters, 110, Article ID: 153501.
https://doi.org/10.1063/1.2089147
[41]
Amaru, L., Gaillardon, P.-E., Mitra, S. and De Micheli, G. (2015) New Logic Synthesis as Nanotechnology Enabler. Proceedings of the IEEE, 103, 2168-2195.
https://doi.org/10.1109/JPROC.2015.2460377
[42]
Cowburn, R.P. and Welland, M.E. (2000) Room Temperature Magnetic Quantum Cellular Automata. Science, 287, 1466-1468.
https://doi.org/10.1126/science.287.5457.1466
[43]
Zhu, J., Zhang, L., Dong, S. and Wang, E. (2013) Four-Way Junction-Driven DNA Strand Displacement and Its Application in Building Majority Logic Circuit. ACS Nano, 7, 10211-10217. https://doi.org/10.1021/nn4044854
[44]
Li, W., Yang, Y., Yan, H. and Liu, Y. (2013) Three-Input Majority Logic Gate and Multiple Input Logic Circuit Based on DNA Strand Displacement. Nano Letters, 13, 2980-2988. https://doi.org/10.1021/nl4016107
[45]
George, A.K. and Singh, H. (2016) Three-Input Majority Gate Using Spatially Localised DNA Hairpins. IEEE Transactions on NanoBioscience, 15, 928-938.
https://doi.org/10.1109/TNB.2016.2623218
[46]
Schwierz, F. (2010) Graphene Transistors. Nature Nanotechnology, 5, 487-496.
https://doi.org/10.1038/nnano.2010.89
[47]
Yang, H., Heo, J., Park, S., Song, H.J., Seo, D.H., Byun, K.-E., Kim, P., Yoo, I., Chung, H.-J. and Kim, K. (2010) Graphene Barristor, a Triode Device with a Gate- Controlled Schottky Barrier. Science, 336, 1140-1143.
https://doi.org/10.1126/science.1220527
[48]
Miryala, S., Tenace, V., Calimera, A., Macii, E., Poncino, M., Amaru, L., De Micheli, G. and Gaillardon, P.-E. (2015) Exploiting the Expressive Power of Graphene Reconfigurable Gates via Post-Synthesis Optimization. 25th Great Lakes Symposium on VLSI (GLSVLSI), Pittsburgh, Pennsylvania, 20-22 May 2015, 39-44.
https://doi.org/10.1145/2742060.2742098
[49]
Linn, E., Rosezin, R., Kugeler, C. and Waser, R. (2010) Complementary Resistive Switches for Passive Nanocrossbar Memories. Nature Materials, 9, 403-406.
https://doi.org/10.1038/nmat2748
[50]
Fackenthal, R., Kitagawa, M., Otsuka, W., Prall, K., Mills, D., Tsutsui, K., Javanifard, J., Tedrow, K., Tsushima, T., Shibahara, Y., et al. (2014) 19.7 A 16Gb ReRAM with 200MB/s Write and 1GB/s Read in 27 nm Technology. 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), San Francisco, CA, 9-13 February 2014, 338-339. https://doi.org/10.1109/ISSCC.2014.6757460
[51]
Sheu, S.-S., Chang, M.-F., Lin, K.-F., Wu, C.-W., Chen, Y.-S., Chiu, P.-F., Kuo, C.-C., Yang, Y.-S., Chiang, P.-C., Lin, W.-P., et al. (2011) A 4Mb Embedded SLC Resistive-RAM Macro with 7.2 ns Read-Write Random-Access Time and 160 ns MLC-Access Capability. IEEE Solid-State Circuits Conference Digest of Technical Papers, February 2011, 200-202.
[52]
Lin, Y.-M., Appenzeller, J., Knoch, J. and Avouris, P. (2005) High-Performance Carbon Nanotube Field Effect Transistor with Tunable Polarities. IEEE Transactions on Nanotechnology, 4, 481-489. https://doi.org/10.1109/TNANO.2005.851427
[53]
Appenzeller, J. (2008) Carbon Nanotubes for High-Performance Electronics Progress and Prospect. Proceedings of the IEEE, 96, 201-211.
https://doi.org/10.1109/JPROC.2007.911051
[54]
Navi, K., Momeni, A., Sharifi, F. and Keshavarzian, P. (2009) Two Novel Ultra High Speed Carbon Nanotube Full-Adder Cells. IEICE Electronics Express, 6, 1395-1401.
https://doi.org/10.1587/elex.6.1395
[55]
Navi, K., Sharifi, F., Momeni, A. and Keshavarzian, P. (2009) Ultra High Speed CNFET Full-Adder Cell Based on Majority Gates. IEICE Transactions on Electronics, 93, 932-934.
[56]
Dadda, L. (1963) Information Processing: Proceedings of the IFIP Congress. North Holland, The Netherlands.
[57]
Lisanke, R. (1988) Logic Synthesis and Optimization Benchmarks User Guide Version 2.0. Tech Report, Microelectronics Center North Carolina, Research Triangle Park.
