Information Technology Reference
In-Depth Information
TABLE 14 . 1 . Time Analysis: Spin Wave
1: Neighbor Recording
O(1)
2: Node Elimination
O(1)
3: Graph Formation
O(1)
14.4.2. O(N) Variables on the Electrical Version
The VSLI reconfigurable mesh architecture shares many similarities with the spin-
wave reconfigurable mesh; however, multiple nodes cannot send messages at the
same time. This poses major challenges when the application is communication-
intensive. The graph formation algorithms we presented in the previous section,
was optimized for a spin-wave reconfigurable mesh where we could benefit from
different properties of waves such as simultanious multiple data transmission and
superposition. The graph formation algorithm for the VLSI reconfigurable mesh
is exactly the same as the one we presented for the constant number of variables.
The steps are performed for each type of node sequentially.
Initial Mapping. As explained in the constant number of variables, this step is
done in constant time.
Neighbor Recording. In this step, as explained previously, each node's right
neighbor is stored in its second memory slot in constant time.
Node Elimination. The elimination process will again be handled via disabling
the repeated nodes in each column, as discussed previously. This step is
done sequentially for each type of node, so it takes O(N) time.
Graph Formation. This step is also done exactly the same as memory update
step in constant number of variations case. Since this step is done
sequentially for each of O(N) type of nodes, it is performed in O(N).
Table 14.2 lists the time complexities of each stage of the process. The total
time complexity of the process will be O(1)+O(N)+O(N)=O(N).
To summarize the time complexities for both arbitrary variation and constant
variation of the PO-MSAG formation problem solved with two reconfigurable
mesh architectures is Table 14.3.
TABLE 14 . 2 . Time Analysis: VLSI
1: Neighbor Recording
O(1)
2: Node Elimination
O(N)
3: Graph Formation
O(N)
Search WWH ::
Custom Search