Dinh:COMPUTATIONAL/GPU Project/MummerGPU study

From ZhangLabWiki
Jump to navigation Jump to search

MUMmerGPU 1.1

High-throughput sequence alignment using graphics processing units by Michael C. Schatz et. al. (2007). University of Maryland

MUMmerGPU is an open-source high-throughput parallel, pairwise local sequence alignment program. The application was developed using CUDA (Compute Unified Device Architecture) to run on the nVidia's G80 architecture. Sequence alignment is done by aligning multiple query sequences against the suffix tree of a single reference sequence. The analysis by Schatz shows 10x speedup against the CPU version of MUMmer in sequence alignment and an overall 3.5x speedup in total running time. MUMmerGPU-1.1, the current release of the application is only a hybrid between GPU and CPU.

Summary of MUMmer algorithm: suffix-tree: for every suffix S there is a unique path from the root to leaf in suffix tree, T. For a string of length n, there are n leaf nodes for each of the n suffixes in S. Each edge in T is labeled with a substring of variable length of S, the "edge-label". An "i's path label" is a label created from concatenating edge-labels along a path from the root to a node i.

leaves are labeled with the position where the path-label begins in S internal nodes have at least 2 children (2 possible path to diverge from). Edge-labels ofthe children each begin with a different character of the alphabet (one child per letter of the alphabet). The depth of anyleaf is at most n (length of string). There are O(n) nodes in the T.

All substrings of a query string Q of length m that occur in a string S can be found by navigating T of S to follow the characters in Q.

1. Reference sequence is processed to create a data structure known as the "suffix-tree" 2. Find the longest prefix of Q that occurs in T going from root and transversing as many nodes exactly as possible. 3. If at the node v, there is no matching labeled edge, report the occurrences of Q[1,i], where i is the last matching character. 4. Continues by finding the longest substrings for each of the m-1 remaining start positions in Q. 5. Instead of navigating from root this time, the algorithm resumes at Q[1,i+1] and from node v to v'.

Summary of MUMmerGPU Process: 1. Suffix tree of the reference sequence is constructed on the GPU using Ukkonen algorithm. 2. Transfer suffix tree to the GPU. 3. Transfer query seqences to GPU 4. Align query to tree 5. Write results to GPU 6. Transfer result in bulk to host RAM for all queries 7. All maximal alignments longer than a user-supplied value, (l) are reported by post-processing the raw alignment results on the CPU

Task Parallelization:

1. Each multiprocessor on the GPU process a subset of the queries in parallel.

2. kernel aligns the query to the reference by navigating the tree using the suffix-links to avoid reprocessing the same character of the query.

Data Parallelization:

1. data are partitioned into large blocks so that reference suffix tree, query sequences, and output buffers will fit on the GPU. -k smaller suffix trees are created from overlapping segments ("page") of the reference sequence to fill 1/3 of GPU memory. -the overlapping regions are of query length m to guarantee all alignments in the reference but overlapping regions will only be reported one.

2. Compute the amoung of GPU memory available for storing query data and alignment results. - read query from disk in blocks to fill the remaining memory & transfer them to the GPU - auxillary 1D array is used to store the offset of each query in the query buffer on the GPU.

3. reverse complement alignments are computed on-the-fly to allow for computing forward and reverse alignments without additional data transfer.

4. Output buffer contains memory blocks to record the alignment result for each of the m-l +1 substrings of query of length m. -result consist of the node id of the last visited node and the length of the substring that exactly aligns.

5. for k>1, the output slots for each tree are preserved until the queries in a block have been aligned against each tree.

Path through MAIN: 1. ParseCommandLine() 2. createReference() -->getReferenceString() 3. createQuerySet() 4. createMatchContext() 5. matchQueries() -Loop through "page" of reference: --> buildReferenceTexture();


>createTreeTexture();


>buildUkkonenSuffixTree(); //create tree k


>buildSuffixTreeTexture(); // flatten tree

-cudaGetDeviceProperties(); -Loop through query blocks: -->getQueryBlock


>matchSubset()


>destroyQueryBlock()


>cudaThreadExit();

-Loop through "page": --> destroyReference(); --> writeStatisticsFile(); 6. destroyMatchContext() --> free(ctx); --> destroyQuerySet(); GPU Memory Layout: two 2D textures are used to store the suffix tree. In both, the tree node is stored as a pair of 16-byte texels.

Node texture: stores start & end coord and suffix link Children texture: stores pointers to A, C, G, T children and addressed in parallel to the node texture.

(*auxillary table contain each node's edge length, sequence depth, parent pointer, and suffix number for leaf nodes is stored in RAM and used later on to manage outputs).

(*the nodes are rearranged into cache blocks to optimize 2D locality, ensuring that modes of the same depth are placed into the same 'wide' block' near the root while further down, the nodes from hte same subtree are placed into the same 'tall' block. Each block contains 32x32 nodes.)

The reference sequence is transferred to the GPU as a third 2D texture after they are reordered along 2D space filling curve to maximize the cache hit rate for subsequent accessed along a node's edge. OVERALL: using cache memory organized with the space filling curves for the suffix-tree and reference sequence improved kernel execution speed by several fold.