Obligatory task 2
Develop a parallel program for solving the all pairs shortest path problem
using Dijkstras algorithm (Section 7.4.2). The program should use both
MPI and OpenMP.
The program should use p MPI processes and for each MPI process
it should use q OpenMP processes. (Thus a total of p x q
processes will be used).
The program should work as follows: One (MPI) processes reads in the
data and divides the sources into p groups. The necessary data is
then distributed to the other MPI processes. Each MPI process solves the
single source shortest path problem for its sources using an OpenMP
parallel version of Dijkstra's algorithm with q processes. The length
of the paths are then gathered on one processor and written to a file.
The input should be a file containing the adjacency matrix of the
graph. Here is a
small example
(5 nodes) and a large
example (500 nodes). The first line contains the number of vertices.
Each following line of the file contains the distance from a node to all
other nodes. The distance from a node to itself is always 0.
Note to Fortran users: There is a problem with reading long
formated lines of input in Fortran. For this reason please use the following
two unformated data files found on ask:
/Home/origin13/fredrikm/i236/ob2/fort.10 (small example)
/Home/origin13/fredrikm/i236/ob2/fort.20 (large example)
(The weights on the edges are different from the formatted examples)
These files can be read as follows (replace 10 with 20 for large example):
integer, allocatable :: verdi(:,:)
integer n
read(10)n
allocate(verdi(n,n))
read(10)verdi(1:n,1:n)
You must write a report including:
-
Detailed description of your code
-
Source listings of the code with detailed comments
-
Report on the best run time attained with your code
-
Keeping (p x q) fixed, plott the performance for different
values of q and p. What are the best choices for p
and q?
Hint: To obtain maximum performance using OpenMP you need to use
the SGI
specific directives for data distribution (Chapter 6).