Intel® Software Network

Hello,
 
i would like to parallelize the Diijkstra Singe Source Shorthest Path algorithm.
I have C#-Code and i would like to parallelize it with ParallelFx.
 
In the book "Introduction to parallel computing" (by Ananth Grama,George Karypis,
Vipin Kumar,Anshul Gupta) is a parallelizatzion of this algorithm shown.
i think that its only possible to parallelize the for-loop inside of the while loop.
this point is not good because it would had a better speedup when its possible the
outer-while-loop.
when i paralleize the inner-for-loop than my parallel program even become slower
than the normal serial program.so my parallel programm is 2 times slower than
the serial program on my dual-core-machine :-(
i think that the problem is that inside of the loop will not much work done.
only alot of memory access which dont become faster while using more cpu-cores.
therefore i want to ask you if somebody have some experience with the 
parallelisation of the SSSP-algorithm.maybe some people get a speedup
when they parallelize their program.i have to use the C# programming
language but its possible to change the SSSP-algorithm (for example to
the Bellman-Ford-algorithm). i show you the code-snippet how i
parallelized my algorithm.
 
public override Route Search()
{
...
 
   // Algorithmus: Bestimmen des kürzesten Pfades
   // in einem Graphen (Dijkstra)
   // Siehe "Algorithmen - Robert Sedgewick S.513ff (529)"
   double[] val = new double[_V];
   int[] dad = new int[_V];
   int k;
   const int unseen = int.MaxValue - 2;
   
   //before it looked like this: for (int l = 0; l < _V; l++) 
   Parallel.For(0, _V, l => 
   {
      val[l] = -unseen;
      dad[l] = 0;
   //before it looked like this:  }
   }); // Parallel.For
 
   int finish = -(unseen + 1);
   int min = 0;
   do
   {
      k = min;
      val[k] = -val[k];
      min = 0;
      if (val[k] == unseen)
      {
         val[k] = 0;
      } 
      
      //before it looked like this: for (int t = 0; t < _V; t++)
      Parallel.For(0, _V, t =>
      {
         if (val[t] < 0)
         {
            if ((_A[k, t] != 0) && (val[t] < -(val[k] + _A[k, t])))
            {
               val[t] = -(val[k] + _A[k, t]);
               dad[t] = k;
            }
            if (val[t] > ((min == 0) ? finish : val[min]))
            {
               min = t;
            }
         }
      //before it looked like this: }
      }); // Parallel.For
   }
   while (min != 0);
 
   // Sperrung der Knoten aufheben
   foreach (Edge edge in _Edges)
   {
       if (edge.Locked)
       {
         _ANodes[1 + edge.ID].Locked = false;
      }
   }
   
   // Test ob ein Pfad zum Ziel existiert,
   // wenn eine Distanz zwischen aufeinanderfolgenden
   // Knoten 0 ist.
   int node = _V - 1;
   do
   {
      if (val[node] == 0)
         return null;
      node = dad[node];
   }
   while (node != 0);
...
}

In fact, the current task is to write a threaded program that computes the all-to-all shortest path.

So, a natural way to parallelize given problem is to provide that each thread solved the SSSP for k ( = n / P )

nodes ( see http://www.hpc2n.umu.se/events/ngssc/04/parallel/notes/lecture_6.pdf )

Concerning C#, you can try also MC# ( www.mcsharp.net).

Follows is the code-snippet of our implementation of all-to-all algorithm :

Parallel_ShortestPath  psp = new Parallel_ShortestPath();
  
  int q = n / P, 
      r = n % P;  

  int from = 0,
      to;
  
  //      Run the (asynchronous) methods
  
  for ( i = 0; i < P; i++)  {
   to = from + q + (i < r ? 1 : 0);
   psp.ComputeShortestPath ( from, to, n, w, degrees, edges, SP, psp.sendStop );
   from = to;   
  }
  
  //      Get the stop signals
  
  for ( i = 0; i < P; i++)  
   psp.getStop ? ();

public async ComputeShortestPath  ( int from, int to, int n, int[,] w, int[] degrees,
                                     int[,] edges, int[,] SP, channel() sendStop       ) {
           ....

}

Hello,

thanks for your fast answer. before i posted my post i didnt see that the shorthest path-group belongs to the Threading Challagen Contest.

In fact i have a serial method which i have to parallelize.

and as you can see the code its a single source shorthest apth algorithm.

therefore the parallelization will be little more tricky and the speedup will be not such big.

did nobody made experience with that?

peterd86:

therefore the parallelization will be little more tricky and the speedup will be not such big.

At first, Dikstra's algorithms runs in 0.02-0.03 secs for graphs with 6000 nodes.

For big graph instances, you can be interested in

http://www.cc.gatech.edu/~bader/papers/ShortestPaths.html

the normal dijkstra-algorithm need only such less time?

so i have to check my c#-application why its need so many time. propably the creation of the graph needs such many time.

thanks.

greetings, peter