DNA SEQUENCE MATCHING AT NANOSCALE LEVEL - Bio-Inspired and Nanoscale Integrated Computing - page 381

A A

A

* * *

A

A A

A A A

Figure 14.5. Disabling nodes using spin wave.

We perform this procedure with all nodes of all types simultaneously, each
type on its own frequency. This process also has a run time of O(1) because in the
spin-wave mesh, similar nodes can communicate to each other in constant time.

M EMORY U PDATE . Now, we must update the memory of the remaining nodes.

A. We first turn off all switches below each node to force all sent signals
upward. This process takes constant time.
B. Then we ask all disabled nodes whether or not their right neighbor (at
memory slot 2) is an A. If so, that disabled node will send a signal upward
to its respective representative node and turn on all switches. This part still
runs at constant time since all disabled nodes can perform this step
simultaneously.
C. Finally, the representative node receives that signal and checks its right
neighbor memory (memory slots 2-6) for an A. If an A is not already
there, the representative node will place an A in the next available slot.
This process take constant time since at most, the representative node will
need to look all five of its right neighbor memory slots.
D. We repeat steps A, B, and C four more times, each time requesting the
disabled nodes to check for a different right neighbor: T, G, C, and *.
Since steps A, B, and C are constant, 4*O(1) is still O(1). All disabled
nodes of each type can perform these steps simultaneously because each
type can communicate in its own frequency. Thus the overall performance
of the Memory Update stage is still O(1) (Figure 14.6).

A T

23456

A

*

*

1 1 23456

C G *

G

*

1 23456 1 23456

T A

23456 1

Figure 14.6. Memory space after the memory update stage.