Biomedical Engineering Reference
In-Depth Information
Character
−
−
−
G
C
A
0
2
0
3
0
4
Initial distance
Stored distance
1
0
0
0
0
1
T
1
A
1
G
−
T
−
A
−
403 020
Figure 10.7
Systolic array for sequence comparison.
The first one is “bidirectional array” as shown in Figure 10.7. The source and target
sequences are shifted simultaneously from the left and right, respectively. Interleaved
with the characters are the data values from the first row and column of the dynamic
programming matrix. When two nonnull characters enter a processor from opposite
directions, a comparison is performed. On the next clock tick, the characters shift
out and the values following them shift in. This processor now determines a new
state based on the result of the comparison, the two values just shifted in, and its
previous state value, using the same rule as in the dynamic programming algorithm.
When the string are shifted out, they carry with them the last two row and column
of the dynamic programming matrix, and hence the answer. Comparing sequences
of lengths
m
and
n
requires at least 2 max
(m
1
)
processors. The number of
steps required to compute the edit distance is proportional to the length of the array.
With the bidirectional array, the source sequence must be cycled through the array
once for each target sequence in the database. The source and target sequences are
both limited in length to half of the array's length.
With respect to the shortcomings of the bidirectional array, “unidirectional array”
process data in one direction. The source sequence is loaded once and stored in the
array starting from the leftmost PE. The target sequences are streamed through the
array one after another, separated by a control character. With the source sequence
loaded and the target sequences streaming through, the array can achieve near 100%
PE utilization. The length of the array determines the maximum length of the source
sequence. The target sequence, however, can be of any length. Altogether, these prop-
erties make the unidirectional array more suitable and efficient than the bidirectional
array for database searches. A unidirectional array of length
n
can compare a source
sequence of length at most
n
and to a target sequence of length
m
in
O(n
+
1,
n
+
m)
steps.
Both bidirectional systolic array and unidirectional array have been implemented
on the Splash 2 system using Xilinx FPGAs. The JBits implementation follows the
same approach but use more advanced features of FPGAs.
+
Search WWH ::
Custom Search