HOME       UP       PREV       NEXT (Polyhedral Address Mapping)  

Smith-Waterman D/P Data Dependencies

The Smith-Waterman algorithm has become an icon for FPGA acceleration. Two strings are matched for edit distance.

A quadratic algorithm based on dynamic programming is used. The maximum score needs to be found in a 2-D array where each score depends on the three immediate neighbours with lower index in the diagram. Zeros are inserted where subscripts would be negative at the edges.

Data dependencies (slightly simplified) in Smith-Waterman Alignment Matcher.
Data dependencies (slightly simplified) in Smith-Waterman Alignment Matcher.

Acceleration is achieved by computing many scores in parallel.

There is no simple nesting of two for loops that can work. Instead, items on a diagonal frontier can be computed in parallel.

Normally one string behaves as a needle with perhaps 1000 characters and the other is a haystack streamed from a fileserver.

We shall discuss suitable hardware architectures on the example sheet.


27: (C) 2012-18, DJ Greaves, University of Cambridge, Computer Laboratory.