CS 267: Applications of Parallel Computers Graph PartitioningOutline of Graph Partitioning LectureDefinition of Graph PartitioningSlide 4Some ApplicationsSparse Matrix Vector Multiplication y = y +A*xCost of Graph PartitioningOutline of Graph Partitioning LecturesFirst Heuristic: Repeated Graph BisectionEdge Separators vs. Vertex SeparatorsOverview of Bisection HeuristicsSlide 12Nodal Coordinates: How Well Can We Do?Nodal Coordinates: Inertial PartitioningInertial Partitioning: Choosing LInertial Partitioning: choosing L (continued)Nodal Coordinates: Random SpheresRandom Spheres: Well Shaped GraphsGeneralizing Lipton/Tarjan to Higher DimensionsStereographic ProjectionChoosing a Random SphereRandom Sphere Algorithm (Gilbert)Slide 23Slide 24Slide 25Slide 26Slide 27Nodal Coordinates: SummarySlide 29Coordinate-Free: Breadth First Search (BFS)Breadth First SearchPartitioning via Breadth First SearchCoordinate-Free: Kernighan/LinKernighan/Lin: Preliminary DefinitionsKernighan/Lin AlgorithmComments on Kernighan/Lin AlgorithmCoordinate-Free: Spectral BisectionMotivation for Spectral BisectionBasic DefinitionsExample of In(G) and L(G) for Simple MeshesProperties of Laplacian MatrixSpectral Bisection AlgorithmSlide 44Motivation for Spectral Bisection (recap)Details for Vibrating String AnalogyDetails for Vibrating String (continued)Slide 48Eigenvectors of L(1D mesh)2nd eigenvector of L(planar mesh)4th eigenvector of L(planar mesh)Computing v2 and l2 of L(G) using LanczosSpectral Bisection: SummarySlide 54Introduction to Multilevel PartitioningMultilevel Partitioning - High Level AlgorithmMultilevel Kernighan-LinMaximal MatchingMaximal Matching: ExampleExample of CoarseningCoarsening using a maximal matchingExpanding a partition of Gc to a partition of GMultilevel Spectral BisectionMaximal Independent SetsSlide 65Coarsening using Maximal Independent SetsSlide 67Example: 1D mesh of 9 nodesImprove eigenvector: Rayleigh Quotient IterationExample of convergence for 1D meshSlide 71Available ImplementationsComparison of methodsNumber of edges cut for a 64-way partitionSpeed of 256-way partitioning (from KK95a)Beyond Simple Graph PartitioningExtra SlidesCoordinate-Free Partitioning: SummaryIs Graph Partitioning a Solved Problem?Myth 1: Edge Cut = Communication CostMyth 2: Simple Graphs are SufficientMyth 3: Partition Quality is ParamountReferencesSummaryAnother Example02/11/2010 CS267 Lecture 81CS 267: Applications of Parallel ComputersGraph PartitioningJames Demmel and Horst Simonwww.cs.berkeley.edu/~demmel/cs267_Spr1002/11/2010 CS267 Lecture 8Outline of Graph Partitioning Lecture•Review definition of Graph Partitioning problem•Overview of heuristics•Partitioning with Nodal Coordinates•Ex: In finite element models, node at point in (x,y) or (x,y,z) space•Partitioning without Nodal Coordinates•Ex: In model of WWW, nodes are web pages•Multilevel Acceleration•BIG IDEA, appears often in scientific computing•Comparison of Methods and Applications02/11/2010 CS267 Lecture 83Definition of Graph Partitioning•Given a graph G = (N, E, WN, WE)•N = nodes (or vertices),•WN = node weights•E = edges•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 Bisection1 (2)2 (2) 3 (1)4 (3)5 (1)6 (2)7 (3)8 (1)546121212302/11/2010 CS267 Lecture 84Definition of Graph Partitioning•Given a graph G = (N, E, WN, WE)•N = nodes (or vertices),•WN = node weights•E = edges•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 (shown in black)•Ex: balance the work load, while minimizing communication•Special case of N = N1 U N2: Graph Bisection1 (2)2 (2) 3 (1)4 (3)5 (1)6 (2)7 (3)8 (1)461212123502/11/2010 CS267 Lecture 85Some Applications•Telephone network design•Original application, algorithm due to Kernighan•Load Balancing while Minimizing Communication•Sparse Matrix times Vector Multiplication•Solving PDEs•N = {1,…,n}, (j,k) in E if A(j,k) nonzero, •WN(j) = #nonzeros in row j, WE(j,k) = 1•VLSI Layout•N = {units on chip}, E = {wires}, WE(j,k) = wire length•Sparse Gaussian Elimination•Used to reorder rows and columns to increase parallelism, and to decrease “fill-in”•Data mining and clustering•Physical Mapping of DNA•Image Segmentation02/11/2010 CS267 Lecture 86Sparse Matrix Vector Multiplication y = y +A*x… declare A_local, A_remote(1:num_procs), x_local, x_remote, y_localy_local = y_local + A_local * x_localfor all procs P that need part of x_localsend(needed part of x_local, P)for all procs P owning needed part of x_remotereceive(x_remote, P)y_local = y_local + A_remote(P)*x_remote02/11/2010 CS267 Lecture 87Cost of Graph Partitioning•Many possible partitionings to search•Just to divide in 2 parts there are: n choose n/2 = n!/((n/2)!)2 ~ sqrt(2/(n)*2n possibilities•Choosing optimal partitioning is NP-complete•(NP-complete = we can prove it is a hard as other well-known hard problems in a class Nondeterministic Polynomial time)•Only known exact algorithms have cost = exponential(n)•We need good heuristics02/11/2010 CS267 Lecture 8Outline of Graph Partitioning Lectures•Review definition of Graph Partitioning problem•Overview of heuristics•Partitioning with Nodal Coordinates•Ex: In finite element models, node at point in (x,y) or (x,y,z) space•Partitioning without Nodal Coordinates•Ex: In model of WWW, nodes are web pages•Multilevel Acceleration•BIG IDEA, appears often in scientific computing•Comparison of Methods and Applications02/11/2010 CS267 Lecture 89First Heuristic: Repeated Graph Bisection•To partition N into 2k parts•bisect graph recursively k times•Henceforth discuss mostly graph bisection02/11/2010 CS267 Lecture 810Edge Separators vs. Vertex Separators•Edge Separator: Es (subset of E) separates G if removing Es from E leaves two
View Full Document
Unlocking...