= Acronimul Proiectului: Numele proiectului =

 * Nume Scurt: '''Traffic'''
 * SVN: https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/Traffic/

 * Membri echipei: Stefan Nour - stefan.nour, Raluca Negru - raluca.negru; 
 * Descriere proiect: Improving the algorithm for computing the shortest path to a destination for graphs with large numbers of nodes and integrate it in an existing framework for traffic rerouting.



== Related Work ==

We recently discovered a new way of parallelizing a program in Java by using Parallel Java( an API and middleware for parallel programming in 100% Java on shared memory multiprocessor (SMP) parallel computers, cluster parallel computers, and hybrid SMP cluster parallel computers). 
All the files related to this project are at [http://www.cs.rit.edu/~ark/winter2008/531/team/u8/] 

We tried to simulate the test performed by them but we did not obtain the same results. The main issue that we discussed about at our presentation (the time of execution for the parallel implementation on 1 thread vs. the time of execution of the sequential algorithm) was proven to be wrong for them. As our test confirmed, the sequential algorithm runs a little bit faster.

The sequential algorithm on 1 thread:
{{{
[0] -> [23] -> [51] -> [99] (Total Distance = 7)
Running Time : 407
}}}
The parallel algorithm on 1 thread:
{{{
[0] -> [23] -> [51] -> [99] (Total Distance = 7)
Running Time : 428
}}}
== Implementation ==
We tried to integrate the parallelized algorithm into the existing framework by calling a C program from a java context. 
[http://java.sun.com/docs/books/jni/html/start.html#26346]

== Experimental Results ==

The results were obtained for a 1000 nodes graph using the Dijkstra algorithm parallelized with OpenMp on specified number of threads on cluster.

[[Image(results.jpg)]]