Microsoft PowerPoint – Chapter 10 – Graph Algorithms
Introduction to
Parallel Computing
George Karypis
Graph Algorithms
Outline
Graph Theory Background
Minimum Spanning Tree
Prim’s algorithm
Single-Source Shortest Path
Dijkstra’s algorithm
All-Pairs Shortest Path
Dijkstra’s algorithm
Floyd’s algorithm
Maximal Independent Set
Luby’s algorithm
Background
Minimum Spanning Tree
Compute the minimum weight spanning
tree of an undirected graph.
Prim’s Algorithm
Prim’s Algorithm
Θ(n2) serial complexity for dense
graphs.
why?
How can we parallelize this
algorithm?
Which steps can be done in
parallel?
Parallel Formulation of Prim’s
Algorithm
Parallelize the inner-most loop
of the algorithm.
Parallelize the selection of the
“minimum weight edge” connecting
an edge in VT to a vertex in V-VT.
Parallelize the updating of the d[]
array.
What is the maximum
concurrency that such an
approach can use?
How do we “implement” it on a
distributed-memory
architecture?
Decompose the graph A (adjacency
matrix) and vector d vector using a 1D
block partitioning along columns.
Why columns?
Assign each block of size n/p to one of
the processors.
How will lines 10 & 12—13 be
performed?
Complexity?
Parallel Formulation of Prim’s
Algorithm
Isoefficiency:
Single-Source Shortest Path
Given a source vertex s
find the shortest-paths to
all other vertices.
Dijkstra’s algorithm.
How can it be
parallelized for dense
graphs?
All-pairs Shortest Paths
Compute the shortest paths between all
pairs of vertices.
Algorithms
Dijkstra’s algorithm
Execute the single-source algorithm n times.
Floyd’s algorithm
Based on dynamic programming.
All-Pairs Shortest Path
Dijkstra’s Algorithm
Source-partitioned formulation
Partition the sources along the different
processors.
Is it a good algorithm?
Computational & memory scalability
What is the maximum number of processors
that it can use?
Source-parallel formulation
Used when p > n.
Processors are partitioned into n groups
each having p/n processors.
Each group is responsible for one single-
source SP computation.
Complexity?
Floyd’s Algorithm
Solves the problem using a
dynamic programming algorithm.
Let d(k)i,j be the shortest path distance
between vertices i and j that goes
only through vertices 1,…, k.
Complexity: Θ(n3).
Note: The algorithm can run in-place.
How can we parallelize it?
Distribute the matrix using a 2D block
decomposition.
Parallelize the double inner-most loop.
Communication pattern?
Complexity?
Parallel Formulation of Floyd’s
Algorithm
Comparison of All-Pairs SP
Algorithms
Maximal Independent Sets
Find the maximal set of vertices that are
not adjacent to each other.
Serial Algorithms for MIS
Practical MIS algorithms are incremental in
nature.
Start with an empty set.
1. Add the vertex with the smallest degree.
2. Remove adjacent vertices
3. Repeat 1—2 until the graph becomes empty.
These algorithms are impossible to parallelize.
Why?
Parallel MIS algorithms are based on the ideas
initially introduced by Luby.
Luby’s MIS Algorithm
Randomized algorithm.
Starts with an empty set.
1. Assigns random numbers to each vertex.
2. Vertices whose random number are smaller
than all of the numbers assigned to their
adjacent vertices are included in the MIS.
3. Vertices adjacent to the newly inserted
vertices are removed.
4. Repeat steps 1—3 until the graph becomes
empty.
This algorithms will terminate in O(log (n))
iterations.
Why is this a good algorithm to parallelize?
How will the parallel formulation proceed?
Shared memory
Distributed memory