A cost-optimal parallel algorithm based on Floyd-Warshall Algorithm in order to resolve the APSP problem
The sequential version of the Floyd’s algorithm takes in input the adjacency matrix of size 𝑛 × 𝑛, whose entries (𝑖, 𝑗) represent the positive weights that refer to the distance between vertex 𝑖 and vertex 𝑗, for 𝑖, 𝑗 = 1, ... , 𝑛. The same matrix in output will contain the updated weights representing the shortest paths for each pair of nodes. The development of the parallel version was done according to Foster’s PCAM methodology.
Install MPICH, a high performance implementation of the Message Passing Interface (MPI) standard.
Build the executables by using Makefile
make all
- Generate first the input square matrix through
gen_adj_matrix, by providing the number or rows/columns and the name of the binary output file.bin. Optionally, a user-defined maximum weight can be set instead of the default one
./gen_adj_matrix <matrix size> <file> optional: <max weight>
-
Alternatively, as the input square matrix a predefined one inside the homonymous folder
matricescan be used. -
Run the APSP algorithm by providing the number of processors, which must be a perfect square, and the binary file containing the adjacency matrix
mpiexec -n <number of processors> ./allshortestpair <file>
The benchmark was performed on a virtual machine on a single CPU machine with 4 physical cores, and 8 logical ones due to hyper-threading.
| Matrix size | Time on 1 processor | Time on 4 processors | Speedup | Efficiency |
|---|---|---|---|---|
| 1000 × 1000 | 1,7 seconds | 0,55 seconds | 3 | 0,75 |
| 3000 × 3000 | 38 seconds | 12 seconds | 3,16 | 0,79 |
| 5000 × 5000 | 174 seconds | 55 seconds | 3,16 | 0,79 |