Embedded Systems
Speeding up DNA sequence alignment in C, then moving it onto the FPGA of a Zynq board.
8.5Course grade
Smith-Waterman
DNA alignment on FPGA
What it is
Smith-Waterman finds the most similar stretch between two DNA or protein sequences. We sped it up in C on x86 and Arm, then built a hardware accelerator for the FPGA of a Zynq board with Vitis HLS, where the Arm cores hand it the work.
The software got 3.81× faster. The hardware passed every simulation but, with one exception, didn’t run on the board, so there is no hardware speedup to report.
One cell at a time
The algorithm fills a table with one cell per pair of letters. Each cell takes the best of three neighbours, left, above and above-left, plus a score for a match, a mismatch or a gap. That makes rows and columns impossible to compute in parallel, but every cell on an anti-diagonal depends only on earlier ones.
Faster software
We changed the C code one step at a time and measured each version:
- Simpler loops: two nested loops instead of one with a division, and a border of padding so the edges need no checks: 1.43×.
- No branches: written so the compiler uses conditional moves instead of jumps, with up to 95 times fewer branch mispredictions: 1.8×.
- Reordered maximum: the same comparisons in a different order, faster for reasons the assembly didn’t explain: 2.93×.
- Fewer memory reads: walking along a row, a cell’s value and its upper neighbour carry over to the next cell instead of being read again: 3.81×.
Prefetching and the restrict keyword made it slower again, and on Arm, which has no conditional move, removing branches did little.
Hardware
The accelerator works along anti-diagonals, so every cell on one can be computed at once, and keeps only the last three of them instead of the whole table. Over seven versions we narrowed every number to the bits it needs, split arrays so they can be read in parallel, kept storage in block RAM, and streamed the second sequence through a sliding window. Most versions could start a new anti-diagonal only every two clock cycles; the last was built to start one every cycle.
On the board
Every version passed simulation and hardware emulation but failed on the board. We ruled out the synthesis tools and rewrote the Arm program from scratch; the fault was in the accelerator’s code, and we ran out of time to find it.
One variant did run, on a 32 × 65,536 input: about 8.8 ms on the board, against the 1.6 ms the tools estimated.
Results
Speed of each software version against the original C code on x86, aligning 256 letters against 300,000, averaged over 100 runs.
Code
match = (string1[j] == string2[i]) ? MATCH : MISS_MATCH;
northwest_value += match;
north_value = similarity_matrix[similarity_index - N - 1] + GAP_d;
max_value = northwest_value;
direction = NORTH_WEST;
int cond_north = (north_value > max_value);
max_value = cond_north ? north_value : max_value;
direction = cond_north ? NORTH : direction;
int cond_west = (west_value > max_value);
max_value = cond_west ? west_value : max_value;
direction = cond_west ? WEST : direction;
int cond_zero = (0 >= max_value);
max_value = cond_zero ? 0 : max_value;
direction = cond_zero ? CENTER : direction;
similarity_matrix[similarity_index] = max_value;
direction_matrix[index] = direction;
*max_index = max_value > similarity_matrix[*max_index] ? similarity_index : *max_index;
northwest_value = north_value - GAP_d;
west_value = max_value + GAP_i;Tools
What this course's projects were built with. Pick one to see where else I used it.