Efficiency of Shared-Memory Multiprocessors for a Genetic Sequence Similarity Search Algorithm

Shared-Memory Multiprocessors (SMPs) may offer performance that scales with the growth of the genetic databases. This paper analyzes the performance of BLAST on SMPs, to improve our theoretical and practical understanding of the scalability of the algorithm. We conducted experiments on throughput and response time of BLAST on three different SMPs---SGI Challenge, Sun Sparc Center 2000, and Cray CS6400. We experimentally determined the scalability of the three major variations of the BLAST algorithm, BLASTX, BLASTN, and BLASTP, and compared the experimental results to the theoretically predicted scalability. The results indicate that BLASTX and BLASTP scale well on SMPs. Moreover, achieving acceptable response times will require more processors as sequence databases increase in size, even considering the likely future improvements in processor speed.