Information Technology Reference
In-Depth Information
14.4. PO-MSAG FORMATION FOR O(N) VARIATION
The nature of the problem is the same (N sequences of length L on a reconfigur-
able mesh). However, the data considered in this section can have as many as N
different variations.
14.4.1. O(N) Variables on the Spin-Wave Version
Before we begin, we must make some assumptions. First, the size of our spin-wave
reconfigurable mesh must be increased to 2N 2L. This is still acceptable because
it is only a constant increase. Next, we must assume that all nodes can access their
own row index very quickly in constant time. Finally, we assume that when the
nodes are mapped initially, they are done so in such a way that there is an empty
column to the right of each data column. These empty columns will be known as
graph columns.
Initial Mapping. This step is exactly the same as shown previously.
Neighbor Recording. This step is also exactly the same as shown previously.
Node Elimination. This step is exactly the same as shown previously as well.
Graph Formation. We will form the graph and store it in the graph columns.
The overall idea here is that we place each representative node in the graph
column to its right and all its right connections beneath it.
A. Counting disabled nodes. When we store the representative nodes in the
graph columns, we need to leave the correct number of empty graph column
slots beneath each representative node. These empty slots will be used to store
the right neighbors of the representative nodes as well as of that of their
respective disabled nodes. Therefore, we must first count the number of disabled
nodes of each type within a column. To do this, we utilize a property of
spin waves: superposition. The main idea behind superposition is that when
nodes transmit signals in the same frequency, the signals will superpose in
amplitude when they meet. So we can have all disabled nodes of each type
transmit a signal with amplitude 1 in their own frequencies and have their
respective representative node receive in its own frequency. We tell the
representative node to keep receiving for a constant, certain amount of time
(the time taken for a signal to propagate through the entire channel). When the
representative is done receiving, it will have received the total amplitude of all
the superposed signals sent by its disabled nodes. This amplitude received by the
representative node is the number of its disabled nodes. We use our third column
again as an example. The two disabled A nodes send up signals with amplitude 1
in their own frequency. The superposed signal of amplitude 2 is received by the
representative A (Figure 14.8).
 
Search WWH ::




Custom Search