Information Technology Reference
In-Depth Information
switches to be set. The nodes are all connected to the shared medium, where they
can broadcast their MSB or receive signals from other nodes.
Note that on all of the spin-wave architectures, this whole routine can be
performed simultaneously on disjoint sets of input, using different frequencies for
each set. This cannot be done on a standard VLSI reconfigurable mesh due to the
conflicts on the buses. Finding the maximum/minimum routine is used in several
applications. For instance, it is used in the labeling algorithm and finding the
nearest neighbor, explained in Chapter 19.
8.2.2. Find the First/Last in the List
In many applications, we need to find the first or last element of a list. In geometric
algorithms, for instance, this operation is useful where we find the extreme points
of a figure. The convex hull algorithm presented in Chapter 19 and the graph
formation for multiple sequence alignment algorithms, presented in Chapter 14,
are application examples that use this routine.
To find the first or last element of at most N inputs, the first step is to store the
inputs in the processing elements in a column. We find the local topmost nodes on
that column by making each node send a signal downward. This procedure begins
by turning off all the switches above each node (disconnect the channel) to force
the signal sent by each node downwards. Then all nodes simultaneously send out a
signal downward and turn on all switches (reconnecting the channel), thereby
lettings all signals pass through the bus. Each node that receives a signal will
become disabled. As the result, the only active nodes are the local topmost nodes
that have not received a signal. This procedure is performed in O(1) time. An
example is shown in Figure 8.1, where the first A in the list is found by disabling
the rest of the As.
If different sets exist among the inputs, it is possible to find the first element of
each set using frequency division multiplexing. For instance, in the above example,
there are two sets (As and Bs). As shown in Figure 8.2, we find the first A and B in
the list simultaneously by performing the routine on two different frequencies for
A and B.
Unlike a reconfigurable switch that can be controlled in four different direc-
tions, a crossbar switch has just two possible statuses: ''on'' or ''off.'' Therefore, it is
not possible to force the wave in only one direction. As a result, the first/last routine
cannot be implemented on a crossbar in a similar fashion as a reconfigurable mesh.
A
A
A
B
B
B
A
A
A
A
A
A
Figure 8.1. Finding the first element of a list.
 
Search WWH ::




Custom Search