生物信息学课件英文原版课件 (104)

1/14/2018,CS267, Yelick,1,CS 267: Applications of Parallel ComputersLecture 19:Graph Partitioning Part II,Kathy Yelick/cs267,1/14/2018,CS267, Yelick,2,Recap of Last Lecture,Partitioning with nodal coordinates:Inertial methodProjection onto a sphereAlgorithms are efficientRely on graphs having nodes connected (mostly) to “nearest neighbors” in spacePartitioning without nodal coordinates:Breadth-First Search simple, but not great partitionKernighan-Lin good corrector given reasonable partitionSpectral Method good partitions, but slowToday:Spectral methods revisitedMultilevel methods,1/14/2018,CS267, Yelick,3,Basic Definitions,Definition: The Laplacian matrix L(G) of a graph G(N,E) is an |N| by |N| symmetric matrix, with one row and column for each node. It is defined byL(G) (i,i) = degree of node I (number of incident edges)L(G) (i,j) = -1 if i != j and there is an edge (i,j)L(G) (i,j) = 0 otherwise,2 -1 -1 0 0 -1 2 -1 0 0-1 -1 4 -1 -10 0 -1 2 -10 0 -1 -1 2,1,2,3,4,5,G =,L(G) =,1/14/2018,CS267, Yelick,4,Properties of Laplacian Matrix,Theorem 1: Given G, L(G) has the following properties (proof on web page)L(G) is symmetric. This means the eigenvalues of L(G) are real and its eigenvectors are real and orthogonal.Rows of L sum to zero:Let e = 1,1T, i.e. the column vector of all ones. Then L(G)*e=0.The eigenvalues of L(G) are nonnegative:0 = l1 = l2 = = lnThe number of connected components of G is equal to the number of li equal to 0. Definition: l2(L(G) is the algebraic connectivity of GThe magnitude of l2 measures connectivityIn particular, l2 != 0 if and only if G is connected.,1/14/2018,CS267, Yelick,5,Spectral Bisection Algorithm,Spectral Bisection Algorithm:Compute eigenvector v2 corresponding to l2(L(G)For each node n of Gif v2(n) 0 put node n in partition N-else put node n in partition N+Why does this make sense? Recall l2(L(G) is the algebraic connectivity of GTheorem (Fiedler): Let G1(N,E1) be a subgraph of G(N,E), so that G1 is “less connected” than G. Then l2(L(G) = l2(L(G) , i.e. the algebraic connectivity of G1 is less than or equal to the algebraic connectivity of G. (proof on web page),1/14/2018,CS267, Yelick,6,Motivation for Spectral Bisection,Vibrating string has modes of vibration, or harmonicsModes computable as followsModel string as masses connected by springs (a 1D mesh)Write down F=ma for coupled system, get matrix AEigenvalues and eigenvectors of A are frequencies and shapes of modesLabel nodes by whether mode - or + to get N- and N+Same idea for other graphs (eg planar graph trampoline),1/14/2018,CS267, Yelick,7,Eigenvectors of L(1D mesh),Eigenvector 1 (all ones),Eigenvector 2,Eigenvector 3,1/14/2018,CS267, Yelick,8,2nd eigenvector of L(planar mesh),1/14/2018,CS267, Yelick,9,Computing v2 and l2 of L(G) using Lanczos,Given any n-by-n symmetric matrix A (such as L(G) Lanczos computes a k-by-k “approximation” T by doing k matrix-vector products, k = 2) of nodesBipartite model: use bipartite graph for directed graphMulti-object, Multi-Constraint model: use when single structure may involve multiple computations with differing costs,1/14/2018,CS267, Yelick,35,Myth 3: Partition Quality is Paramount,When structure are changing dynamically during a simulation, need to partition dynamicallySpeed may be more important than qualityPartitioner must run fast in parallelPartition should be incrementalChange minimally relative to prior oneMust not use too much memory Example from Touheed, Selwood, Jimack and Bersins1 M elements with adaptive refinement on SGI OriginTiming data for different partitioning algorithms:Repartition time from 3.0 to 15.2 secsMigration time : 17.8 to 37.8 secsSolve time: 2.54 to 3.11 secs,1/14/2018,CS267, Yelick,36,Load Balancing in General,In some communities, load balancing is equated with graph partitioningSome load balancing problems do not fit this modelMade several assumptions about the problemTask costs (node weights) are knownCommunication volumes (edge weights) are knownDependencies are knownFor basic partitioning techniques covered in class, the dependencies were only between iterationsWhat if we have less information?,1/14/2018,CS267, Yelick,37,Load Balancing in General,Spectrum of solutionsStatic - all information available before startingSemi-Static - some info before startingDynamic - little or no info before startingSurvey of solutionsHow each one worksTheoretical bounds, if anyWhen to use itEnormous and diverse literature on load balancingComputer Science systems operating systems, compilers, distributed computingComputer Science theoryOperations research (IEOR)Application domains,1/14/2018,CS267, Yelick,38,Understanding Load Balancing Problems,Load balancing problems differ in:Tasks costsDo all tasks have equal costs?If not, when are the costs known?Before starting, when task created, or only when task endsTask dependenciesCan all tasks be run in any order (including parallel)?If not, when are the dependencies known?Before starting, when task created, or only when task endsLocalityIs it important for some tasks to be scheduled on the same processor (or nearby) to reduce communication cost?When is the information about communication between tasks known?,1/14/2018,CS267, Yelick,39,Task Cost Spectrum,1/14/2018,CS267, Yelick,40,Task Dependency Spectrum,1/14/2018,CS267, Yelick,41,Task Locality Spectrum (Data Dependencies),1/14/2018,CS267, Yelick,42,Spectrum of Solutions,One of the key questions is when certain information about the load balancing problem is knownLeads to a spectrum of solutions:Static scheduling. All information is available to scheduling algorithm, which runs before any real computation starts. (offline algorithms)Semi-static scheduling. Information may be known at program startup, or the beginning of each timestep, or at other well-defined points. Offline algorithms may be used even though the problem is dynamic.Dynamic scheduling. Information is not known until mid-execution. (online algorithms),1/14/2018,CS267, Yelick,43,Approaches,Static load balancingSemi-static load balancingSelf-schedulingDistributed task queuesDiffusion-based load balancingDAG schedulingMixed ParallelismNote: these are not all-inclusive, but represent some of the problems for which good solutions exist.,1/14/2018,CS267, Yelick,44,Static Load Balancing,Static load balancing is use when all information is available in advanceCommon cases:dense matrix algorithms, such as LU factorization done using blocked/cyclic layoutblocked for locality, cyclic for load balancemost computations on a regular mesh, e.g., FFTdone using cyclic+transpose+blocked layout for 1Dsimilar for higher dimensions, i.e