Monday 17 February 2014

Parallel Dijkstra

The initial version has only parallelized the outer loop of the algorithm and has not been done in the most efficient way however has provided a significant speed up for the larger graph sizes.

For each graph the source node was the top left and the goal node was the bottom right, both the parallel and sequential implementations found the same path

map
Sequential Dijkstra (ms)
Parallel Dijkstra (ms)
32x32
1
8.49
64x64
3.8
16.73
128x128
16.2
33.20
256x256
68.01
66.38
512x512
277.07
142.77
1024x1024
1146.38
405.50
2048x2048
4954.72
1763.95


No comments:

Post a Comment