CS 267: Applications of Parallel Computers Graph PartitioningOutline of Graph Partitioning LecturesDefinition of Graph PartitioningSlide 4ApplicationsSparse Matrix Vector Multiplication y = y +A*xCost of Graph PartitioningSlide 8First 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)Extra 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/23/2005 CS267 Lecture 101CS 267: Applications of Parallel ComputersGraph PartitioningJames Demmelwww.cs.berkeley.edu/~demmel/cs267_Spr0502/23/2005 CS267 Lecture 10Outline 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/23/2005 CS267 Lecture 103Definition 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/23/2005 CS267 Lecture 104Definition 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/23/2005 CS267 Lecture 105Applications•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 DNA02/23/2005 CS267 Lecture 106Sparse 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/23/2005 CS267 Lecture 107Cost of Graph Partitioning•Many possible partitionings to search•Just to divide in 2 parts there are: n choose n/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/23/2005 CS267 Lecture 10Outline 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/23/2005 CS267 Lecture 109First Heuristic: Repeated Graph Bisection•To partition N into 2k parts•bisect graph recursively k times•Henceforth discuss mostly graph bisection02/23/2005 CS267 Lecture 1010Edge Separators vs. Vertex Separators•Edge Separator: Es (subset of E) separates G if removing Es from E leaves two ~equal-sized, disconnected components of N: N1 and N2 •Vertex Separator: Ns (subset of N) separates G if removing Ns
View Full Document
Unlocking...