HMMer-cell: High performance protein profile searching on the cell/B.E. processor

This paper presents HMMer-Cell, an implementation of the computationally intensive bioinformatics application HMMER on the Cell/B.E. multiprocessor architecture. The core of the HMMER workload is the Plan7 Viterbi algorithm, which has a memory requirement of O(NM) where N is the length of the HMM and M is the length of the input sequence length. The main challenge in implementing the Plan7 Viterbi algorithm on the novel Cell/B.E. multiprocessor is the limited local storage space of the Cell/B.E. SPEs (synergistic processing element). We describe our approach to modifying the Viterbi algorithm to reduce the space complexity from O(MN) to O(N). We then proceed to discuss design considerations such as task parallelization and code partitioning, in addition to other optimizations we used to implement HMMer-Cell. We demonstrate near-linear speedup when processing relatively larger HMM profiles; and compare our results to those obtained on commodity x86 processors. © 2008 IEEE.