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

0.9

0.273

A0

o3

0.808

0.9
0.9

0.191

B0
C0

0.727

a b

o2 Out

o1

0.273

0.9

D0

o4

Figure 10.13. Example circuit.

o2, o3 and o4 and one primary output marked as out. The probability of each of
these outputs being logic 1 are manually computed, given the defect rate of 0.001.
The NAND and NOR gates marked a and b, respectively, form a subcircuit with
output o2. The probability of o2 being logic high is computed to be 0.808, whereas
the primary output of the circuit in Figure 10.13 has a 0.727 probability of being
logic 1. These probability values indicate that the reliability of a circuit may be
very different from the reliability of the smaller sub-circuits that compose the
circuit. For large nanoscale circuits that may consist of millions to billions of
devices, this difference will only widen. Hence, analyzing smaller sub-circuits does
not accurately reflect the impact of each nanoscale process technology on the
reliability of large circuits.
On a practical note, Table 10.3 indicates the exponential state space increase
when the input width of a ripple carry adder is increased. It has been shown that
for adders with width 4, if the inputs have nonzero probability of being both

stimulated and nonstimulated at the same time, the analysis becomes intractable
in terms of memory for even high-end workstations.
To alleviate this scalability problem, [69] presents a scalable technique. The
basic concept in this technique is to iteratively build and analyze probabilistic
gate-level models and propagate the probability values through the circuit
according to the logic dependencies. This concept is dissimilar to the direct
PMC or PTM approach because it does not build a monolithic probabilistic model
or PTM for the circuit. Instead, it folds space into time by iteratively computing

Z

TABLE 10 . 3 . State Space Size for Multibit Adders
Design DTMC states MTBDD nodes

1 bit 847 618

2 bit 10191 1455

3 bit 84943 2580

4 bit 682959 3965

5 bit 5467087 5644

6 bit 43740111 7579

7 bit 349924303 9806

8 bit 2799397839 12307