wiki:Traffic:

Version 16 (modified by stefan.nour, 14 years ago) (diff)

--

Acronimul Proiectului: Numele proiectului

  • 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.

Attachments (3)

Download all attachments as: .zip