Defect Tolerant Logic Implementation onto Nanocrossbar-Based Architectures

Crossbar-based architectures are promising for the future nanoelectronic systems. Nanocrossbar logic implementation emerges as a new fundamental issue, because massive defects, resulting from self-assembly fabrication process, introduce irregular topological constraints on the otherwise regular nanocrossbars. Therefore, defect tolerance techniques become crucially important for the realization of nanocrossbar potentials. As an emerging challenge, defect-tolerant logic implementation onto nanocrossbars turns out to be a hard problem. It is therefore important to model the defect-tolerant logic implementation problem, analyze the cost and tradeoffs, and explore efficient defect tolerance methodologies. In this dissertation, we first study the defect tolerant logic implementation problem by modeling it in a probabilistic way, so as to analyze the computational complexity and exploring the design quality. Both logic functions and nanocrossbars can be mathematically modeled by matrix model. The mapping based approach is then formulated with a matrix mapping problem, with the goal of finding a mismatch-free mapping (by permutating rows and columns of the matrices) between the logic function and the crossbar matrices. This way, the implementation process is translated into a constraint satisfiability problem with the complexity of NP-completeness. In order to quantitatively understand the defect-tolerant logic implementation and identity the design tradeoffs, beside a probabilistic view from the solution density point of view over the collection of mapping space, design quality is examined furthermore in a more precise way using mismatch number distribution over all the implementation possibilities. The mismatch number distribution reveals the probability that a valid logic implementation exists and identifies the cost for finding a valid implementation. The number of mismatches turns out to be possible to be well modeled in probabilistic approaches, and the mismatch number distribution follows Normal/Poisson and Hypergeometric distributions, respectively. With the knowledge of design quality indicated by mismatch number distribution, yield is analyzed and modeled when a large number of crossbars, each having a different defect pattern, are considered. Yield of nanocrossbars, different from traditional manufacturing yield in CMOS, depends on logic implementation algorithms as well as allowed runtime. Due to the high defect rate in nanocrossbars, the implementation process could take prohibitive runtime. Therefore we propose a practical concept of runtime-constrained yield, and identify the tradeoffs between yield and the impacting factors: runtime, defect rate and hardware cost. In parallel to the analytical work on the modeling of defect tolerance quality, we propose low-cost aggressive approaches to further improve defect tolerance capability, namely logic morphing and fine-grained logic hardening. These novel approaches could be applied on top of the logic mapping technique. Logic morphing exploits the various equivalent forms of a logic function to tolerate defects, while logic hardening adds calculated redundancies to a logic function to make the hardened logic function inherently defect tolerable. Each approach explores an additional dimension of freedom in achieving defect tolerance, and both are orthogonal to and compatible with the existing mapping-based approach. In summary, all three approaches (logic mapping, morphing and hardening) are orthogonal to each other, and can be exploited simultaneously without offsetting each other's performance. We propose an integrated algorithmic framework, which employs mapping, logic morphing and logic hardening simultaneously, and efficiently searches for a successful logic implementation in the combined solution space. Simulation results show that the proposed schemes boost defect tolerance capability significantly with many-fold yield improvement, while having no extra runtime over the existing approach of performing mapping alone.