Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (5): 1145-1154.doi: 10.1007/s11390-021-0898-7

Special Issue: Computer Architecture and Systems

• Special Section of 2020 CCF Integrated Circuit Design and Automation Conference • Previous Articles     Next Articles

Inversion Optimization Strategy Based on Primitives with Complement Attributes

Hui-Ming Tian, Student Member, CCF, and Zhu-Fei Chu*, Member, CCF, IEEE        

  1. Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China
  • Received:2020-08-11 Revised:2021-04-26 Online:2021-09-30 Published:2021-09-30
  • About author:Hui-Ming Tian received his B.S. degree in microelectronic science and engineering from Ningbo University, Ningbo, in 2018. Now he is pursuing his M.S. degree in integrated circuit engineering in the same university.
  • Supported by:
    This work was partially supported by the National Natural Science Foundation of China under Grant No. 61871242, and K.C.Wong Magna Fund in Ningbo University.

Inverters or logic primitives that have complement attributes are essential to building a logical complement system. NAND and NOR operations which have complement attributes are of high interest for complementary metal-oxidesemiconductor (CMOS) technology, as they can be easily implemented in transistors. Different from the logic models used in standard CMOS, several nano-emerging technologies, such as quantum-dot cellular automata (QCA) and spin torque majority gates, are in favor of realizing a majority voter function but imposing difficulties in implementing inversions. Previous studies pay lots of effort in optimizing the number of inverters in logic representations, whereas the mapping using primitives with complement attributes is not a major concern. In this paper, we establish a technology mapping method from logic representations to nanotechnology primitives by considering NAND-NOR-Inverter (NNI) and exclusive-NOR (XNOR) operations. We adopt XOR-Majority Graph (XMG) as a logic representation. The proposed mapping method is evaluated using the QCA technology. Experimental results over EPFL benchmark suites show we achieve 11.77% and 30.13% reductions in the area and the number of inverters, respectively.

Key words: inversion optimization; quantum-dot cellular automata; majority-of-three; NAND-NOR-Inverter (NNI);

