Su_Yehua.pdf (1.46 MB)

Download file# Defect Tolerant Logic Implementation onto Nanocrossbar-Based Architectures

thesis

posted on 21.02.2013, 00:00 by Yehua SuCrossbar-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.