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

This preview shows page 1-2-3-4-5-36-37-38-39-40-73-74-75-76-77 out of 77 pages.

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

Unformatted text preview:

CS 267 Sources of Parallelism and Locality in SimulationParallelism and Locality in SimulationBasic Kinds of SimulationExample: Circuit SimulationOutlineA Model Problem: Sharks and FishSharks and FishDiscrete Event SystemsSlide 9Parallelism in Game of Life (S&F 3)PowerPoint PresentationSynchronous Circuit SimulationAsynchronous SimulationScheduling Asynchronous Circuit SimulationSummary of Discrete Even SimulationsParticle SystemsSlide 17Forces in Particle SystemsParallelism in External ForcesParallelism in Nearby ForcesSlide 21Slide 22Parallelism in Far-Field ForcesFar-field Forces: Particle-Mesh MethodsFar-field forces: Tree DecompositionSummary of Particle MethodsLumped Systems: ODEsSystem of Lumped VariablesCircuit ExampleStructural Analysis ExampleSolving ODEsSolving ODEs: Explicit MethodsSolving ODEs: Implicit MethodsSolving ODEs: EigensolversODEs and Sparse MatricesKey facts about SpMVParallel Sparse Matrix-vector multiplicationMatrix Reordering via Graph PartitioningGoals of ReorderingGraph Partitioning and Sparse MatricesImplicit Methods; EigenproblemsSummary: Common ProblemsExtra SlidesSlide 44Continuous 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 542D Implicit MethodAlgorithms 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 MeshesSlide 71CS267 Final ProjectsProject IdeasSlide 74Slide 75Review on Particle SystemsRegular Meshes (eg Sharks and Fish)Slide 78Slide 7902/02/2006 CS267 Lecture 61CS 267Sources of Parallelism and Locality in SimulationJames Demmelwww.cs.berkeley.edu/~demmel/cs267_Spr0602/02/2006 CS267 Lecture 62Parallelism and Locality in Simulation•Real world problems have parallelism and locality:•Many objects operate independently of others.•Objects often depend much more on nearby than distant objects.•Dependence on distant objects can often be simplified.•Scientific models may introduce more parallelism:•When a continuous problem is discretized, time dependencies are generally limited to adjacent time steps.•Far-field effects may be ignored or approximated in many cases.•Many problems exhibit parallelism at multiple levels•Example: circuits can be simulated at many levels, and within each there may be parallelism within and between subcircuits.02/02/2006 CS267 Lecture 63Basic Kinds of Simulation•Discrete event systems:•Examples: “Game of Life,” logic level circuit simulation. •Particle systems:•Examples: billiard balls, semiconductor device simulation, galaxies.•Lumped variables depending on continuous parameters:•ODEs, e.g., circuit simulation (Spice), structural mechanics, chemical kinetics.•Continuous variables depending on continuous parameters:•PDEs, e.g., heat, elasticity, electrostatics.•A given phenomenon can be modeled at multiple levels.•Many simulations combine more than one of these techniques.02/02/2006 CS267 Lecture 64Example: Circuit Simulation •Circuits are simulated at many different levelsLevel Primitives ExamplesInstruction level Instructions SimOS, SPIMCycle level Functional units VIRAM-pRegister Transfer Level (RTL)Register, counter, MUXVHDLGate Level Gate, flip-flop, memory cell ThorSwitch level Ideal transistor CosmosCircuit level Resistors, capacitors, etc.SpiceDevice level Electrons, silicon02/02/2006 CS267 Lecture 65Outline•Discrete event systems•Time and space are discrete•Particle systems•Important special case of lumped systems•Ordinary Differential Equations (ODEs)•Lumped systems•Location/entities are discrete, time is continuous•Partial Different Equations (PDEs)•Time and space are continuous•Next lecture•Identify common problems and solutionsdiscretecontinuous02/02/2006 CS267 Lecture 66A Model Problem: Sharks and Fish•Illustration of parallel programming•Original version (discrete event only) proposed by Geoffrey Fox•Called WATOR•Basic idea: sharks and fish living in an ocean•rules for movement (discrete and continuous)•breeding, eating, and death•forces in the ocean•forces between sea creatures •6 problems (S&F1 - S&F6)•Different sets of rules, to illustrate different phenomena•Available in many languages (see class web page)•Matlab, pThreads, MPI, OpenMP, Split-C, Titanium, CMF, CMMD, pSather •not all problems in all languages02/02/2006 CS267 Lecture 67Sharks and Fish•S&F 1. Fish alone move continuously subject to an external current and Newton's laws. •S&F 2. Fish alone move continuously subject to gravitational attraction and Newton's laws. •S&F 3. Fish alone play the "Game of Life" on a square grid. •S&F 4. Fish alone move randomly on a square grid, with at most one fish per grid point. •S&F 5. Sharks and Fish both move randomly on a square grid, with at most one fish or shark per grid point, including rules for fish attracting sharks, eating, breeding and dying. •S&F 6. Like Sharks and Fish 5, but continuous, subject to Newton's laws.02/02/2006 CS267 Lecture 68Discrete Event Systems02/02/2006 CS267 Lecture 69Discrete Event Systems•Systems are represented as:•finite set of variables.•the set of all variable values at a given time is called the state.•each variable is updated by computing a transition function depending on the other variables.•System may be:•synchronous: at each discrete timestep evaluate all transition functions; also called a state machine.•asynchronous: transition functions are evaluated only if the inputs change, based on an “event” from another part of the system; also called event driven simulation.•Example: The “game of life:”•Also known as Sharks and Fish #3: •Space divided into cells, rules govern cell contents at each step02/02/2006 CS267 Lecture 610Parallelism in Game of Life (S&F 3)•The simulation is synchronous•use two copies of the grid (old and new).•the value of each new grid


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?