Parallel Graph Algorithms I
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 04: Parallel Graph Algorithms I
This topic begins the complex study of parallel graph algorithms by addressing data distribution challenges, focusing on techniques for partitioning the adjacency matrix or list structure across parallel processors. The primary algorithm covered is the parallel formulation of Minimum Spanning Tree (MST) algorithms, such as Kruskal's or Prim's, emphasizing how to manage concurrent edge processing and maintain connectivity across partitions.
Learning Outcomes
Learning Outcomes
The impact of graph representation on locality, memory usage, and interprocessor communication is understood and analyzed.
The causes and implications of irregular data access and load imbalance in parallel graph algorithms are explained.
The principles behind the parallelization of MST algorithms, including Kruskal’s and Borůvka’s approaches, are examined with respect to scalability and communication cost.
Topic Outline
Topic Outline
Handout: Parallel Graph Algorithms I*
When Structure Becomes Irregular
Representations and Foundations
Adjacency: Matrix, List, and Locality
Irregularity and Load Balancing
Minimum Spanning Tree (MST)
Kruskal's and Prim's Parallel Challenges
Merging Local Forests: Communication Cost
From Connectivity to Paths
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
General Parallel Computing and Graph Theory
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing. Addison-Wesley.
Foundational Parallel Algorithms and Complexity
Leighton, F. T. (1992). Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes. Morgan Kaufmann Publishers.
Parallel Kruskal's and MST Algorithms
Akl, S. G. (1989). The design and analysis of parallel algorithms. Prentice Hall.
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 04: Parallel Graph Algorithms I
Page updated
Report abuse