Skip to content

jedbrooke/cuda_bwt

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CUDA accelerated burrows-wheeler transform

The burrows wheeler transform is an algorithm commonly used in bioinformatics and data compression applications. It involves sorting large amounts of data, which generally doesn't paralellize well. We can bitonic sort, which generally has a runtime of O(n log2(n)) if not parallelized, worse than traditional O(n log(n)) algos, but it can be greatly parallelized.

Implementation

Requires CUDA and c++11

This implementation uses '$' as the end marker character, as is commonly used in bioinformatics, since our data only contains A,C,T,G. if you need a different ETX character you can change it in "bwt.hpp"

Normally the bwt algorithm has O(n2) Memory requirements, but we can get around that by just storing each "rotation number" of each string and using that to generate the entire string only when we need it for sorting so we don't need to store it, bringing the memory requirement to just O(n)

Running

the included Makefile has rules for building the object file and the demo/benchmark executable

make will generate bwt.o, to use in other projects just include "bwt.hpp" and link the object file.

make demo will generate the demo executable which will run a comparison between the gpu version, and a cpu version based around std::list.sort() for the bwt.

So how fast is it?

testing platform:

  • OS: Ubuntu 20.04
  • CPU: Intel i7 4930k @ 4.0Ghz
  • GPU: Nvidia Tesla M40 @ 1.1Ghz
Size: Cpu time: Gpu time:
100Kbp 0.129s 0.99s
1Mbp 1.977s 0.228s
10Mbp 26.996s 2.862s
100Mbp 6m21.266s 0m56.382s*

*When I run the gpu version by itself without running the cpu version like in demo.cpp, the time is 39.528s. not sure what is causing the difference

Some tests of just the gpu, I did not run the cpu version for these tests because I thought it would take too long

Size: GPU time:
500Mbp 5m23.737s
800Mpb 11m0.889s
1Bbp 14m9.651s

for small sequences below 1Mbp, it probably isn't worth the extra overhead and latency from sending the data to the GPU, but for larger datasets, it offers a 7-10x speedup.