TY - GEN
T1 - WOODSTOCC
T2 - 13th IEEE International Symposium on Parallel and Distributed Computing, ISPDC 2014
AU - Cole, Stephen V.
AU - Gardner, Jacob R.
AU - Buhler, Jeremy D.
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/9/16
Y1 - 2014/9/16
N2 - An exponential increase in the speed of DNA sequencing over the past decade has driven demand for fast, space efficient algorithms to process the resultant data. The first step in processing is alignment of many short DNA sequences, or reads, against a large reference sequence. This work presents WOODSTOCC, an implementation of short-read alignment designed for Graphics Processing Unit (GPU) architectures. WOODSTOCC translates a novel CPU implementation of gapped short-read alignment, which has guaranteed optimal and complete results, to the GPU. Our implementation combines an irregular trie search with dynamic programming to expose regularly structured parallelism. We first describe this implementation, then discuss its port to the GPU. WOODSTOCC's GPU port exploits three generally useful techniques for extracting regular parallelism from irregular computations: dynamic thread mapping with a work list, kernel stage decoupling, and kernel slicing. We discuss the performance impact of these techniques and suggest further opportunities for improvement.
AB - An exponential increase in the speed of DNA sequencing over the past decade has driven demand for fast, space efficient algorithms to process the resultant data. The first step in processing is alignment of many short DNA sequences, or reads, against a large reference sequence. This work presents WOODSTOCC, an implementation of short-read alignment designed for Graphics Processing Unit (GPU) architectures. WOODSTOCC translates a novel CPU implementation of gapped short-read alignment, which has guaranteed optimal and complete results, to the GPU. Our implementation combines an irregular trie search with dynamic programming to expose regularly structured parallelism. We first describe this implementation, then discuss its port to the GPU. WOODSTOCC's GPU port exploits three generally useful techniques for extracting regular parallelism from irregular computations: dynamic thread mapping with a work list, kernel stage decoupling, and kernel slicing. We discuss the performance impact of these techniques and suggest further opportunities for improvement.
UR - http://www.scopus.com/inward/record.url?scp=84908632378&partnerID=8YFLogxK
U2 - 10.1109/ISPDC.2014.30
DO - 10.1109/ISPDC.2014.30
M3 - Conference contribution
AN - SCOPUS:84908632378
T3 - Proceedings - IEEE 13th International Symposium on Parallel and Distributed Computing, ISPDC 2014
SP - 197
EP - 204
BT - Proceedings - IEEE 13th International Symposium on Parallel and Distributed Computing, ISPDC 2014
A2 - Muntean, Traian
A2 - Rolland, Robert
A2 - Mugwaneza, Leon
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 24 June 2014 through 27 June 2014
ER -