CS 267: Applications of Parallel Computers Unstructured Multigrid for Linear SystemsRecall Big Idea used several times in course“BR” tire: compute displacement during rollingDisplacement historySource of Unstructured Finite Element Mesh: VertebraMethods: FE modelingOutlinePoisson’s equation in 1D: 2u/x2 = f(x)2D Poisson’s equationMultigrid OverviewError on fine and coarse gridsMultigrid uses Divide-and-Conquer in 2 WaysMultigrid Sketch in 2DMultigrid OperatorsMultigrid V-Cycle AlgorithmWhy is this called a V-Cycle?The Solution Operator S(i) - DetailsWeighted Jacobi chosen to damp high frequency errorThe Restriction Operator R(i) - DetailsInterpolation Operator In(i-1): detailsParallel 2D MultigridAvailable softwareHYPRE: Multiple interfaces are necessary to provide “best” solvers and data layouts Source: Robert Falgout, LLNLSlide 24Generalizing Multigrid beyond Poisson, to unstructured meshesGeometric MultigridExample of Geometric CoarseningExamples of meshes from geometric coarseningWhat can go wrongHow to coarsen carefullyAlgebraic MultigridParallel Smoothers for Unstructured MultigridSlide 33Computational ArchitectureSlide 35ScalabilityPartitioning the Vertebra with ParMETISVertebral Body With ShellComputational phasesLinear solver iterations131K dof / proc - Flops/sec/proc .47 Teraflops - 4088 processorsEnd to end times and (in)efficiency componentsSources of scale inefficiencies in solve phase164K dof/procFirst try: Flop rates (265K dof/processor)Slide 47Speedup with 7.5M dof problem (1 to 128 nodes)Slide 49Nodal Performance of IBM SP Power3 and Power4SpeedupConclusionsExtra SlidesMultigrid V(n1,n2) - cycleSlide 55Algorithms for 2D (3D) Poisson Equation (N vars)Multigrid MotivationSlide 58Multigrid Sketch in 1DComplexity of a V-CycleFull Multigrid (FMG)Full Multigrid Cost AnalysisComplexity of Solving Poisson’s EquationMultigrid as Divide and Conquer AlgorithmConvergence Picture of Multigrid in 1DConvergence Picture of Multigrid in 2DPerformance Model of parallel 2D Multigrid (V-cycle)Comparison of Methods (in O(.) sense)PracticalitiesMultigrid on an Adaptive MeshMultiblock ApplicationsAdaptive Mesh RefinementSupport for AMRMultigrid on an Unstructured MeshSlide 75Trabecular Bone: Failure modes under stressMultigrid for nonlinear elastic analysis of bone03/14/06 CS267 Lecture 17CS 267: Applications of Parallel ComputersUnstructured Multigrid for Linear SystemsJames DemmelBased in part on material fromMark Adams (www.cs.berkeley.edu/~madams)www.cs.berkeley.edu/~demmel/cs267_Spr0503/14/06 CS267 Lecture 17Recall Big Idea used several times in course°To solve a hard problem, •Use a coarse approximation, which is solved recursively by coarser ones•Depends on coarse approximation being accurate enough if we are far enough away•“Coarse” means small to represent, so fast to compute or communicate°Multilevel Graph Partitioning (METIS): •Replace graph to be partitioned by a coarser graph, obtained via Maximal Independent Set•Given partitioning of coarse grid, refine using Kernighan-Lin°Barnes-Hut and Fast Multipole Method for computing gravitational forces on n particles in O(n log n) time:•Approximate particles in box by total mass, center of gravity•Good enough for distant particles; for close ones, divide box recursively°Solving Poisson equation on mesh using Multigrid•Approximate low frequency part of solution using coarse mesh• How general is this idea?03/14/06 CS267 Lecture 17 “BR” tire: compute displacement during rollingSource: Mark Adams, PPPL03/14/06 CS267 Lecture 17Displacement historySource: Mark Adams, PPPL03/14/06 CS267 Lecture 17Source of Unstructured Finite Element Mesh: VertebraSource: M. Adams, H. Bayraktar, T. Keaveny, P. Papadopoulos, A. GuptaStudy failure modes of trabecular Bone under stress03/14/06 CS267 Lecture 17Micro-Computed TomographyCT @ 22 m resolutionMechanical TestingE, yield, ult, etc.Methods: FE modeling3D image2.5 mm cube44 m elementsFE meshSource: Mark Adams, PPPLUp to 537M unknowns03/14/06 CS267 Lecture 17Outline°Recall Poisson Equation on regular mesh°Recall solution by Multigrid°Geometric Multigrid°Algebraic Multigrid °Software framework°Numerical examples03/14/06 CS267 Lecture 17Poisson’s equation in 1D: 2u/x2 = f(x)2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2T =2-1 -1Graph and “stencil”03/14/06 CS267 Lecture 172D Poisson’s equation°Similar to the 1D case, but the matrix T is now°3D is analogous4 -1 -1-1 4 -1 -1 -1 4 -1 -1 4 -1 -1 -1 -1 4 -1 -1 -1 -1 4 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4T =4-1-1-1-1Graph and “stencil”03/14/06 CS267 Lecture 17Multigrid Overview°Basic Algorithm:•Replace problem on fine grid by an approximation on a coarser grid•Solve the coarse grid problem approximately, and use the solution as a starting guess for the fine-grid problem, which is then iteratively updated•Solve the coarse grid problem recursively, i.e. by using a still coarser grid approximation, etc.°Success depends on coarse grid solution being a good approximation to the fine grid03/14/06 CS267 Lecture 17Error on fine and coarse gridssmoothingFinest GridFirst Coarse GridRestriction (R)03/14/06 CS267 Lecture 17Multigrid uses Divide-and-Conquer in 2 Ways°First way:•Solve problem on a given grid by calling Multigrid on a coarse approximation to get a good guess to refine°Second way:•Think of error as a sum of sine curves of different frequencies-Same idea as FFT-based solution, but not explicit in algorithm•Replacing value at each grid point by a certain weighted average of nearest neighbors decreases the “high frequency error”•Multigrid on coarse mesh decreases the “low frequency error”03/14/06 CS267 Lecture 17Multigrid Sketch in 2D°Consider a 2m+1 by 2m+1 grid in 2D°Let P(i) be the problem of solving the discrete Poisson equation on a 2i+1 by 2i+1 grid in 2D•Write linear system as T(i) * x(i) = b(i)°P(m) , P(m-1) , … , P(1) is sequence of problems from finest to coarsestNeed to generalize this to unstructured meshes / matrices03/14/06 CS267 Lecture 17Multigrid Operators°For problem P(i) :•b(i) is the RHS and •x(i) is
View Full Document
Unlocking...