Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (5): 1118-1132.doi: 10.1007/s11390-021-0904-0

Special Issue: Computer Architecture and Systems

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

Defect-Tolerant Mapping of CMOL Circuit Targeting Delay Optimization

Xiao-Jing Zha, Yin-Shui Xia*, Shang-Luan Xie, and Zhu-Fei Chu*, Member, CCF, IEEE        

  1. Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China
  • Received:2020-08-19 Revised:2021-08-05 Online:2021-09-30 Published:2021-09-30
  • About author:Xiao-Jing Zha received her B.S. degree in communication engineering from Anhui Normal University, Wuhu, in 2016. She is currently working toward her Ph.D. degree in communication and information system at Ningbo University, Ningbo. Her research interests include electronic design automation and logic mapping.
  • Supported by:
    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. U1709218 and 61871242.

In view of the significant number of defective nanodevices in the Cmos/nanowire/MOLecular hybrid (CMOL) circuit, defect-tolerant mapping is an essential step to achieve correct logic operations in defective CMOL circuits. However, less effort has been made to improve circuit delay by defect-tolerant strategies. In this paper, the factors affecting the delay of mapped circuits are analyzed, and the path-tree based defect-tolerant mapping method for the delay optimization is proposed. From the logic-domain, the terminology of the path tree is presented, and the logic circuit is first partitioned into multiple path trees. Then, the mapping areas in the physic-domain are pre-planned for (near) critical path trees. During the mapping process, the specific mapping modes and an updating strategy are formulated to map the path trees:inputs are mapped based on input sorting; (near) critical path trees are mapped with priority, while the others are mapped in a hierarchical way. Finally, an improved tabu search algorithm is employed to verify the validity of the proposed defect-tolerant mapping method. Experimental evaluations on the ISCAS benchmarks show that the proposed method can reduce circuit delay by 15.22%.

Key words: nanohybrid circuit; defect-tolerant mapping; delay optimization;

