ajnarayan / genome-indexing-on-gpu Goto Github PK

Construction of suffix arrays on the GPU using CUDA.

<last edit: 05/14/12>

bucketsort/qsort.cu - Parallel bucket sort + Parallel quick sort of suffix array.

Compile using

nvcc -I <NVIDIA_SDK_PATH>/C/common/inc qsort.cu -o qsort

Run as

./qsort <suffix_size, multiple of 1024> <genome_file>

e.g. ./qsort 10240 genome

bucketsort/bsort.cu - Parallel Bucket sort based on common prefix.

sort.cu - Program to sort the suffixes of a string on the GPU using the thrust libraries and CUDA.

dc3.c - Linear time suffix array consruction on the CPU

quick_sort.c - A program to sort suffixes of a string using quick sort on CPU.

Time Complexity: O(n^2*log(n))

Varrun Ramani [email protected]

Shishir Horane [email protected]

Ashish Bagate [email protected]