A CGM/BSP Parallel Similarity Algorithm.
C. E. R. Alves, Edson N. Cáceres, Frank Dehne, Siang Wun Song · 2002
We present a CGM/BSP algorithm for computing an alignment (or string editing) between two strings A and C, with jAj = m and jCj = n. The algorithm requires O(p) communication rounds and O( nm ) local computing time, on a distributed memory parallel computer of p processors each with O(nm=p) memory. We also present implementation results obtained on Beowulf machine with 64 nodes.