[1] Goldstein S C, Budiu M. Nanofabrics:Spatial computing using molecular electronics. SIGARCH Comput. Archit. News, 2001, 29(2):178-191. DOI:10.1145/384285.379262.
[2] DeHon A. Nanowire-based programmable architectures. J. Emerg. Technol. Comput. Syst., 2005, 1(2):109-162. DOI:10.1145/1084748.1084750.
[3] Lu W, Lieber C M. Nanoelectronics from the bottom up. Nature Materials, 2007, 6(11):841-850. DOI:10.1038/nmat2028.
[4] Strukov D B, Likharev K K. CMOL FPGA:A reconfigurable architecture for hybrid digital circuits with twoterminal nanodevices. Nanotechnology, 2005, 16(6):888-900. DOI:10.1088/0957-4484/16/6/045.
[5] Likharev K K. Hybrid CMOS/nanoelectronic circuits:Opportunities and challenges. J. Nanoelectron. Optoelectron., 2008, 3(3):203-230. DOI:10.1166/jno.2008.301.
[6] Madhavan A, Sherwood T, Strukov D B. High-throughput pattern matching with CMOL FPGA circuits:Case for logic-in-memory computing. IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2018, 26(12):2759-2772. DOI:10.1109/TVLSI.2018.2809644.
[7] Sait S M, Oughali F C, Arafeh A M. Engineering a memetic algorithm from discrete cuckoo search and tabu search for cell assignment of hybrid nanoscale CMOL circuits. J. Circuits Syst. Comput., 2016, 25(04):Article No. 1650023. DOI:10.1142/S0218126616500237.
[8] Xia Y, Chu Z, Hung W N N, Wang L, Song X. An integrated optimization approach for nanohybrid circuit cell mapping. IEEE Trans. Nanotechnol., 2011, 10(6):1275-1284. DOI:10.1109/TNANO.2011.2131153.
[9] Tunali O, Altun M. A survey of fault-tolerance algorithms for reconfigurable nano-crossbar arrays. ACM Comput. Surv., 2018, 50(6):Article No. 79. DOI:10.1145/3125641.
[10] Ariga K, Lee M V, Mori T, Yu X, Hill J P. Twodimensional nanoarchitectonics based on self-assembly. Adv. Colloid Interface Sci., 2010, 154(1/2):20-29. DOI:10.1016/j.cis.2010.01.005.
[11] Yan H, Choe H S, Nam S, Hu Y, Das S, Klemic J F, Ellenbogen J C, Lieber C M. Programmable nanowire circuits for nanoprocessors. Nature, 2011, 470(7333):240-244. DOI:10.1038/nature09749.
[12] Yuan B, Li B. A fast extraction algorithm for defect-free subcrossbar in nanoelectronic crossbar. ACM J. Emerg. Technologies Comput. Syst., 2014, 10(3):Article No. 25. DOI:10.1145/2517137.
[13] Sasikumar D, Kumar A. A novel defect tolerance scheme for nanocrossbar architectures with enhanced efficiency. Micromachines, 2018, 10(1):Article No. 14. DOI:10.3390/mi10010014.
[14] Yuan B, Li B, Chen H H. Defect-and variation-tolerant logic mapping in nanocrossbar using bipartite matching and memetic algorithm. IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2016, 24(9):2813-2826. DOI:10.1109/TVLSI.2016.2530898.
[15] Hung W N N, Gao C, Song X, Hammerstrom D. Defect-tolerant CMOL cell assignment via satisfiability. IEEE Sens. J., 2008, 8(6):823-830. DOI:10.1109/JSEN.2008.923261.
[16] Sait S M, Arafeh A M. Reconfiguration-based defecttolerant design automation for hybrid CMOS/nanofabrics circuits using evolutionary and non-deterministic heuristics. Arab. J. Sci. Eng., 2015, 40(9):2515-2529. DOI:10.1007/s13369-015-1682-1.
[17] Chen D, Xia Y, Wang Z. Stuck-at-close defect propagation and its blocking technique in CMOL cell mapping. Microelectron. J., 2018, 72:100-108. DOI:10.1016/j.mejo.2017.12.004.
[18] Morgul M C, Tunali O, Altun M, Frontini L, Ciriani V, Vatajelu E I, Anghel L, Moritz C A, Stan M R, Alexandrescu D. Integrated synthesis methodology for crossbar arrays. In Proc. the 14th IEEE/ACM Int. Symp. Nanoscale Architectures, Jul. 2018, pp.91-97. DOI:10.1145/3232195.3232211.
[19] Xu Q, Chen S, Geng H, Yuan B, Yu B, Wu F, Huang Z. Fault tolerance in memristive crossbar-based neuromorphic computing systems. Integr. VLSI J., 2020, 70:70-79. DOI:10.1016/j.vlsi.2019.09.008.
[20] Kule M, Rahaman H, Bhattacharya B B. Maximal defectfree component in nanoscale crossbar circuits amidst stuck-open and stuck-closed faults. J. Circuits Syst. Comput., 2019, 28(11):Article No. 1950180. DOI:10.1142/S0218126619501809.
[21] Chu Z, Xia Y, Hung W N N, Song X, Wang L. Timing-driven logic restructuring for nano-hybrid circuits. Int. J. Electron., 2013, 100(5):669-685. DOI:10.1080/00207217.2012.720945.
[22] Zha X, Xia Y. Defect-tolerant mapping of CMOL circuits with delay optimization. In Proc. the 30th ACM Great Lakes Symp. VLSI, Sept. 2020, pp.451-456. DOI:10.1145/3386263.3406944.
[23] Cong J, Xiao B. Defect tolerance in nanodevice-based programmable interconnects:Utilization beyond avoidance. In Proc. the 50th ACM/EDAC/IEEE Des. Autom. Conf., May 29-June 7, 2013, Article No. 9. DOI:10.1145/2463209.2488745.
[24] Sait S M, Arafeh A M. Cell assignment in hybrid CMOS/nanodevices architecture using tabu search. Appl. Intell., 2014, 40(1):1-12. DOI:10.1007/s10489-013-0441-9.
[25] Matrosova A, Ostanin S, Chernyshov S. Finding false paths for sequential circuits using operations on ROBDDs. In Proc. the 24th IEEE Int. Symp. On-Line Testing and Robust System Design, July 2018, pp.240-242. DOI:10.1109/IOLTS.2018.8474213.
[26] Brglez F, Bryan D, Kozminski K. Combinational profiles of sequential benchmark circuits. In Proc. IEEE Int. Symp. Circuits and Systems, May 1989, pp.1929-1934. DOI:10.1109/ISCAS.1989.100747.
[1] Ji-Zan Zhang, Zhi-Min Gu, Member, CCF, Ming-Quan Zhang, Member, CCF. Reducing the Upper Bound Delay by Optimizing Bank-to-Core Mapping [J]. , 2016, 31(6): 1179-1193.
[2] Zhu-Fei Chu (储著飞), Student Member, IEEE, Yin-Shui Xia (夏银水), and Lun-Yao Wang (王伦耀). Cell Mapping for Nanohybrid Circuit Architecture Using Genetic Algorithm [J]. , 2012, 27(1): 113-120.
Full text



[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] Wu Enhua;. A Graphics System Distributed across a Local Area Network[J]. , 1986, 1(3): 53 -64 .
[4] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[5] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[8] 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 .
[9] Xu Xiaoshu;. Simplification of Multivalued Sequential SULM Network by Using Cascade Decomposition[J]. , 1986, 1(4): 84 -95 .
[10] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .

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