程序代写代做代考 concurrency algorithm Microsoft PowerPoint – Chapter 10 – Graph Algorithms

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