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

amplitude of all the superposed signals sent by the nodes above shows the number
of its preceding elements in the list.
Another special case of finding the all prefix sum routine would be the
summation routine, where the summation of all nodes is found and stored in
constant time. This is equivalent of all the prefix sum routine when performed at
the very last node in the list. All the processing elements send downwards a signal
with an amplitude equal to the value they have stored. Utilizing the superposition
property of spin-waves, the last node receives the ''sum'' of the input values in
constant time. This routine has been used in implementing the graph formation of
the POMSA algorithm [5] described in Chapter 14. Note that the all prefix sum
routine can be performed on at most N inputs, on a single column of the
reconfigurable mesh. However, the summation routine can have as many as N 2
inputs, mapped to all the nodes of the reconfigurable mesh. In that case, all the
nodes send out their signals and the superposed signal or the ''sum'' received by all
the nodes in O(1) time.
Since it is not possible to send signals downwards in a crossbar or in a fully
interconnected cluster, the all prefix sum routine can not be implemented on these
two architectures. However, the special case of finding the summation of all
inputs, for at most N inputs, can be implemented on one single column of a
crossbar and on a fully interconnected cluster.
As another application example, consider the problem of creating a histogram
of input values where all such values are in the range of 1. N and each value
represents a type. We show that this problem can be solved in O(1) time on a spin-
wave reconfigurable mesh. Assuming that the number of inputs is at most N 2 , the
inputs can be mapped to processing nodes. There are two approaches to store
the result of the histogram. The first one is to choose one node of each type to be
the representatives of that type. We can find the first of each type in the list to
represent its type, using the routine explained in the previous section. The second
approach, which we choose, is to let each node keep track of the number of nodes
from its type.
The next step is to count the number of times each value has been repeated in
the list and store the sum at each (or the representative) node. As explained above,
this problem is a subset of finding the all prefix sum routine. In this case all the
nodes send a value of ''1'' and the result would be the number of inputs in that
category.
Note that this routine should be performed on each type of input; however,
using different frequencies, these separate routines can be done simultaneously. In
other words, each type's sender and receiver are tuned on a distinct frequency.
Due to superposition characteristic of the waves, each node receives the sum of 1 s
sent on its tuned frequency, which is the number of nodes of that type.
8.2.4. Shifting the Elements of a List
In several applications, the elements of a list needed to be shifted. The shifting
operation can be implemented on a row or a column of a spin-wave reconfigurable