A multithreaded parallel implementation of a dynamic programming algorithm for sequence comparison.

This paper discusses the issues involved in implementing a dynamic programming algorithm for biological sequence comparison on a generalpurpose parallel computing platform based on a ne-grain event-driven multithreaded program execution model. Fine-grain multithreading permits e cient parallelism exploitation in this application both by taking advantage of asynchronous point-to-point synchronizations and communication with low overheads and by e ectively tolerating latency through the overlapping of computation and communication. We have implemented our scheme on EARTH, a ne-grain event-driven multithreaded execution and architecture model which has been ported to a number of parallel machines with o -the-shelf processors. Our experimental results show that the dynamic programming algorithm can be e ciently implemented on EARTH systems with high performance (e.g., speedup of 90 on 120 nodes), good programmability and reasonable cost.