Methods and Implementation
Each thread has its own program
Using a serial version of Dijkstra's Algorithm as a baseline, we made modifications to parallelize the
program using Java threads. One way we considered parallelizing the program was having each thread
compute
its own instance of the program independently using random start and ending points. However, we decided
not
to use this method because it introduced challenges. For example, if one thread chooses two points that
do
not connect, the program would stall leading to inefficiency.
Spanning Tree Approach
While we could have used a spanning tree rather than the shortest points, we decided not to take this
approach as it had several disadvantages. For example, Threads would need to share updates on the
shortest
path. This constant synchronization would lead to overhead when accessing the priority queue. Our goal
is to
have an efficient algorithm that improves speedup and runtimes, and this would cause us to have a
limited
speedup on the algorithm.
Priority Queue
Another method we considered was just parallelizing the priority queue, a key component of the
algorithm. By
parallelizing the priority queue, each thread would get its own access to the queue and add items to
compute
the shortest path. We chose this method because we felt it's the most effective way to parallelize the
program as you can update the distance to a vertex’s neighbors concurrently. While we found this
approach to
be more efficient, there were disadvantages such as the fact that it does not compute the absolute
shortest
path, but rather gives an approximation of the shortest path.
The worker thread class in our program is responsible for parallelizing the priority queue. Each thread
repeatedly calls poll() to process the next edge from the queue. When an edge is processed, the thread
checks if the start vertex has been visited, if it has then it is skipped. If it has not been visited,
it is
added to the result map which stores the shortest path from the start vertex to each destination. The
threads are synchronized to make sure only one thread updates the map at a time. The threads then add
all of
the neighbors of the starting vertex to the priority queue if they haven’t been visited already, this is
also synchronized. Then the threads repeat the process until it finds the end vertex or all of the
vertices
have been visited.
