DOC PREVIEW
Berkeley COMPSCI C267 - Sources of Parallelism and Locality in Simulation

This preview shows page 1-2-15-16-31-32 out of 32 pages.

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

Unformatted text preview:

CS 267: Applications of Parallel Computers Lecture 9: Sources of Parallelism and Locality in SimulationRecap of Last LecturePowerPoint PresentationContinuous 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 132D Implicit MethodRelation of Poisson to Gravity, ElectrostaticsAlgorithms for 2D Poisson Equation (N vars)Overview of AlgorithmsMflop/s Versus Run Time in PracticeSummary of Approaches to Solving PDEsComments on practical meshesParallelism in Regular meshesAdaptive Mesh Refinement (AMR)Adaptive MeshComposite Mesh from a Mechanical StructureConverting the Mesh to a MatrixEffects of Reordering on Gaussian EliminationIrregular mesh: NASA Airfoil in 2DIrregular mesh: Tapered Tube (Multigrid)Challenges of Irregular MeshesHomework 2: N-Body SimulationCS267 Final ProjectsProject IdeasSlide 3301/14/19 CS267, Yelick 1CS 267: Applications of Parallel ComputersLecture 9:Sources of Parallelism and Locality in SimulationKathy Yelickhttp://www-inst.eecs.berkeley.edu/~cs26701/14/19 CS267, Yelick 2Recap of Last Lecture•Real world problems have parallelism and locality•Four kinds of simulations:•Discrete event simulations •Particle systems•Lumped variables with continuous parameters, ODEs•Continuous variables with continuous parameters, PDEs•General observations:•Locality and load balance often work against each other•Graph partitioning arose in different contexts as an approach•Sparse matrices are important in several of these problems•Sparse matrix-vector multiplication, in particular01/14/19 CS267, Yelick 3Partial Differential EquationsPDEs01/14/19 CS267, Yelick 4Continuous Variables, Continuous ParametersExamples of such systems include•Parabolic (time-dependent) problems:•Heat flow: Temperature(position, time)•Diffusion: Concentration(position, time)•Elliptic (steady state) problems:•Electrostatic or Gravitational Potential: Potential(position)•Hyperbolic problems (waves):•Quantum mechanics: Wave-function(position,time)Many problems combine features of above•Fluid flow: Velocity,Pressure,Density(position,time)•Elasticity: Stress,Strain(position,time)01/14/19 CS267, Yelick 6Example: 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-h01/14/19 CS267, Yelick 7Details of the Explicit Method for Heat•From experimentation (physical observation) we have: u(x,t) /t = 2 u(x,t)/x (assume C = 1 for simplicity)•Discretize time and space and use explicit approach (as described for ODEs) to approximate derivative: (u(x,t+1) – u(x,t))/dt = (u(x-h,t) – 2*u(x,t) + u(x+h,t))/h2 u(x,t+1) – u(x,t)) = dt/h2 * (u(x-h,t) - 2*u(x,t) + u(x+h,t)) u(x,t+1) = u(x,t)+ dt/h2 *(u(x-h,t) – 2*u(x,t) + u(x+h,t))•Let z = dt/h2 u(x,t+1) = z* u(x-h,t) + (1-2z)*u(x,t) + z+u(x+h,t)•By changing variables (x to j and y to i): u[j,i+1]= z*u[j-1,i]+ (1-2*z)*u[j,i]+ z*u[j+1,i]01/14/19 CS267, Yelick 8Explicit Solution of the Heat Equation•Use finite differences with u[j,i] as the heat at•time t= i*dt (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 •nearest neighbors on gridt=5t=4t=3t=2t=1t=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 = dt/h201/14/19 CS267, Yelick 9Matrix View of Explicit Method for Heat•Multiplying by a tridiagonal matrix at each step•For a 2D mesh (5 point stencil) the matrix is pentadiagonal•More on the matrix/grid views later1-2z z z 1-2z z z 1-2z z z 1-2z z z 1-2zT =1-2zzzGraph and “3 point stencil”01/14/19 CS267, Yelick 10Parallelism in Explicit Method for PDEs•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 = dt/h2 > .5•need to make the time steps very small when h is small: dt < .5*h201/14/19 CS267, Yelick 11Instability in Solving the Heat Equation Explicitly01/14/19 CS267, Yelick 12Implicit Solution of the Heat Equation•From experimentation (physical observation) we have: u(x,t) /t = 2 u(x,t)/x (assume C = 1 for simplicity)•Discretize time and space and use implicit approach (backward Euler) to approximate derivative: (u(x,t+1) – u(x,t))/dt = (u(x-h,t+1) – 2*u(x,t+1) + u(x+h,t+1))/h2 u(x,t) = u(x,t+1)+ dt/h2 *(u(x-h,t+1) – 2*u(x,t+1) + u(x+h,t+1))•Let z = dt/h2 and change variables (t to j and x to i) u(:,i) = (I - z *L)* u(:, i+1) •Where I is identity and L is Laplacian 2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2L =01/14/19 CS267, Yelick 13Implicit Solution of the Heat Equation•The previous slide used Backwards Euler, but using the trapezoidal rule gives better numerical properties.•This turns into solving the following equation:•Again I is the identity matrix and L is:•This is essentially solving Poisson’s equation in 1D(I + (z/2)*L) * u[:,i+1]= (I - (z/2)*L) *u[:,i]2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2L =2-1 -1Graph and “stencil”01/14/19 CS267, Yelick 142D Implicit Method •Similar to the 1D case, but the matrix L is now•Multiplying by this matrix (as in the explicit case) is simply nearest neighbor computation on 2D grid.•To solve this system, there are several techniques.4 -1 -1-1 4 -1 -1 -1


View Full Document

Berkeley COMPSCI C267 - Sources of Parallelism and Locality in Simulation

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 Sources of Parallelism and Locality in Simulation
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 Sources of Parallelism and Locality in Simulation 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 Sources of Parallelism and Locality in Simulation 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?