Parallel computation and FASTA: confronting the problem of parallel database search for a fast sequence comparison algorithm.
We have parallelized the FASTA algorithm for biological sequence comparison using Linda, a machine-independent parallel programming language. The resulting parallel program runs on a variety of different parallel machines. A straight-forward parallelization strategy works well if the amount of computation to be done is relatively large. When the amount of computation is reduced, however, disk I/O becomes a bottleneck which may prevent additional speed-up as the number of processors is increased. The paper describes the parallelization of FASTA, and uses FASTA to illustrate the I/O bottleneck problem that may arise when performing parallel database search with a fast sequence comparison algorithm. The paper also describes several program design strategies that can help with this problem. The paper discusses how this bottleneck is an example of a general problem that may occur when parallelizing, or otherwise speeding up, a time-consuming computation.
Miller
P L
PL
Department of Anesthesiology, Yale University School of Medicine, New Haven, CT 06510.
Nadkarni
P M
PM
Carriero
N M
NM
D000465:Algorithms; D000595:Amino Acid Sequence; D003199:Computer Systems; D008432:Mathematical Computing; D008969:Molecular Sequence Data; D011381:Programming Languages; D012985:Software Design