PARALLEL COMPUTING WITH SPIN WAVES - Bio-Inspired and Nanoscale Integrated Computing - page 235

most important trade offs are between granularity and reliability [12] and between
redundancy and reliability [13]. It is shown that to make nanoscale systems reliable,
different degrees of redundancy need to be applied at different granularity levels (i.e.,
gate and reconfigurable logic block levels) [13].
Several designs and techniques have been studied to increase the tolerance of
nanoscale architectures to both transient and fabrication defects [14-31]. For
instance, a number of redundancy schemes, including von Neumann's multi-
plexing logic, N-tuple modular redundancy, and interwoven redundant logic, have
been presented in [20]. In addition, a new fault-tolerant design approach based on
coding theory has recently been proposed at HP Labs [21]. In this approach, by
using a crossbar architecture and adding 50% more wires, nanoelectronic circuits
with nearly perfect yields can be fabricated even though the probability of broken
components is high. To implement fault-tolerant quantum computers, quantum
error correcting codes are being developed and elementary quantum gates are
being constructed to form the basic building block of these computers [22].
Furthermore, three logic mapping algorithms with defect avoidance have been
presented in [23] to circumvent clustered defective crosspoints in nanowire
reconfigurable crossbar architectures.
Fault tolerance is achieved in all these architectures by adding some level of
redundancy. While redundancy is needed for reliable computation, economic
constraints also need to be considered in choosing the redundancy factor [11]. The
advantage of the fault-tolerant scheme presented in this chapter as compared to
the other methods mentioned previously is in its smaller degree of required
redundancy. In this section, we concentrate on the fault-tolerance features of a
spin-wave nanoscale crossbar architecture. We show that by employing the
parallel features of this architecture the amount of the spatial redundancy required
for a fault-tolerant design is significantly reduced [9]. In the following section, we
briefly talk about fault diagnosis for our spin-wave crossbar and then present a
simple fault recovery scheme.
F AULT D IAGNOSIS . There are many different ways in literature to detect a
defective switch [24-28]. Here we choose a very simple method, in which an
acknowledgment is sent from the receiver back to the sender for each transmis-
sion. If the sender does not receive an acknowledgment from the receiver after a
fixed amount of time, existence of a fault has been determined. The sender then
tries to resend the message through another route.
F AULT R ECOVERY . In the example presented earlier where input 3 was sending
to output 6, assume that the switch s(3,6) is defective. So now after node 3 sends a
message to node 6, it does not receive the acknowledgement. Therefore, sender 3
will attempt to resend the message to node 6 through a new path. There are several
schemes to reroute the message. The method we employ to reroute the path is
simple. It is basically performed by adding an extra column of switches to the
crossbar. In case of a fault on any of the switches on row i, the input, using the
extra column, connects with the spin-wave bus path on row i+1 (or row i 1ifin