CS267: Lecture 20
Graph Partitioning
October 31, 2002
Lecturer: Horst D. Simon
Abstract.
Algorithms that find good partitionings of unstructured meshes and irregular
graphs are criticial for the effective execution of many scientific simulations
on parallel platforms. In this lecture some basic algorithms for
graph partitioninigs are discussed, and current software is surveyed.
2002 Lecture Notes
The lecture was based on old lecture notes that are curently not available
in power point. The lecture notes by Kathy Yelick from Fall of 2001 covered
two lectures, and more material that was presented ( Lecture
18 - 2001, Lecture
19 - 2001).
Readings
-
Sourcebook Chapter 18: This is a very nice and comprehensive survey of
the state of the art, and I recommend reading this to learn more about
graph partitioning
-
The lecture was based on two of my older papers. The links below also lead
you to the images used for my presentation.
-
Horst Simon, Partitioning
of Unstructured Problems for Parallel Processing, Computing Systems
in Engineering, Vol. 2, Number 2/3, pp. 135 - 148, 1991.
-
Steve Barnard and Horst Simon, A
Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning
Unstructured Problems, Concurrency: Practice and Experience, Vol. 6,
No. 2. pg. 101 - 117, April 1994.