Premium
Sequence alignment on the Cray MTA‐2
Author(s) -
Bokhari Shahid H.,
Sauer Jon R.
Publication year - 2004
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.808
Subject(s) - parallel computing , computer science , porting , speedup , dynamic programming , scheduling (production processes) , smith–waterman algorithm , architecture , software , sequence (biology) , synchronization (alternating current) , parallel algorithm , algorithm , sequence alignment , programming language , mathematics , art , mathematical optimization , peptide sequence , visual arts , gene , computer network , biochemistry , chemistry , genetics , channel (broadcasting) , biology
Several variants of standard algorithms for DNA sequence alignment have been implemented on the Cray Multithreaded Architecture‐2 (MTA‐2). We describe the architecture of the MTA‐2 and discuss how its hardware and software enable efficient implementation of parallel algorithms with little or no regard for issues of partitioning, mapping or scheduling. We describe how we ported variants of the naive algorithm for exact alignment and the dynamic programming algorithm for approximate alignment to the MTA‐2 and provide detailed performance measurements. It is shown that, for the dynamic programming algorithm, the use of the MTA's ‘Full/Empty’ synchronization bits leads to almost perfect speedup for large problems on one to eight processors. These results illustrate the versatility of the MTA's architecture and demonstrate its potential for providing a high‐productivity platform for parallel processing. Copyright © 2004 John Wiley & Sons, Ltd.