Block Elements: this depends on the size of the block’s local memory (LOCAL_MEM) and the size of each element in the data structure (sizeof(int)). For the Tesla card there is 16K of space so LOCAL_MEM=16384. 16384/4 = 4096
Block Size (number of threads per block): Each thread is responsible for one window. The number of threads per block depends on the block elements, the window size, and the slide size. (block_elements – window_length) / slide_length. (4096 – 200)/50 = 77
Usable Threads: Each thread is responsible for loading the first slide_length of its range from global memory to local memory. This means that some threads at the end of the block will not have all of their data load. There will be window_length/slide_length unusable threads, and block_size – (window_length/slide_length) usable threads.
NOTE: blockDim.x and window_length/slide refer to number of windows (how many windows in a block, and how many unusable windows/threads per block). To convert to position we often must multiply the number of windows by the slide_length. For example, window 5 will start at position 5*slide_length.
Each block starts at position blockIdx.x*(blockDim.x – window_length/slide_length)*slide_length
blockIdx.x is the block ID, if blocks did not need to overlap, then we would just multiply this by blockDim.x*slide_length (blockDim.x refers to the number of windows, and we need position, so we multiply by slide_length). Since things overlap, we need each block (after the first one) to start a few positions back. The number of unusable windows at the end of each block is equal to window_length/slide_length. The next block needs to cover these windows. Block sizes are fixed, so blocks that are moved back to cover unused windows will leave some amount of unprocessed windows that must be covered by the next block (in addition to the unusable windows). Block 1 needs to be moved back window_length/slide_length to cover the unusable windows in block 0; block 2 needs to be moved back 2*(window_length/slide_length) to cover both the unprocessed space and the unusable windows; block 3 needs to be moved back 3*(window_length/slide_length); and so forth. The amount a block must be moved back is blockIdx.x*window_length/slide_length, and therefore each block starts at blockIdx.x(blockDim.x – window_length/slide_length)slide_length.
Each thread, which corresponds to a window, starts at an offset from where the block starts, that offset is based on the slide size: threadIdx.x*slide_length + blockIdx.x(blockDim.x – window_length/slide_length)slide_length
Number of Blocks: block_elements/chrom_size would be correct if there was no overlapping, but blocks must overlap to account for the unusable threads
This is a short description of the algorithm used in the paper Yeast genome analysis identifies chromosomal translocation, gene conversion events and several sites of Ty element insertion.
Yeast genome analysis identifies chromosomal translocation, gene conversion events and several sites of Ty element insertion.
Nucleic Acids Res. 2009 Aug 26.
Paired end mapping of chromosomal fragments has been used in human cells to identify numerous structural variations in chromosomes of individuals and of cancer cell lines; however, the molecular, biological and bioinformatics methods for this technology are still in development. Here, we present a parallel bioinformatics approach to analyze chromosomal paired-end tag (ChromPET) sequence data and demonstrate its application in identifying gene rearrangements in the model organism Saccharomyces cerevisiae. We detected several expected events, including a chromosomal rearrangement of the nonessential arm of chromosome V induced by selective pressure, rearrangements introduced during strain construction and gene conversion at the MAT locus. In addition, we discovered several unannotated Ty element insertions that are present in the reference yeast strain, but not in the reference genome sequence, suggesting a few revisions are necessary in the latter. These data demonstrate that application of the chromPET technique to a genetically tractable organism like yeast provides an easy screen for studying the mechanisms of chromosomal rearrangements during the propagation of a species.