CS 267 Applications of Parallel Computers Lecture 10: Sources of Parallelism and LocalityRecap: Parallel Models and MachinesOutlineSimulation Models and A Simple ExampleSources of Parallelism and Locality in SimulationBasic Kinds of SimulationA Model Problem: Sharks and FishDiscrete Event SystemsSlide 9Sharks and Fish as Discrete Event SystemThe Game of Life (Sharks and Fish 3)Parallelism in Sharks and FishParallelism in Synchronous Circuit SimulationParallelism in Asynchronous Circuit SimulationScheduling Asynchronous Circuit SimulationParticle SystemsSlide 17Forces in Particle SystemsParallelism in External ForcesParallelism in Nearby ForcesParallelism in Nearby Forces: Tree DecompositionParallelism in Far-Field ForcesFar-field forces: Particle-Mesh MethodsFar-field Forces: Tree DecompositionLumped Systems ODEsSystem of Lumped VariablesCircuit ExampleSystems of Lumped VariablesSolving ODEsParallelism in Sparse MatricesPartitioningMatrix ReorderingCS267 L10 Sources of Parallelism.1Demmel Sp 1999CS 267 Applications of Parallel ComputersLecture 10: Sources of Parallelism and LocalityJames Demmelhttp://www.cs.berkeley.edu/~demmel/cs267_Spr99CS267 L10 Sources of Parallelism.2Demmel Sp 1999Recap: Parallel Models and Machines°Machine models Programming models•shared memory - threads•distributed memory - message passing•SIMD - data parallel - shared address space°Steps in creating a parallel program•decomposition •assignment•orchestration •mapping°Performance in parallel programs•try to minimize performance loss from-load imbalance-communication-synchronization-extra workCS267 L10 Sources of Parallelism.3Demmel Sp 1999Outline°Simulation models°A model problem: sharks and fish°Discrete event systems°Particle systems°Lumped systems (Ordinary Differential Equations, ODEs)°(Next time: Partial Different Equations, PDEs)CS267 L10 Sources of Parallelism.4Demmel Sp 1999Simulation Modelsand A Simple ExampleCS267 L10 Sources of Parallelism.5Demmel Sp 1999Sources of Parallelism and Locality in Simulation°Real world problems have parallelism and locality•Many objects do not depend on other objects•Objects often depend more on nearby than distant objects•Dependence on distant objects often “simplifies”°Scientific models may introduce more parallelism•When continuous problem is discretized, may limit effects to timesteps•Far-field effects may be ignored or approximated, if they have little effect°Many problems exhibit parallelism at multiple levels•e.g., circuits can be simulated at many levels and within each there may be parallelism within and between subcircuitsCS267 L10 Sources of Parallelism.6Demmel Sp 1999Basic Kinds of Simulation°Discrete event systems•e.g.,”Game of Life”, timing level simulation for circuits °Particle systems•e.g., 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 these modeling techniquesCS267 L10 Sources of Parallelism.7Demmel Sp 1999A 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 rule, to illustrate different phenomena°Available in Matlab, Threads, MPI, Split-C, Titanium, CMF, CMMD, pSather (not all problems in all languages)°www.cs.berkeley.edu/~demmel/cs267/Sharks_and_Fish (being updated)CS267 L10 Sources of Parallelism.8Demmel Sp 1999Discrete Event SystemsCS267 L10 Sources of Parallelism.9Demmel Sp 1999Discrete Event Systems°Systems are represented as•finite set of variables•each variable can take on a finite number of values•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 finite 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°E.g., functional level circuit simulation•state is represented by a set of boolean variables (high & low voltages)•set of logical rules defining state transitions (and, or, etc.)•synchronous: only interested in state at clock ticksCS267 L10 Sources of Parallelism.10Demmel Sp 1999Sharks and Fish as Discrete Event System°Ocean modeled as a 2D toroidal grid°Each cell occupied by at most one sea creature°S&F3, 4 and 5 are variations on thisCS267 L10 Sources of Parallelism.11Demmel Sp 1999The Game of Life (Sharks and Fish 3)°Fish only, no sharks°An new fish is born if•a cell is empty•exactly 3 (of 8) neighbors contain fish°A fish dies (of overcrowding) if•cell contains a fish•4 or more neighboring cells are full°A fish dies (of loneliness) if•cell contains a fish•less than 2 neighboring cells are full°Other configurations are stableCS267 L10 Sources of Parallelism.12Demmel Sp 1999Parallelism in Sharks and Fish°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, where each cell is updated at every timestep°Easy to parallelize using domain decomposition°Locality is achieved by using large patches of the ocean•boundary values from neighboring patches are needed°If only cells next to occupied ones are visited (an optimization), then load balance is more difficult. The activities in this system are discrete eventsP4P1 P2 P3P5 P6P7 P8 P9CS267 L10 Sources of Parallelism.13Demmel Sp 1999Parallelism in Synchronous Circuit Simulation°Circuit is a graph made up of subcircuits connected by wires•component simulations need to interact if they share a wire•data structure is irregular (graph), but simulation may be synchronous•parallel algorithm is bulk-synchronous -compute subcircuit
View Full Document
Unlocking...