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

Freq
A

Freq
B

A

B

A

A

Figure 8.2. Finding the first element of different sets.

This implementation does not apply to a fully interconnected network either, since
in that symmetric architecture, there is no notion of first or last.

8.2.3. Find the All Prefix Sum
To find the all prefix, one should compute the sum of the first j elements in an
array and store the sum in the jth element. Using this algorithm, the sum of all the
input values will be computed and stored in the last element. Here we show how
this operation is performed in O(1) time on spin-wave architectures.
To perform the all prefix sum routine for most N inputs, first we map the
inputs to the processing nodes on one column of the spin-wave reconfigurable
mesh. At the beginning, all of the switches are turned on. Then, each node sends a
signal with an amplitude equal to the value it has stored and immediately turns off
the switch above it, directing the generated wave downwards. Note that for
synchronization purpose, each node generates its spin-wave signal after a short
period of time to compensate the spin-wave propagation delay in the ferromag-
netic channel. This short period of time has to be greater than or equal to the
distance between adjacent nodes divided by the speed of spin waves, which is in
the order of 10 9 /10 4 =10 13 . Considering the fact that the frequency is in the
order of GHz or even THz, this whole process is considered as constant time. The
sum of previous values can be found at each element by using the superposition
property of spin-waves. The main idea behind superposition is that when nodes
transmit signals on the same frequency, the signals will superpose in amplitude
when they meet. The amplitude of the superposed wave received by each node will
be the prefix sum on that node. This routine is used in the graph formation
algorithm for partial-order multiple sequence alignment, presented in Chapter 14.
A special case of finding all prefix sum routine is counting the number of
elements preceding a certain element in the list. To solve this problem, all the
nodes transmit a signal downwards with an amplitude of 1. In each node, the total