Jason NikasLive FPGA Lab

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

Vitis HLSOpenCLARM/ZynqC++VerilogVivado/VitisJason NikasPanagiotis Nikolaos Tsogkas

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.

GATTACAGCATTACbest matchATTACATTAC

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.

Original1×
Simpler loops1.43×
No branches1.8×
Reordered maximum2.93×
Fewer memory reads3.81×
Prefetch and restrict3.57×

Code

The fastest software version's inner loop: maximums picked without branches, and two neighbours carried over to the next cell instead of read again. Lines 57–82 on GitHub
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;

Report and repository

  • ReportPDF, read in a new tabReadDownload
  • RepositoryGitHub, opens in a new tabOpen

Tools

What this course's projects were built with. Pick one to see where else I used it.

Tap the picture to see it at full size