wiki:pgraph

Acronimul Proiectului: pgraph

  • Nume scurt: pgraph
  • SVN: https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/pgraph
  • Membrii echipei:Antonio-Gabriel Sturzu-asturzu, Adela-Diana Almasi, Alexandrina Floroiu;
  • Descriere proiect: The purpose of this project is to try to parallelize some graph algorithms and see how well they scale

Activitate proiect

Technologies we used

Steps

1.Search and see which graph algorithms can be parallelized

2.Implement the serial versions of the graph algorithms we chose

3.Test the correctness of the serial algorithms using some online evaluators.We used the one on http://infoarena.ro/arhiva-educationala

4.Build case tests with some hand made generators to verify the correctness and performance of the parallel
algorithms that will be implemented

5.Implement in OpenMP and MPI the parallel versions of the graph algorithms

6.Test the performance and correctness of the parallel algorithms on the fep cluster

Results

The results we obtained are in the powerpoint presentation located
in the svn repository in the folder named Presentation. For the Dijkstra and
Prim parallel algorithms, the profiler showed that the bottleneck was produced
mainly by the MPI_Allreduce function. For the Bellman-Ford algorithm, the poor
results were caused clearly by the thread creation and destruction overhead in OpenMP.
A conclusion would be that, when possible, it is optimal to parallelize the most outer loop.
In our case this wasn't possible because it would have affected the correctness of the algorithm.

References

All the articles and books that we used are on the svn repository in the Documentation folder.
They include articles on distributed algorithms for graphs, some articles on parallel CREW PRAM
algorithms for graphs and the CLR Introduction to Algorithms book(doesn't need any introduction)
which was the main reference for the serial algorithms.

Last modified 12 years ago Last modified on Jan 15, 2010, 12:03:46 AM