title: Parallel computation and FASTA: confronting the problem of parallel database search for a fast sequence comparison algorithm.
abstract: 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.
authors.affiliation: Department of Anesthesiology, Yale University School of Medicine, New Haven, CT 06510.
authors.forename: P L
authors.initials: PL
authors.lastname: Miller
authors.forename: P M
authors.initials: PM
authors.lastname: Nadkarni
authors.forename: N M
authors.initials: NM
authors.lastname: Carriero
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D003199:Computer Systems; D008432:Mathematical Computing; D008969:Molecular Sequence Data; D011381:Programming Languages; D012985:Software Design