Name
Abstract | ||
|---|---|---|
In this paper we work on the parallelization of the inherently serial Dijkstra's algorithm on modern multicore platforms. Dijkstra's algorithm is a greedy algorithm that computes Single Source Shortest Paths for graphs with non-negative edges and is based on the iterative extraction of nodes from a priority queue. This property limits the explicit parallelism of the algorithm and any attempt to utilize the remaining parallelism results in significant slowdowns due to synchronization overheads. To deal with these problems, we employ the concept of Helper Threads (HT) to extract parallelism on a non-traditional fashion and Transactional Memory (TM) to efficiently orchestrate the concurrent threads' accesses to shared data structures. Results demonstrate that the proposed implementation is able to achieve performance speedups (reaching up to 1.84 for 14 threads), indicating that the two paradigms could be efficiently combined. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ICPP.2009.60 | ICPP |
Keywords | Field | DocType |
greedy algorithms,microcomputers,Dijkstra algorithm,greedy algorithm,helper threads,iterative node extraction,multicore platforms,single source shortest paths,transactional memory,Graph Algorithms,Helper Threading,SSSP algorithms,Speculative Multithreading,Transactional Memory | Task parallelism,Explicit parallelism,Computer science,Parallel computing,Transactional memory,Theoretical computer science,Thread (computing),Priority queue,Suurballe's algorithm,A* search algorithm,Distributed computing,Dijkstra's algorithm | Conference |
Citations | PageRank | References |
14 | 1.28 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Konstantinos Nikas | 1 | 31 | 6.45 |
| Nikos Anastopoulos | 2 | 103 | 9.07 |
| Georgios Goumas | 3 | 268 | 22.03 |
| N. Koziris | 4 | 1015 | 107.53 |