[1] Chu Z, Soeken M, Xia Y et al. Advanced functional decom position using majority and its applications. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2020, 39(8):1621-1634. DOI:10.1109/TCAD.2019.2925392.
[2] Mishchenko A, Chatterjee S, Brayton R. DAG-aware AIG rewriting:A fresh look at combinational logic synthesis. In Proc. the 43rd ACM/IEEE Design Automation Conference, Jul. 2006, pp.532-535. DOI:10.1145/1146909.1147048.
[3] Testa E, Soeken M, Amarú L G, De Micheli G. Logic synthesis for established and emerging computing. Proceedings of the IEEE, 2018, 107(1):165-184. DOI:10.1109/JPROC.2018.2869760.
[4] Lent C S, Tougaw P D, Porod W, Bernstein G H. Quantum cellular automata. Nanotechnology, 1993, 4(1):Article No. 49. DOI:10.1088/0957-4484/4/1/004.
[5] Nikonov D E, Bourianoff G I, Ghani T. Proposal of a spin torque majority gate logic. IEEE Electron Device Letters, 2011, 32(8):1128-1130. DOI:10.1109/LED.2011.2156379.
[6] Mohaghegh S M, Reza S N, Mohammadi M. Innovative model for ternary QCA gates. IET Circuits, Devices & Systems, 2017, 12(2):189-195. DOI:10.1049/ietcds.2017.0276.
[7] Amarù L, Gaillardon P E, De Micheli G. Majorityinverter graph:A novel data-structure and algorithms for efficient logic optimization. In Proc. the 1st ACM/IEEE Design Automation Conference, Jun. 2014. DOI:10.1145/2593069.2593158.
[8] Amarù L, Gaillardon P E, De Micheli G. Majority-inverter graph:A new paradigm for logic optimization. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2016, 35(5):806-819. DOI:10.1109/TCAD.2015.2488484.
[9] Haaswijk W, Soeken M, Amarù L et al. A novel basis for logic rewriting. In Proc. the 22nd Asia and South Pacific Design Automation Conference, Jan. 2017, pp.151-156. DOI:10.1109/ASPDAC.2017.7858312.
[10] Testa E, Soeken M, Zografos O et al. Inversion optimization in majority-inverter graphs. In Proc. the 2016 IEEE/ACM Int. Symp. Nanoscale Architectures, Jul. 2016, pp.15-20. DOI:10.1145/2950067.2950072.
[11] Shi L, Chu Z. Inversions optimization in XOR-majority graphs with an application to QCA. In Proc. the 2019 China Semiconductor Technology International Conference, Mar. 2019. DOI:10.1109/CSTIC.2019.8755713.
[12] Chu Z, Shi L, Wang L, Xia Y. Multi-objective algebraic rewriting in XOR-majority graphs. Integration, 2019, 69:40-49. DOI:10.1016/j.vlsi.2019.08.005.
[13] Momenzadeh M, Huang J, Tahoori M B, Lombardi F. Characterization, test, and logic synthesis of and-or-inverter (AOI) gate design for QCA implementation. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2005, 24(12):1881-1893. DOI:10.1109/TCAD.2005.852667.
[14] Sen B, Sikdar B K. A study on defect tolerance of tiles implementing universal gate functions. In Proc. the 2007 International Conference on Design & Technology of Integrated Systems in Nanoscale Era, Sept. 2007, pp.13-18. DOI:10.1109/DTIS.2007.4449484.
[15] Zhang R, Gupta P, Jha N K. Majority and minority network synthesis with application to QCA-, SET-, and TPL-Based nanotechnologies. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2007, 26(7):1233-1245. DOI:10.1109/TCAD.2006.888267.
[16] Kong K, Shang Y, Lu R. An optimized majority logic synthesis methodology for quantum-dot cellular automata. IEEE Trans. Nanotechnol., 2010, 9(2):170-183. DOI:10.1109/TNANO.2009.2028609.
[17] Wang P, Niamat M Y, Vemuru S R, Alam M, Killian T. Synthesis of majority/minority logic networks. IEEE Trans. Nanotechnol., 2015, 14(3):473-483. DOI:10.1109/TNANO.2015.2408330.
[18] Soeken M, Amarù L, Gaillardon P et al. Exact synthesis of majority-inverter graphs and its applications. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2017, 36(11):1842-1855. DOI:10.1109/TCAD.2017.2664059.
[19] Neutzling A, Marranghello F S, Matos J M, Reis A, Ribas R P. maj-n logic synthesis for emerging technology. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2020, 39(3):747-751. DOI:10.1109/TCAD.2019.2897704.
[20] Vacca M, Vighetti D, Mascarino M, Amarù L G, Graziano M, Zamboni M. Magnetic QCA majority voter feasibility analysis. In Proc. the 7th Conference on Ph.D. Research in Microelectronics and Electronics, Jul. 2011, pp.229-232. DOI:10.1109/PRIME.2011.5966275.
[21] Testa E, Zografos O, Soeken M et al. Inverter propagation and fan-out constraints for beyond-CMOS majority-based technologies. In Proc. the 2017 IEEE Computer Society Annual Symposium on VLSI, Feb. 2017, pp.164-169. DOI:10.1109/ISVLSI.2017.37.
[22] Amarù L G, Gaillardon P E, De Micheli G. The EPFL combinational benchmark suite. In Proc. the 24th International Workshop on Logic & Synthesis, Jun. 2015.
[23] Walus K, Dysart T J, Jullien G A, Budiman R A. QCADesigner:A rapid design and simulation tool for quantum-dot cellular automata. IEEE Trans. Nanotechnol., 2004, 3(1):26-31. DOI:10.1109/TNANO.2003.820815.
No related articles found!
Full text



[1] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[2] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[3] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[4] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[5] Xu Xiaoshu;. Simplification of Multivalued Sequential SULM Network by Using Cascade Decomposition[J]. , 1986, 1(4): 84 -95 .
[6] Shi Zhongzhi;. Knowledge-Based Decision Support System[J]. , 1987, 2(1): 22 -29 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Xia Peisu; Fang Xinwo; Wang Yuxiang; Yan Kaiming; Zhang Tingjun; Liu Yulan; Zhao Chunying; Sun Jizhong;. Design of Array Processor Systems[J]. , 1987, 2(3): 163 -173 .
[10] Sun Yongqiang; Lu Ruzhan; Huang Xiaorong;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved