Algorithms For Defect-tolerance Design In Nano-crossbar Architectures

The conventional CMOS (complementary metal oxide semiconductor) integrated circuit is rapidly approaching its realistic limits in both physical limits and technological side. Emerging nanoelectronic devices and the corresponding nano-architecture technologies are considered to supplement (short-term view) or even replace (long-term view) CMOS technology. Nanoelectronic technology is expected to achieve much higher device density (1012/cm2) and operation frequency (over100gigahertz). It makes it possible to further extend Moore’s law beyond CMOS, and shows the tremendous opportunities for future computing systems.However, challenge always parallels to the chance. The design and fabrication of nanoelectronic system are facing a series of new questions, such as extremely high device defect density, local interconnection, novel logical expression, and high system transient error rate during runtime, etc. The understanding of a series of new challenges provides the initial contribution on how to solve the fundamental issues of building functional nanoelectronic systems. Essentially, the extremely small size of the nanoelectronic device and the serious unreliability introduce important transformation for design optimization, and present difficult challenges in nanoelectronic science and engineering.In recent years, the design for reliability of nanoelectronic systems has emerged as a central concern in the fields of EDA (electronic design automation) and reliability testing, and the researches mainly focus on two aspects:defect-tolerant design and fault-tolerant design. Faced with such a high defect density of nano-architecture, a future nano-chip designing and fabricating industry definitely needs carefully crafted effective and efficient defect-tolerant design techniques. Two promising design flows are suggested for logic function implementation in nanoscale crossbar architectures:application-dependent design flow and application-independent design flow. In application-dependent design flow, the key step is to directly find a mapping from the function to the crossbar with considering the defects. In application-independent design flow, the key step is to extract the maximum universal defect-free subcrossbar within the original defective crossbar first and then any function can be directly mapped to the defect-free subcrossbar without considering the defects. This thesis mainly focuses on the related problems and algorithms on the both design flows, and the main contribution and the innovation are summarized as follows:1. A systematic study of problems and algorithms on DTLM (defect-tolerant logic mapping) for crossbar-based nano-architecture is presented. The key step in application-dependent design flow is DTLM. The previous work related to DTLM is well investigated in this thesis. And on this basis, models and algorithms for DTLM are exploringly studied.1) On the algorithm research:in view of the mapping success rate of previous greedy DTLM algorithm is very low, a concept of diversity mapping is proposed, and three DTLM algorithms based on diversity mapping scheme are presented. As the experiment results show, the proposed algorithms can achieve several or ten times higher mapping success rates compared with the previous greedy DTLM algorithm, especially superior in large scale problems.2) On the model research:a rationality weighted coverage optimization model for DTLM is proposed by considering details of logic functions in DTLM. The new model is proved by experiments that it can calculate the number of crossbar modules required to implement the given logic function more accurately than the previous model.2. A new memetic algorithm with fitness approximation for DTLM is proposed. The problem of DTLM has been modeled as SIP (Subgraph Isomorphism Problem), which is a well-known NP-complete combinatorial search problem. The problem of DTLM is first modeled as a combinatorial optimization problem through introducing Maximum-Bipartite-Matching (MBM). Then, a new memetic algorithm with fitness approximation (MA/FA) is proposed to solve the optimization problem efficiently. In MA/FA, a new greedy re-assignment local search operator, capable of utilizing the domain knowledge and information from problem instances, is designed to help the algorithm find optimal logic mapping with consumption of relatively lower computational resources. In addition, a fitness approximation method is adopted to reduce the time consumption of fitness evaluation dramatically and a hybrid fitness evaluation strategy that combines the exact and approximation fitness evaluation methods is presented to balance the accuracy and time efficiency of fitness evaluation. The effectiveness and efficiency of proposed methods are testified and evaluated on a large set of benchmark instances of various scales.3. A systematic analysis of the existence probability of defect-free subcrossbar within nano-crossbar is presented. The key step in application-independent design flow is the extraction of universal defect-free subcrossbar. The subcrossbars are called universal because the sizes (k) of them are identical for all nano-chips fabricated in the same manufacturing environment (similar defect density p). In order to obtain a good balance between utilization and yield, the manufacturer must know how the size of subcrossbar affects the yield:given crossbar sizes n and defect density p, we need to know the existence probability of the defect-free subcrossbar of size k, which can only be obtained experimentally. Based on recursion, a way for analyzing the existence probability Pexist of the defect-free subcrossbar within the defective nano-crossbar is presented, and the compact upper and lower boundaries for the existence probability are given. The correctness of the theoretical analysis is further validated by simulation experiments.4. A fast extraction algorithm for defect-free subcrossbar in nanoelectronic crossbar is proposed. By mixing the key ideas from two state-of-the-art algorithms, a improved extraction algorithm with lower time complexity is first presented. Then, a fast extraction algorithm is proposed by cutting down the number of major loops considerably. Compared with the current most effective algorithm which improves the solution quality (size of defect-free subcrossbar obtained) at the cost of time complexity O(n3), the time complexity of the proposed fast algorithm is proved to be O(n2). On the basis of a large set of instances with different sizes and defect densities, simulation experiment results show that the proposed algorithm can produce solutions with similar quality as that of most effective algorithm, while the runtime is reduced to about1/3to1/5.5. A new evolutionary algorithm with structure mutation for the defect-free subcrossbar extraction is proposed. The problem of extracting the maximum defect-free subcrossbar corresponds to MBBP (maximum balanced biclique problem), which is well-known NP-hard. A new algorithm for the MBBP, Evolutionary Algorithm with Structure Mutation (EA/SM), is proposed. In the EA/SM framework, local search complemented with a repair-assisted restart process is adopted. A new mutation operator (SM) is proposed to enhance the exploration during the local search process. The SM can change the structure of solutions dynamically while keeping their size (fitness) and the feasibility unchanged. It implements a kind of large mutation in the structure space of MBBP to help the algorithm escape from local optima. An MBBP-specific local search operator is designed to improve the quality of solutions efficiently. Besides, a new repair-assisted restart process is introduced, in which the Marchiori’s heuristic repair is modified to repair every re-initialized solution. The proposed algorithm is evaluated on a large set of benchmark graphs with various scales and densities. Experimental results show the advantages of EA/SM and the effectiveness of the structure mutation operator and the repair-assisted restart process.The contributions of this thesis provide important algorithms and theories basis for the verification of future nanoelectronic system EDA (electronic design automation) tools.