Parallel Graph Algorithms II
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 05: Parallel Graph Algorithms II
The focus shifts to shortest path problems, detailing the parallelization of Dijkstra's algorithm for SSSP by managing the distributed priority queue and efficiently updating distance labels across processors. This introduces challenges related to high-latency communication and workload imbalance that are common when applying parallel models to complex, irregular graph structures.
Learning Outcomes
Learning Outcomes
The limitations of Dijkstra’s algorithm under distributed-memory conditions are identified and analyzed in terms of synchronization and communication cost.
The Δ-Stepping algorithm is understood as a scalable relaxation-based method for Single-Source Shortest Paths (SSSP), and its communication–computation trade-offs are evaluated.
The design and performance of All-Pairs Shortest Paths (APSP) algorithms, including the Floyd–Warshall wavefront approach, are examined in relation to data decomposition and processor-grid topology.
Topic Outline
Topic Outline
Handout: Parallel Graph Algorithms II*
When Distances Become Dimensions
Parallel Single-Source Shortest Paths (SSSP)
Parallelizing Dijkstra: Distributed Priority Queues
The Δ-Stepping Algorithm: Bucket-Based Relaxation
Parallel All-Pairs Shortest Paths (APSP)
APSP Strategies: SSSP vs. Matrix Methods
Floyd–Warshall: Wavefront and 2D Grids
From Paths to Patterns
Note: Links marked with an asterisk (*) lead to materials accessible only to members of the University community. Please log in with your official University account to view them.
Readings
Readings
The Δ-Stepping Algorithm (SSSP)
Meyer, U., & Sanders, P. (2003). Δ-stepping: A parallel single-source shortest path algorithm. Journal of Algorithms, 49(1), 114–152.
Parallel APSP and Floyd–Warshall on 2D Grids
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing. Addison-Wesley.
General Parallel Graph Algorithms and Performance Modeling
Jaja, J. (1992). An introduction to parallel algorithms. Addison-Wesley.
Access Note: Published research articles and books are linked to their respective sources. Some materials are freely accessible within the University network or when logged in with official University credentials. Others will be provided to enrolled students through the class learning management system (LMS).
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 05: Parallel Graph Algorithms II
Page updated
Report abuse