FAULT- AND DEFECT-TOLERANT ARCHITECTURES FOR NANOCOMPUTING - Bio-Inspired and Nanoscale Integrated Computing - page 272

defective. One of the easiest test circuits proposed for such purposes is a counter
circuit [21]. Counter circuits with thresholds of t can indicate 0,1,2, ,t or more

than t defects. Since the lowest element of the structural hierarchy are regions
(composed of 8 PEs), the threshold of such a test circuit may be set to 8.
Another set of simple circuits that can be used for this purpose are linear
feedback shift registers (LFSRs). LFSRs are used widely in built-in self test (BIST)
of RAMs. These can be configured on MUs and run autonomously with sets of
inputs. parallel signal analyzers (PSAs) are also configured on the MUs. These
PSAs are used as parallel-to-serial compression circuits to avoid testing large
number of pseudo-random vectors generated by the LFSRs. The compression of a
number of patterns using a PSA is called a signature. If there are signature
mismatches, the LFSRs may be split into smaller units and configured on each
region of the specific MU instance. Note that even then if there are no signature
mismatches, it does not mean that the constituent nodes are defect free. This is due
to a non-zero probability of aliasing. A way to minimize this aliasing problem is to
use maximal-length PSAs and to frequently compare the signatures with the
expected values [27].
The test circuits discussed here are just a small subset of the different test
circuits that can be used to compute the probability of PEs being defective. The
crossbar junction failure probability can be computed using these probabilities.
Note that determining the junction failure probability is required for both the
defect mapping and structural redundancy insertion methodologies, since logic
functions need to be mapped to the crossbar-based PEs in both the cases.

y

10.3.2.2. Defect-Mapping Technique. The proposed nondeterministic de-
fect-mapping technique [23-25] is based on a variant of the RPF broadcast scheme
[22] and on the defect-mapping methodology proposed in [21]. Simple test circuits
from [21] are configured physically on the nanofabrics to determine the prob-
ability of the crossbar junctions being defective. These defect rates are used in
determining the probability of successfully configuring all the PEs with the same
broadcasting functionality. Once this configuration probability is computed,
probabilistic models representing such PE-based nanofabrics are constructed
and the broadcast-based algorithm is used to determine the reachability graph
of each PE from the vias.
The broadcast-based algorithm used is a modification of the deterministic
algorithm proposed in [22]. The algorithm has been modified such that defect
maps represented by probabilistic broadcast trees can be generated, hence
reflecting the non-deterministic defects in molecular nanofabrics. In this algo-
rithm, the probability of a PE being reached depends on the probability of the
packet reaching the previous PE that forwarded the packet and the probability of
the interconnect on which the packet was transmitted being defect free. The
methodology also stores the via number from which a PE is reachable with highest
probability, since this facilitates the physical logic configuration of the fabric at a
later stage if there is more than one available via. Since the methodology applies
this modified broadcasting algorithm on a nanofabric model, the dynamics of the