DNA SEQUENCE MATCHING AT NANOSCALE LEVEL - Bio-Inspired and Nanoscale Integrated Computing - page 387

TABLE 14 . 3 . Summarized Time Analysis
Arbitrary variation Constant variation

VLSI O(N) O(1)

Spin Wave O(1) O(1)

14.4.3. PO-MSAG on a Hierarchical Multiscale
Reconfigurable Mesh
The algorithm we presented works for a limited data size of O(NL), for N sequences
of length L. In some situations, however, the database size might be larger than this
limit. For instance, the sequences might be longer than L or there might exist more
than N sequences depending on the nature of the data and the size of the dataset.
Let's assume we have a reconfigurable mesh of a fixed N L size, and the dataset
size exceeds the N L limit of the reconfigurable mesh. We can approach this
problem by using multiple N L reconfigurable meshes and connecting each
module in a multiscale fashion. We propose using the Hierarchical Multi-scale
Reconfigurable Mesh described in Chapter 7 or [9] to solve this problem.
Assume there are N N nanoscale reconfigurable meshes in this hierarchical
multi-scale architecture. All these N 2 reconfigurable meshes can communicate
simultaneously at the micro-level in unit time as long as there is only one read or
write from or to each module. Data can now flow freely between reconfigurable
mesh modules, so multiple reconfigurable meshes can be employed to solve PO-
MSAG algorithm for a dataset larger than the N L limit posed by each
individual reconfigurable mesh.
In the algorithm explained in Section 14.3, during the phase in which the
nodes record their right and left neighbors, the nodes at the edge of one
reconfigurable mesh will have to record their left or right neighbors that are on
another reconfigurable mesh through the microlevel interconnects. Since there can
only be one receiving or transmitting at any given time, for the N or L nodes trying
to transmit and receive data, the system time complexity degrades to the
maximum of O(N) and O(L).
The inevitable time complexity degradation from O(1) or O(logN)to
max[O(N), O(L)] might seem to be disadvantageous. However, there can actually
be an advantage in certain cases. Let us assume that we increase the size of our
dataset to A N sequences each having length B L,whereA and B are some
constants. We also assume that the reconfigurable meshes we normally use are only
of size N L. So first of all, the advantage of the multiscale hierarchy is that there is
no need to build a new reconfigurable mesh of size AN BL. In the case of the
AN BL dataset (or as a matter of fact, for any given size dataset), our multiscale
architecture would simply just use multiple reconfigurable meshes of fixed size
N L. However, without using the multiscale architecture, we would first have to
obtain a new reconfigurable mesh or somehow increase the size of the standard one