A Parallel Wavefront Algorithm for Efficient Biological Sequence Comparison
A Parallel Wavefront Algorithm for Efficient Biological Sequence Comparison
复制标题
用于高效生物序列比较的并行波前算法
DOI：
10.1007/3-540-44843-8_27
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
S. W. Song
中科院分区：
文献类型：
--
作者：
C. E. R. Alves;E. Cáceres;F. Dehne;S. W. Song
在本文中，我们提出了一个并行波前算法计算两个字符串A和C之间的对齐，|一|=mand| C| =n.在p个处理机的分布式并行计算机上，该算法需要O（（m+n）/p）的通信次数和O（mn/p）的局部计算时间。该算法的新奇是基于每个处理器的工作负载和所需的通信轮数之间的折衷，由称为α的参数表示。所提出的算法表示在这个参数，可以调整，以获得最佳的整体并行时间在一个给定的实现。我们显示了非常有前途的实验结果，在64节点的Beowulf机。波前通信要求的特征是每个处理器与很少的其他处理器通信。这使得它非常适合作为网格计算的潜在应用。
In this paper we present a parallel wavefront algorithm for computing an alignment between two stringsAandC, with |A| =mand |C| =n. On a distributed memory parallel computer ofpprocessors each withO((m+n)/p) memory, the proposed algorithm requiresO(p) communication rounds andO(mn/p) local computing time. The novelty of this algorithm is based on a compromise between the workload of each processor and the number of communication rounds required, expressed by a parameter called α. The proposed algorithm is expressed in terms of this parameter that can be tuned to obtain the best overall parallel time in a given implementation. We show very promising experimental results obtained on a 64-node Beowulf machine. A characteristic of the wavefront communication requirement is that each processor communicates with few other processors. This makes it very suitable as a potential application for grid computing.