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