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:  Hint: To obtain maximum performance using OpenMP you need to use the SGI specific directives for data distribution (Chapter 6).