DOC PREVIEW
Berkeley COMPSCI C267 - Graph Partitioning

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 267 Applications of Parallel Computers Lecture 14: Graph Partitioning - IOutline of Graph Partitioning LecturesDefinition of Graph PartitioningApplicationsSparse Matrix Vector MultiplicationCost of Graph PartitioningFirst Heuristic: Repeated Graph BisectionOverview of Partitioning Heuristics for BisectionEdge Separators vs. Vertex Separators of G(N,E)Graphs with Nodal Coordinates - Planar graphsGraphs with Nodal Coordinates: Inertial PartitioningInertial Partitioning: Choosing LInertial Partitioning: choosing L (continued)Graphs with Nodal Coordinates: Random SpheresRandom Spheres: Well Shaped GraphsGeneralizing Lipton/Tarjan to higher dimensionsStereographic ProjectionChoosing a Random SphereExample of Random Sphere Algorithm (Gilbert)Partitioning with Nodal Coordinates - SummaryPartitioning without Nodal Coordinates- Breadth First Search (BFS)Breadth First SearchPartitioning via Breadth First SearchPartitioning without nodal coordinates - Kernighan/LinKernighan/Lin - Preliminary DefinitionsKernighan/Lin AlgorithmCS267 L14 Graph Partitioning I.1Demmel Sp 1999CS 267 Applications of Parallel ComputersLecture 14: Graph Partitioning - IJames Demmelhttp://www.cs.berkeley.edu/~demmel/cs267_Spr99CS267 L14 Graph Partitioning I.2Demmel Sp 1999Outline of Graph Partitioning Lectures°Review definition of Graph Partitioning problem°Outline of Heuristics°Partitioning with Nodal Coordinates°Partitioning without Nodal Coordinates°Multilevel Acceleration•BIG IDEA, will appear often in course°Available Software•good sequential and parallel software availble°Comparison of Methods°ApplicationsCS267 L14 Graph Partitioning I.3Demmel Sp 1999Definition 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 L14 Graph Partitioning I.4Demmel Sp 1999Applications°Load Balancing while Minimizing Communication°Sparse Matrix time 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°Telephone network design•Original application, algorithm due to Kernighan°Sparse Gaussian Elimination•Used to reorder rows and columns to increase parallelism, decrease “fill-in”°Physical Mapping of DNA°Evaluating Bayesian Networks?CS267 L14 Graph Partitioning I.5Demmel Sp 1999Sparse Matrix Vector MultiplicationCS267 L14 Graph Partitioning I.6Demmel Sp 1999Cost of Graph Partitioning°Many possible partitionings to search:°n choose n/2 ~ sqrt(2n/pi)*2n bisection possibilities°Choosing optimal partitioning is NP-complete•Only known exact algorithms have cost = exponential(n)°We need good heuristicsCS267 L14 Graph Partitioning I.7Demmel Sp 1999First Heuristic: Repeated Graph Bisection°To partition N into 2k parts, bisect graph recursively k times•Henceforth discuss mostly graph bisectionCS267 L14 Graph Partitioning I.8Demmel Sp 1999Overview of Partitioning Heuristics for Bisection°Partitioning with Nodal Coordinates•Each node has x,y,z coordinates•Partition nodes by partitioning space°Partitioning without Nodal Coordinates•Sparse matrix of Web: A(j,k) = # times keyword j appears in URL k°Multilevel acceleration (BIG IDEA)•Approximate problem by “coarse graph”, do so recursivelyCS267 L14 Graph Partitioning I.9Demmel Sp 1999Edge Separators vs. Vertex Separators of G(N,E)°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 and all incident edges leaves two ~equal-sized, disconnected components of N: N1 and N2°Making an Ns from an Es: pick one endpoint of each edge in Es•How big can |Ns| be, compared to |Es| ?°Making an Es from an Ns: pick all edges incident on Ns•How big can |Es| be, compared to |Ns| ?°We will find Edge or Vertex Separators, as convenientEs = green edges or blue edgesNs = red verticesCS267 L14 Graph Partitioning I.10Demmel Sp 1999Graphs with Nodal Coordinates - Planar graphs°Planar graph can be drawn in plane without edge crossings°Ex: m x m grid of m2 nodes: vertex separatorNs with |Ns| = m = sqrt(|N|) (see last slide for m=5 )°Theorem (Tarjan, Lipton, 1979): If G is planar, Ns such that •N = N1 U Ns U N2 is a partition,•|N1| <= 2/3 |N| and |N2| <= 2/3 |N|•|Ns| <= sqrt(8 * |N|)°Theorem motivates intuition of following algorithmsCS267 L14 Graph Partitioning I.11Demmel Sp 1999Graphs with Nodal Coordinates: Inertial Partitioning°For a graph in 2D, choose line with half the nodes on one side and half on the other•In 3D, choose a plane, but consider 2D for simplicity°Choose a line L, and then choose an L perpendicular to it, with half the nodes on either side°Remains to choose L1) L given by a*(x-xbar)+b*(y-ybar)=0, with a2+b2=1; (a,b) is unit vector to L 2) For each nj = (xj,yj), compute coordinate Sj = -b*(xj-xbar) + a*(yj-ybar) along L3) Let Sbar = median(S1,…,Sn)4) Let nodes with Sj < Sbar be in N1, rest in N2CS267 L14 Graph Partitioning I.12Demmel Sp 1999Inertial Partitioning: Choosing L°Clearly prefer L on left below°Mathematically, choose L to be a total least squares fit of the nodes•Minimize sum of squares of distances to L (green lines on last slide)•Equivalent to choosing L as axis of rotation that minimizes the moment of inertia of nodes (unit weights) - source of nameCS267 L14 Graph Partitioning I.13Demmel Sp 1999Inertial Partitioning: choosing L (continued)j (length of j-th green line)2 = j [ (xj - xbar)2 + (yj - ybar)2 - (-b*(xj - xhar) + a*(yj - ybar))2 ] … Pythagorean Theorem = a2 * j (xj - xbar)2 + 2*a*b* j (xj - xbar)*(xj - ybar) + b2 j (yj - ybar)2 = a2 * X1 + 2*a*b* X2 + b2 * X3 = [a b] * X1 X2 * a X2 X3 bMinimized by choosing (xbar , ybar) = (j xj ,


View Full Document

Berkeley COMPSCI C267 - Graph Partitioning

Documents in this Course
Lecture 4

Lecture 4

52 pages

Split-C

Split-C

5 pages

Lecture 5

Lecture 5

40 pages

Load more
Download Graph Partitioning
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Graph Partitioning and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graph Partitioning 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?