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

physical broadcast are mimicked in the model. Note that the broadcast-based part
of the defect-mapping technique is executed off-line, i.e., on an external system.
The methodology also partitions the nanofabric models to decrease the
computational complexity of the off-line probabilistic broadcasting algorithm.
A molecular nanofabric is partitioned into equal-sized smaller units such that the
algorithm can be run simultaneously on all the units. This implies that in certain
cases some of the PEs may be a part of more than one unit and hence can be
reached from more than one via. The defect-mapping mechanism pin-points the
via from which a specific PE can be reached with the highest probability. If the
highest probability value of reaching a PE from any of the vias is lower than a
user-specified threshold, that PE is marked defective.
In summary, the methodology combines the good features of test circuit-
based and broadcast-based defect mapping techniques. The differences between
this methodology [234-25] and the methodologies in [21, 22] are as follows:
[21] uses extensive on-line testing to improve the recovery metric whereas
this methodology only uses limited on-line testing.
[22] proposes a deterministic broadcast algorithm that has been extensively
modified to a non-deterministic broadcast algorithm.
[23] generates on-line defect maps by physically broadcasting test packets in
the nanofabrics whereas in the methodology discussed such broadcasts are
mimicked in the nanofabric models.
The discussed methodology uses state space partitioning techniques on the
nanofabric models to improve off-line computational complexity. This was
not considered in both [21, 22].
10.3.2.3. Hierarchical Redundancy Insertion Methodology. The pro-
blem of mapping logic onto ultra-dense nanofabrics has been handled well in
[26]. In this methodology, the same procedure is used to map covers of different
designs onto the structural hierarchy of the nanofabric models. Note that a cover
is the decomposition of a monolithic data flow graph (DFG) of a design, where a
DFG of a design represents the behavior of a design. Since there can be more than
one way of decomposing a DFG for a system into a cover, the DFG of a system
may have more than one cover. Figure 10.5 shows one of the possible covers for an
auto regression (AR) filter design.
This procedure is extended so that behaviorally redundant systems can be
mapped onto structurally redundant molecular nanofabrics. Redundancy can be
added to the covers by replicating the nodes. Figure 10.6a shows how a non-
redundant cover with a single flow changes to a cover with two flows when an
operation (Node 1) is triplicated. Similarly, structural redundancy can be inserted
either at the crossbar level; by adding columns or at any of the three tiers of the
nanofabric hierarchy. Figure 10.6b shows TMR configurations for the different
structural hierarchies. The TMR configurations are representative examples of
structurally redundant fault-tolerant configurations. The discussed hierarchical