Overlapping communication and computation with MPI-2 for Floyd's algorithm

The shortest path problem is an important problem that has received multiple and considerable research effort not only in sequential but parallel algorithms as well.

Current research in computer science at Texas Tech University has resulted in the development of a new parallel Floyd All-Pair Shortest Path algorithm that attempts to achieve overlap of computation with data transfer "communication" through the use of MPI_Bcast as the function to interchange information among participant processes. One of the reasons for the development of non-blocking instructions for MPI was to support the overlap of useful computation with communication, and other types of overlap.

This thesis will present changes introduced to this newly developed parallel version of Floyd's Algorithm. Extensive testing of non-blocking and/or blocking MPI-2 instructions is done in order to achieve as much overlap as possible additionally other alternatives for achieving overlap are also analyzed. The research has resulted in several new versions of the Floyd's algorithm that have been compared against a traditional parallel implementation of Floyd's.

The results and conclusions about the level of overlapped observed on these new versions of Floyd's Algorithm are presented with independent overlap and communication tests that provide a comparison between the level of overlap supported by non-blocking instructions in to public domain versions of MPI, MPCH1 and the latest release MPICH2.