DOC PREVIEW
Berkeley COMPSCI C267 - Graph Partitioning

This preview shows page 1-2-3-4-5-34-35-36-37-38-69-70-71-72-73 out of 73 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 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 73 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 73 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

4/15/2004 CS267, Yelick 1CS 267: Applications of Parallel ComputersGraph PartitioningKathy Yelickhttp://www.cs.berkeley.edu/~yelick/cs267Outline of Graph Partitioning Lectures• Review definition of Graph Partitioning problem• Overview of heuristics• Partitioning with Nodal Coordinates• Planar graphs• How well can graphs be partitioned in theory?• Graphs in higher dimensions• Partitioning without Nodal Coordinates• Multilevel Acceleration• BIG IDEA, appears often in scientific computing• Comparison of Methods and Applications4/15/2004 CS267, Yelick 3Definition 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 = N1U N2U … U NPsuch that• The sum of the node weights in each Njis “about the same”• The sum of all edge weights of edges connecting all different pairs Njand Nkis minimized• Ex: balance the work load, while minimizing communication• Special case of N = N1U N2: Graph Bisection1 (2)2 (2) 3 (1)4 (3)5 (1)6 (2)7 (3)8 (1)54612121234/15/2004 CS267, Yelick 4Applications• 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 DNA4/15/2004 CS267, Yelick 6Cost of Graph Partitioning• Many possible partitionings to search• Just to divide in 2 parts there are: n choose n/2 ~ sqrt(2n/pi)*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 heuristics4/15/2004 CS267, Yelick 7First Heuristic: Repeated Graph Bisection• To partition N into 2kparts• bisect graph recursively k times• Henceforth discuss mostly graph bisection4/15/2004 CS267, Yelick 8Edge Separators vs. Vertex Separators• Edge Separator: Es(subset of E) separates G if removing Esfrom E leaves two ~equal-sized, disconnected components of N: N1and N2• Vertex Separator: Ns(subset of N) separates G if removing Nsand all incident edges leaves two ~equal-sized, disconnected components of N: N1and N2• Making an Nsfrom an Es: pick one endpoint of each edge in Es•|Ns| <= |Es| ?• Making an Esfrom an Ns: pick all edges incident on Ns•|Es| <= d * |Ns| where d is the maximum degree of the graph ?• We will find Edge or Vertex Separators, as convenientG = (N, E), Nodes N and Edges EEs= green edges or blue edgesNs= red vertices4/15/2004 CS267, Yelick 9Overview of Bisection Heuristics• Partitioning with Nodal Coordinates• Each node has x,y,z coordinates ! partition space• Partitioning without Nodal Coordinates• E.g., Sparse matrix of Web documents• A(j,k) = # times keyword j appears in URL k• Multilevel acceleration (BIG IDEA)• Approximate problem by “coarse graph,” do so recursively4/15/2004 CS267, Yelick 10Nodal Coordinates: How Well Can We Do?• Consider a special case:• A graph with nodal coordinates• The graph is planar• A planar graph can be drawn in plane without edge crossings• Ex: m x m grid of m2nodes: ∃ vertex separator Nswith |Ns| = m = sqrt(|N|) (see last slide for m=5 )• Theorem (Tarjan, Lipton, 1979): If G is planar, ∃ Ns such that •N = N1U NsU N2is a partition,•|N1| <= 2/3 |N| and |N2| <= 2/3 |N|•|Ns| <= sqrt(8 * |N|)• Theorem motivates intuition of following algorithms4/15/2004 CS267, Yelick 11Nodal 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 side1. Choose a line L through the pointsL given by a*(x-xbar)+b*(y-ybar)=0,with a2+b2=1; (a,b) is unit vector ⊥ to L L(a,b)(xbar,ybar)2. Project each point to the lineFor each nj = (xj,yj), compute coordinateSj= -b*(xj-xbar) + a*(yj-ybar) along L3. Compute the medianLet Sbar = median(S1,…,Sn)4. Use median to partition the nodesLet nodes with Sj< Sbar be in N1, rest in N24/15/2004 CS267, Yelick 12Inertial 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 nameLLN1N2N1N24/15/2004 CS267, Yelick 13Inertial Partitioning: choosing L (continued)ΣΣΣΣj(length of j-th green line)2= ΣΣΣΣj[ (xj-xbar)2+ (yj-ybar)2-(-b*(xj-xbar) + 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 * aX2 X3 bMinimized by choosing(xbar , ybar) = (ΣΣΣΣjxj, ΣΣΣΣjyj) / N = center of mass(a,b) = eigenvector of smallest eigenvalue of X1 X2X2 X3(a,b) is unit vectorperpendicular to L(a,b)L(xbar,ybar)4/15/2004 CS267, Yelick 14Nodal Coordinates: Random Spheres• Generalize nearest neighbor idea of a planar graph to higher dimensions • For intuition, consider a the graph defined by a regular 3D mesh• An n by n by n mesh of |N| = n3nodes• Edges to 6 nearest neighbors• Partition by taking plane parallel to 2 axes•Cuts n2=|N|2/3= O(|E|2/3) edges• For the general graphs• Need a notion of well-shaped• (Any graph fits in 3D without crossings!)4/15/2004 CS267, Yelick 15Random Spheres: Well Shaped Graphs• Approach due to Miller, Teng, Thurston, Vavasis•Def: A k-ply neighborhood system in d dimensions is a set {D1,…,Dn} of closed disks in Rdsuch that no point in Rdis strictly interior to more than k disks•Def: An (α,k) overlap graph is a graph defined in terms of α >= 1 and a k-ply neighborhood system {D1,…,Dn}: There is a node for each Dj, and an


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?