We investigate experimentally, alternative approaches to the distributed parallel computation of a class of problems related
to the generic
transitive closure problem and the
algebraic path problem. Our main result is the comparison of two parallel algorithms for transitive closure,
| – |
a straightforward coarse-grained parallel implementation of the Warshall algorithm named Block-Processing (which also extends
to the stronger algebraic path problem) and
|
| – |
a coarse-grained Three-Pass algorithm, introduced in this paper. Although this latter algorithm is more complicated, it behaves
better for large problem sizes.
|
We show the relationship between the transitive closure problem and matrix multiplication — the latter problem has especially
efficient PVM implementations which can be applied here. The synchronous shared memory model and several known intricate systolic
algorithms are a good starting point for distributed implementations. We discuss alternative implementations and the suitability
of the PVM model.