CS 267 Sources of Parallelism and Locality in Simulation – Part 2Recap of Last LectureSlide 3Continuous Variables, Continuous ParametersExample: Deriving the Heat EquationDetails of the Explicit Method for HeatExplicit Solution of the Heat EquationMatrix View of Explicit Method for HeatParallelism in Explicit Method for PDEsInstability in Solving the Heat Equation ExplicitlyImplicit Solution of the Heat EquationSlide 12Relation of Poisson to Gravity, Electrostatics2D Implicit MethodAlgorithms for 2D (3D) Poisson Equation (N vars)Overview of AlgorithmsMflop/s Versus Run Time in PracticeSummary of Approaches to Solving PDEsComments on practical meshesParallelism in Regular meshesComposite mesh from a mechanical structureConverting the mesh to a matrixEffects of Ordering Rows and Columns on Gaussian EliminationIrregular mesh: NASA Airfoil in 2D (direct solution)Irregular mesh: Tapered Tube (multigrid)Source of Unstructured Finite Element Mesh: VertebraMethods: FE modeling (Gordon Bell Prize, 2004)Adaptive Mesh Refinement (AMR)Adaptive MeshChallenges of Irregular MeshesSummary – sources of parallelism and localityExtra SlidesHigh-end simulation in the physical sciences = 7 numerical methods:Composite Mesh from a Mechanical StructureConverting the Mesh to a MatrixEffects of Reordering on Gaussian EliminationIrregular mesh: NASA Airfoil in 2DIrregular mesh: Tapered Tube (Multigrid)CS267 Final ProjectsProject IdeasSlide 4102/07/2006 CS267 Lecture 71CS 267Sources of Parallelism and Localityin Simulation – Part 2James Demmelwww.cs.berkeley.edu/~demmel/cs267_Spr0602/07/06 CS267 Lecture 72Recap of Last Lecture•4 kinds of simulations•Discrete Event Systems•Particle Systems•Ordinary Differential Equations (ODEs)•Today: Partial Differential Equations (PDEs)•Common problems:•Load balancing•Dynamically, if load changes significantly during run•Statically – Graph Partitioning–Sparse Matrix Vector Multiply (SpMV)•Linear Algebra•Solving linear systems of equations, eigenvalue problems•Sparse and dense matrices•Fast Particle Methods•Solving in O(n) instead of O(n2)02/07/2006 CS267 Lecture 73Partial Differential EquationsPDEs02/07/06 CS267 Lecture 74Continuous Variables, Continuous ParametersExamples of such systems include•Elliptic problems (steady state, global space dependence)•Electrostatic or Gravitational Potential: Potential(position)•Hyperbolic problems (time dependent, local space dependence):•Sound waves: Pressure(position,time)•Parabolic problems (time dependent, global space dependence)•Heat flow: Temperature(position, time)•Diffusion: Concentration(position, time)Many problems combine features of above•Fluid flow: Velocity,Pressure,Density(position,time)•Elasticity: Stress,Strain(position,time)02/07/06 CS267 Lecture 75Example: Deriving the Heat Equation0 1xx+hConsider a simple problem•A bar of uniform material, insulated except at ends•Let u(x,t) be the temperature at position x at time t•Heat travels from x-h to x+h at rate proportional to:•As h 0, we get the heat equation:d u(x,t) (u(x-h,t)-u(x,t))/h - (u(x,t)- u(x+h,t))/h dt h= C *d u(x,t) d2 u(x,t) dt dx2= C *x-h02/07/06 CS267 Lecture 76Details of the Explicit Method for Heat•Discretize time and space using explicit approach (forward Euler) to approximate time derivative: (u(x,t+) – u(x,t))/ = C (u(x-h,t) – 2*u(x,t) + u(x+h,t))/h2 u(x,t+) = u(x,t)+ C* /h2 *(u(x-h,t) – 2*u(x,t) + u(x+h,t))•Let z = C* /h2 u(x,t+) = z* u(x-h,t) + (1-2z)*u(x,t) + z*u(x+h,t)•Change variable x to j*h, t to i*, and u(x,t) to u[j,i] u[j,i+1]= z*u[j-1,i]+ (1-2*z)*u[j,i]+ z*u[j+1,i]d u(x,t) d2 u(x,t) dt dx2= C *02/07/06 CS267 Lecture 77Explicit Solution of the Heat Equation•Use finite differences with u[j,i] as the temperature at•time t= i* (i = 0,1,2,…) and position x = j*h (j=0,1,…,N=1/h)•initial conditions on u[j,0]•boundary conditions on u[0,i] and u[N,i]•At each timestep i = 0,1,2,...•This corresponds to•matrix vector multiply by T (next slide)•Combine nearest neighbors on gridi=5i=4i=3i=2i=1i=0u[0,0] u[1,0] u[2,0] u[3,0] u[4,0] u[5,0]For j=0 to N u[j,i+1]= z*u[j-1,i]+ (1-2*z)*u[j,i] + z*u[j+1,i]where z =C*/h2ij02/07/06 CS267 Lecture 78Matrix View of Explicit Method for Heat•u[j,i+1]= z*u[j-1,i]+ (1-2*z)*u[j,i] + z*u[j+1,i]•u[ :, i+1] = T * u[ :, i] where T is tridiagonal:•L called Laplacian (in 1D)•For a 2D mesh (5 point stencil) the Laplacian is pentadiagonal•More on the matrix/grid views later1-2zzzGraph and “3 point stencil”T == I – z*L, L = 2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 21-2z z z 1-2z z z 1-2z z z 1-2z z z 1-2z02/07/06 CS267 Lecture 79Parallelism in Explicit Method for PDEs•Sparse matrix vector multiply, via Graph Partitioning•Partitioning the space (x) into p largest chunks•good load balance (assuming large number of points relative to p)•minimized communication (only p chunks)•Generalizes to •multiple dimensions.•arbitrary graphs (= arbitrary sparse matrices).•Explicit approach often used for hyperbolic equations•Problem with explicit approach for heat (parabolic): •numerical instability.•solution blows up eventually if z = C/h2 > .5•need to make the time step very small when h is small: < .5*h2 /C02/07/06 CS267 Lecture 710Instability in Solving the Heat Equation Explicitly02/07/06 CS267 Lecture 711Implicit Solution of the Heat Equation•Discretize time and space using implicit approach (backward Euler) to approximate time derivative: (u(x,t+) – u(x,t))/dt = C*(u(x-h,t+) – 2*u(x,t+) + u(x+h, t+))/h2 u(x,t) = u(x,t+) - C*/h2 *(u(x-h,t+) – 2*u(x,t+) + u(x+h,t+))•Let z = C*/h2 and change variable t to i*, x to j*h and u(x,t) to u[j,i] (I + z *L)* u[:, i+1] = u[:,i] •Where I is identity and L is Laplacian as before 2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2L =d u(x,t) d2 u(x,t) dt dx2= C *02/07/06 CS267 Lecture 712Implicit Solution of the Heat Equation•The previous slide used Backwards Euler, but using the trapezoidal rule gives better numerical properties•Backwards Euler: (I + z *L)* u[:, i+1] = u[:,i] •This turns
View Full Document
Unlocking...