The sequence comparison on a linear systolic array proceeds as follows: one sequence (the query sequence) is stored into the array (one character per processor) and the other sequence flows from the left to right through the array. During each systolic step, one elementary matrix computation is performed on each processor. The result is available on the rightmost processor when the last character of the flowing sequence is output.
Compared to a sequential machine the speed-up for computing one query sequence of size N against a database of M residues is given by:
N x M
--------- = N (considering that M >> N)
N + M - 1
N = size of the query sequence (number of processors)
M = size of the database