April 14th, 2013, 02:46 PM

MPJ Parallel programming
I want to make a Collective communication in my program, using the mpi.* package. I have an implementation of famous Dijkstra algorithm (this algorithm finds a shortest paths in graph from source to all other vertices(nodes)), which I need to make it work in parallel, and I'm not sure how to do it, because I have no experience with parallel programming.
I don't know where in the program and how to put mpi operations. Probably one of the operations that I should use is the MPI_MINLOC operation, which I don't know how to put in my program.
These are essential functions of my program:
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}