Information Technology Reference
In-Depth Information
techniques that can be used for routing and design of fast algorithms on these
spin-wave architectures. We also present a set of application examples to illustrate
the operation of the proposed generic parallel techniques on these new spin-wave
models.
8.2. PARALLEL ALGORITHM DESIGN TECHNIQUES
In this section, we present three generic parallel processing techniques that are
mainly designed for spin-wave reconfigurable meshes. The implementation of
some of these techniques using spin-wave crossbar and fully interconnected
clusters is also briefly discussed. When using these architectures, one should
take into consideration the fact that two different types of data detections are
possible at the nodes. Once the spin waves are detected by the receiver, the
transmitted data can either be digitized or left as analog.
In analog detection mode, the receiver detects a voltage that is the super-
position of multiple waves. For example, if ten waves are sending a ''1,'' then their
analog sum through their cumulative amplitude is computed instantly as 10. Also,
this property can be used to compute logical functions as described previously. In
digital detection mode, this value is digitized to just a ''1,'' and then the
computations are continued digitally. In the following section, the generic parallel
techniques are presented [1, 2].
8.2.1. Find the Maximum/Minimum
To find the maximum or minimum of O(N 2 ) inputs (with a maximum value of 2 N )
on a reconfigurable mesh, we first assign each value to a processing node on the
grid points of the reconfigurable mesh. Next, each node checks its most significant
bit (MSB). If MSB is 1, the node broadcasts a ''1'' to all the other processing
nodes. If the MSB is 0, on the other hand, the processing node listens to the
channel and gets disabled if it detects a 1 on the bus. At the next step, the nodes
check their next most significant bit. This procedure is repeated for all the bits.
Since the maximum value of the inputs is N, this procedure takes O(log N) time [3].
If the number of inputs is at most N, the minimum and maximum numbers can be
found in O(1) as presented in [4].
Finding the minimum is similar to finding the maximum except that in the
case of MSB=1, the node broadcasts a ''1'' and at the same time listens to the
channel. If there is a 1 on the bus, that node becomes disabled.
The same implementation technique applies when using one single column of
a spin-wave crossbar. In that case, the max/min of at most N inputs can be found
using the N processing units. One of the columns would be used as the shared
medium, where nodes broadcast their MSB. All the switches on that column must
be turned on to connect the processing units to the shared bus.
This algorithm can also be implemented on a fully interconnected cluster in a
similar fashion, except that in the fully interconnected cluster, there are no
 
Search WWH ::




Custom Search