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 softwareSlide 23Generalizing 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 32Computational ArchitectureSlide 34ScalabilityPartitioning the Vertebra with ParMETISVertebral Body With ShellComputational phasesLinear solver iterations131K dof / proc - Flops/sec/proc .47 Teraflops - 4088 processorsSources of scale inefficiencies in solve phaseSlide 43Speedup with 7.5M dof problem (1 to 128 nodes)ConclusionsSlide 46End to end times and (in)efficiency components164K dof/procFirst try: Flop rates (265K dof/processor)Slide 50Nodal Performance of IBM SP Power3 and Power4SpeedupExtra 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 boneHYPRE: Multiple interfaces are necessary to provide “best” solvers and data layouts Source: Robert Falgout, LLNL04/13/07 CS267 Guest LectureCS 267: Applications of Parallel ComputersUnstructured Multigrid for Linear SystemsJames DemmelBased in part on material fromMark Adams (www.columbia.edu/~ma2325)www.cs.berkeley.edu/~demmel/cs267_Spr0704/13/07 CS267 Guest LectureRecall 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?04/13/07 CS267 Guest Lecture “BR” tire: compute displacement during rollingSource: Mark Adams, PPPL04/13/07 CS267 Guest LectureDisplacement historySource: Mark Adams, PPPL04/13/07 CS267 Guest LectureSource of Unstructured Finite Element Mesh: VertebraSource: M. Adams, H. Bayraktar, T. Keaveny, P. Papadopoulos, A. GuptaStudy failure modes of trabecular Bone under stress04/13/07 CS267 Guest LectureMicro-Computed TomographyCT @ 22 m resolutionMechanical TestingE, yield, ult, etc.Methods: FE modeling3D image2.5 mm cube44 m elementsFE meshSource: Mark Adams, PPPLUp to 537M unknowns04/13/07 CS267 Guest LectureOutline°Recall Poisson Equation on regular mesh°Recall solution by Multigrid°Geometric Multigrid°Algebraic Multigrid °Software framework°Numerical examples04/13/07 CS267 Guest LecturePoisson’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”04/13/07 CS267 Guest Lecture2D 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”04/13/07 CS267 Guest LectureMultigrid 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 grid04/13/07 CS267 Guest LectureError on fine and coarse gridssmoothingFinest GridFirst Coarse GridRestriction (R)04/13/07 CS267 Guest LectureMultigrid 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”04/13/07 CS267 Guest LectureMultigrid 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 / matrices04/13/07 CS267 Guest LectureMultigrid Operators°For
View Full Document
Unlocking...