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

This preview shows page 1-2-3-22-23-24-44-45-46 out of 46 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 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 46 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 46 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 46 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 46 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 46 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 46 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 46 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 46 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 46 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 SimulationSharks & Fish in Loosely Connected PondsAsynchronous SimulationScheduling Asynchronous Circuit SimulationDeadlock in Conservative Asynchronous Circuit SimulationSummary of Discrete Event SimulationsParticle SystemsSlide 19Forces in Particle SystemsExample S&F 1: Fish in an External CurrentParallelism in External ForcesParallelism in Nearby ForcesSlide 24Slide 25Parallelism in Far-Field ForcesFar-field Forces: Particle-Mesh MethodsFar-field forces: Tree DecompositionSummary of Particle MethodsLumped Systems: ODEsSystem of Lumped VariablesCircuit ExampleStructural Analysis ExampleGaming ExampleSolving ODEsSolving ODEs: Explicit MethodsSolving ODEs: Implicit MethodsSolving ODEs: EigensolversImplicit Methods; EigenproblemsSpMV in Compressed Sparse Row (CSR) FormatParallel Sparse Matrix-vector multiplicationMatrix Reordering via Graph PartitioningGoals of ReorderingGraph Partitioning and Sparse MatricesSummary: Common ProblemsMotif/Dwarf: Common Computational Methods (Red Hot  Blue Cool)CS267 Lecture 41CS 267Sources of Parallelism and Locality in SimulationJames Demmelwww.cs.berkeley.edu/~demmel/cs267_Spr1201/26/2012CS267 Lecture 42Parallelism and Locality in Simulation•Parallelism and data locality both critical to performance•Recall that moving data is the most expensive operation•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.•Example of all three: particles moving under gravity•Scientific models may introduce more parallelism:•When a continuous problem is discretized, time dependencies are generally limited to adjacent time steps.•Helps limit dependence to nearby objects (eg collisions)•Far-field effects may be ignored or approximated in many cases.•Many problems exhibit parallelism at multiple levels01/26/2012CS267 Lecture 43Basic Kinds of Simulation•Discrete event systems:• “Game of Life,” Manufacturing systems, Finance, Circuits, Pacman, …•Particle systems:•Billiard balls, Galaxies, Atoms, Circuits, Pinball …•Lumped variables depending on continuous parameters • aka Ordinary Differential Equations (ODEs),•Structural mechanics, Chemical kinetics, Circuits, Star Wars: The Force Unleashed•Continuous variables depending on continuous parameters•aka Partial Differential Equations (PDEs)•Heat, Elasticity, Electrostatics, Finance, Circuits, Medical Image Analysis, Terminator 3: Rise of the Machines•A given phenomenon can be modeled at multiple levels.•Many simulations combine more than one of these techniques.•For more on simulation in games, see•www.cs.berkeley.edu/b-cam/Papers/Parker-2009-RTD01/26/2012CS267 Lecture 44Example: 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, siliconLumpedSystemsDiscreteEventContinuousSystems01/26/2012CS267 Lecture 45Outline•Discrete event systems•Time and space are discrete•Particle systems•Important special case of lumped systems•Lumped systems (ODEs)•Location/entities are discrete, time is continuous•Continuous systems (PDEs)•Time and space are continuous•Next lecture•Identify common problems and solutionsdiscretecontinuous01/26/2012CS267 Lecture 46A 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 languages)•Some homework based on these01/26/2012CS267 Lecture 47Sharks 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.CS267 Lecture 48Discrete Event Systems01/26/2012CS267 Lecture 49Discrete 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 step01/26/2012CS267 Lecture 410Parallelism 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 cell depends only on 9 cells (itself plus 8 neighbors) in old grid.•simulation proceeds in timesteps-- each cell is updated at every step.•Easy to parallelize by dividing physical domain: Domain Decomposition•Locality is achieved by using large patches of the ocean•Only boundary values from neighboring patches are needed.•How to pick shapes of domains?P4P1 P2 P3P5 P6P7


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?