计算机科学技术学报 ›› 2021,Vol. 36 ›› Issue (5): 1145-1154.doi: 10.1007/s11390-021-0898-7

所属专题: Computer Architecture and Systems

• • 上一篇    下一篇

基于具有互补属性器件的反相器优化策略

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
  • 收稿日期:2020-08-11 修回日期:2021-04-26 出版日期:2021-09-30 发布日期:2021-09-30
  • 作者简介: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.
  • 基金资助:
    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.

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.

研究背景:
反相器和具有互补属性的器件对于构建一个逻辑完备系统来说是非常重要的,NAND和NOR操作在传统的CMOS工艺中受到了广泛关注,因为它们可以通过半导体被轻易地实现。不同于标准的CMOS单元,一些纳米技术例如量子元胞自动机(QCA)等,易于实现多数逻辑门,而对于反相器的实现具有一定的困难,同时反相器占有较大的面积。以前QCA中优化反相器的方法主要集中于优化电路的逻辑表示中的反相器数量,而使用本身具有互补属性的器件进行逻辑映射优化并未被考虑到,从而限制了电路可以获取更优的面积以及延时的可能性。
目的:
我们的研究目标是,提供一种从基于多数逻辑运算符的逻辑表示到QCA中基本器件库{AND,OR,NAND,NOR,NOT,XOR,XNOR}的逻辑映射方法,通过该方法来减少电路在QCA中实现时所需要的反相器的数量。
方法:
我们提出了一套适用于QCA中反相器数量优化的逻辑映射算法,通过C++语言实现了所提出的算法并集成到了开源综合工具ALSO中,运行“xmgcost2”命令即可对输入电路进行反相器数量的优化并且报告电路在QCA中实现所需要的面积、延时等代价。
结果:
我们的方法对于XMG和MIG格式的电路具有良好的优化效果,通过对EPFL中的二十个基准电路开展实验,结果表明,对于MIG格式电路而言,同目前最好的方法相比,我们的方法可以45.95%的面积和98.40%的反相器数量;对于XMG格式电路而言,我们的方法可以优化11.77%的面积和30.13%的反相器数量。
结论:
相比于传统的优化电路逻辑表示中的反相器数量的方法,我们提出了一套适用于QCA中反相器数量优化的逻辑映射算法,通过选取EPFL的二十个基准电路开展实验,结果表明,通过将本身具有互补属性的XNOR和NNI器件添加进QCA单元映射库,对于MIG和XMG电路具有良好的优化效果。

关键词: 反相器优化, 量子元胞自动机, 三输入则多门, 与非-或非-反相器

Abstract: 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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 李万学;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[2] C.Y.Chung; 华宣仁;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[3] 章萃; 赵沁平; 徐家福;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[4] 黄学东; 蔡莲红; 方棣棠; 迟边进; 周立; 蒋力;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[5] 许小曙;. Simplification of Multivalued Sequential SULM Network by Using Cascade Decomposition[J]. , 1986, 1(4): 84 -95 .
[6] 史忠植;. Knowledge-Based Decision Support System[J]. , 1987, 2(1): 22 -29 .
[7] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] 夏培肃; 方信我; 王玉祥; 严开明; 张廷军; 刘玉兰; 赵春英; 孙继忠;. Design of Array Processor Systems[J]. , 1987, 2(3): 163 -173 .
[10] 孙永强; 陆汝占; 黄小戎;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: