CS 267 Applications of Parallel Computers Lecture 17: Graph Partitioning - IIIOutline of Graph Partitioning LecturesReview Definition of Graph PartitioningReview of last 2 lecturesIntroduction to Multilevel PartitioningMultilevel Partitioning - High Level AlgorithmMultilevel Kernighan-LinMaximal MatchingMaximal Matching - ExampleCoarsening using a maximal matchingExample of CoarseningExpanding a partition of Gc to a partition of GMultilevel Spectral BisectionMaximal Independent SetsCoarsening using Maximal Independent SetsSlide 16Slide 17Example: 1D mesh of 9 nodesImprove eigenvector v using Rayleigh Quotient IterationExample of convergence for 1D meshAvailable ImplementationsComparison of methodsTest matrices, and number of edges cut for a 64-way partitionSpeed of 256-way partitioning (from KK95a)Application to DNA SequencingProbes and FragmentsActual B not sorted this way, so we want to sort itRelation to Graph PartitioningExample: recovering a symmetric band matrix via graph partitioningUnscrambling the rows and columns of BpExample of effectiveness in the presence of errorCS267 L17 Graph Partitioning III.1Demmel Sp 1999CS 267 Applications of Parallel ComputersLecture 17: Graph Partitioning - IIIJames Demmelhttp://www.cs.berkeley.edu/~demmel/cs267_Spr99CS267 L17 Graph Partitioning III.2Demmel Sp 1999Outline of Graph Partitioning Lectures°Review of last lectures°Multilevel Acceleration•BIG IDEA, will appear often in course°Available Software•good sequential and parallel software availble°Comparison of Methods°Application to DNA sequencingCS267 L17 Graph Partitioning III.3Demmel Sp 1999Review Definition of Graph Partitioning°Given a graph G = (N, E, WN, WE)•N = nodes (or vertices), E = edges•WN = node weights, WE = edge weights°Ex: N = {tasks}, WN = {task costs}, edge (j,k) in E means task j sends WE(j,k) words to task k°Choose a partition N = N1 U N2 U … U NP such that•The sum of the node weights in each Nj is “about the same”•The sum of all edge weights of edges connecting all different pairs Nj and Nk is minimized°Ex: balance the work load, while minimizing communication°Special case of N = N1 U N2: Graph BisectionCS267 L17 Graph Partitioning III.4Demmel Sp 1999Review of last 2 lectures°Partitioning with nodal coordinates•Rely on graphs having nodes connected (mostly) to “nearest neighbors” in space•Common when graph arises from physical model•Finds a circle or line that splits nodes into two equal-sized groups•Algorithm very efficient, does not depend on edges°Partitioning without nodal coordinates•Depends on edges•Breadth First Search (BFS)•Kernighan/Lin - iteratively improve an existing partition•Spectral Bisection - partition using signs of components of second eigenvector of L(G), the Laplacian of GCS267 L17 Graph Partitioning III.5Demmel Sp 1999Introduction to Multilevel Partitioning°If we want to partition G(N,E), but it is too big to do efficiently, what can we do?•1) Replace G(N,E) by a coarse approximation Gc(Nc,Ec), and partition Gc instead•2) Use partition of Gc to get a rough partitioning of G, and then iteratively improve it°What if Gc still too big?•Apply same idea recursivelyCS267 L17 Graph Partitioning III.6Demmel Sp 1999Multilevel Partitioning - High Level Algorithm (N+,N- ) = Multilevel_Partition( N, E ) … recursive partitioning routine returns N+ and N- where N = N+ U N- if |N| is small(1) Partition G = (N,E) directly to get N = N+ U N- Return (N+, N- ) else(2) Coarsen G to get an approximation Gc = (Nc, Ec)(3) (Nc+ , Nc- ) = Multilevel_Partition( Nc, Ec )(4) Expand (Nc+ , Nc- ) to a partition (N+ , N- ) of N(5) Improve the partition ( N+ , N- ) Return ( N+ , N- ) endif(2,3)(2,3)(2,3)(1)(4)(4)(4)(5)(5)(5)How do we Coarsen? Expand? Improve?“V - cycle:”CS267 L17 Graph Partitioning III.7Demmel Sp 1999Multilevel Kernighan-Lin°Coarsen graph and expand partition using maximal matchings°Improve partition using Kernighan-LinCS267 L17 Graph Partitioning III.8Demmel Sp 1999Maximal Matching°Definition: A matching of a graph G(N,E) is a subset Em of E such that no two edges in Em share an endpoint°Definition: A maximal matching of a graph G(N,E) is a matching Em to which no more edges can be added and remain a matching°A simple greedy algorithm computes a maximal matching:let Em be emptymark all nodes in N as unmatchedfor i = 1 to |N| … visit the nodes in any order if i has not been matched if there is an edge e=(i,j) where j is also unmatched, add e to Em mark i and j as matched endif endifendforCS267 L17 Graph Partitioning III.9Demmel Sp 1999Maximal Matching - ExampleCS267 L17 Graph Partitioning III.10Demmel Sp 1999Coarsening using a maximal matchingConstruct a maximal matching Em of G(N,E)for all edges e=(j,k) in Em Put node n(e) in Nc W(n(e)) = W(j) + W(k) … gray statements update node/edge weightsfor all nodes n in N not incident on an edge in Em Put n in Nc … do not change W(n)… Now each node r in N is “inside” a unique node n(r) in Nc… Connect two nodes in Nc if nodes inside them are connected in Efor all edges e=(j,k) in Em for each other edge e’=(j,r) in E incident on j Put edge ee = (n(e),n(r)) in Ec W(ee) = W(e’) for each other edge e’=(r,k) in E incident on k Put edge ee = (n(r),n(e)) in Ec W(ee) = W(e’)If there are multiple edges connecting two nodes in Nc, collapse them, adding edge weightsCS267 L17 Graph Partitioning III.11Demmel Sp 1999Example of CoarseningCS267 L17 Graph Partitioning III.12Demmel Sp 1999Expanding a partition of Gc to a partition of GCS267 L17 Graph Partitioning III.13Demmel Sp 1999Multilevel Spectral Bisection°Coarsen graph and expand partition using maximal independent sets°Improve partition using Rayleigh Quotient IterationCS267 L17 Graph Partitioning III.14Demmel Sp 1999Maximal Independent Sets°Definition: An independent set of a graph G(N,E) is a subset Ni of N such that no two nodes in Ni are connected by an edge°Definition: A maximal independent set of a graph G(N,E) is an independent set Ni to which no more nodes can be added and remain an independent set°A simple greedy algorithm computes a maximal independent set:let Ni be emptyfor i = 1 to |N| … visit the nodes in any order if node i is not adjacent to any node already in Ni add i to Ni
View Full Document
Unlocking...