TY - GEN
T1 - Accelerator design for protein sequence HMM search
AU - Maddimsetty, Rahul P.
AU - Buhler, Jeremy
AU - Chamberlain, Roger D.
AU - Franklin, Mark A.
AU - Harris, Brandon
PY - 2006
Y1 - 2006
N2 - Profile Hidden Markov models (HMMs) are a powerful approach to describing biologically significant functional units, or motifs, in protein sequences. Entire databases of such models are regularly compared to large collections of proteins to recognize motifs in them. Exponentially increasing rates of genome sequencing have caused both protein and model databases to explode in size, placing an ever-increasing computational burden on users of these systems.Here, we describe an accelerated search system that exploits parallelism in a number of ways. First, the application is functionally decomposed into a pipeline, with distinct compute resources executing each pipeline stage. Second, the first pipeline stage is deployed on a systolic array, which yields significant fine-grained parallelism. Third, for some instantiations of the design, parallel copies of the first pipeline stage are used, further increasing the level of coarse-grained parallelism.A nave parallelization of the first stage computation has serious repercussions for the sensitivity of the search. We present a pair of remedies to this dilemma and quantify the regions of interest within which each approach is most effective. Analytic performance models are used to assess the overall speedup that can be attained relative to a single-processor software solution. Performance improvements of 1 to 2 orders of magnitude are predicted.
AB - Profile Hidden Markov models (HMMs) are a powerful approach to describing biologically significant functional units, or motifs, in protein sequences. Entire databases of such models are regularly compared to large collections of proteins to recognize motifs in them. Exponentially increasing rates of genome sequencing have caused both protein and model databases to explode in size, placing an ever-increasing computational burden on users of these systems.Here, we describe an accelerated search system that exploits parallelism in a number of ways. First, the application is functionally decomposed into a pipeline, with distinct compute resources executing each pipeline stage. Second, the first pipeline stage is deployed on a systolic array, which yields significant fine-grained parallelism. Third, for some instantiations of the design, parallel copies of the first pipeline stage are used, further increasing the level of coarse-grained parallelism.A nave parallelization of the first stage computation has serious repercussions for the sensitivity of the search. We present a pair of remedies to this dilemma and quantify the regions of interest within which each approach is most effective. Analytic performance models are used to assess the overall speedup that can be attained relative to a single-processor software solution. Performance improvements of 1 to 2 orders of magnitude are predicted.
KW - HMMER
KW - Hidden Markov model
KW - Protein motif
UR - http://www.scopus.com/inward/record.url?scp=34547458596&partnerID=8YFLogxK
U2 - 10.1145/1183401.1183442
DO - 10.1145/1183401.1183442
M3 - Conference contribution
AN - SCOPUS:34547458596
SN - 1595932828
SN - 9781595932822
T3 - Proceedings of the International Conference on Supercomputing
SP - 288
EP - 296
BT - Proceedings of the 20th Annual International Conference on Supercomputing, ICS 2006
T2 - 20th Annual International Conference on Supercomputing, ICS 2006
Y2 - 28 June 2006 through 1 July 2006
ER -