CS 267 Shared Memory Programming and Sharks and Fish ExampleParallel Programming OverviewA Model Problem: Sharks and FishSharks and Fish as Discrete Event SystemFish-only: the Game of LifeParallelism in Sharks and FishSlide 7Particle SystemsForces in Particle SystemsParallelism in External ForcesParallelism in Nearby ForcesSlide 12Slide 13Parallelism in Far-Field ForcesFar-field Forces: Particle-Mesh MethodsFar-field forces: Tree DecompositionSummary of Particle MethodsCreating Parallelism with ThreadsProgramming with ThreadsLanguage Notions of Thread CreationForking Posix ThreadsPosix Thread ExampleSPMD Parallelism with ThreadsCreating Parallelism in OpenMPOpenMP ExampleGeneral Parallelism in OpenMPLoop Level ParallelismSlide 28Dynamic ParallelismCommunication: Creating Shared Data StructuresShared Data and ThreadsShared Data and OpenMPSynchronizationSynchronization in Sharks and FishBasic Types of Synchronization: BarrierPairwise SynchronizationBasic Types of Synchronization: MutexesMutual Exclusion in OpenMPSummary01/13/19 CS267 Lecure 9 1CS 267Shared Memory ProgrammingandSharks and Fish ExampleKathy Yelickhttp://www.cs.berkeley.edu/~yelick/cs26701/13/19 CS267 Lecure 9 2Parallel Programming OverviewFinding parallelism and locality in a problem:•“Sharks and Fish” particle example today•More on sources of parallelism and locality next weekBasic parallel programming problems:1.Creating parallelism•Loop Scheduling 2.Communication between processors•Building shared data structures3.Synchronization•Point-to-point or “pairwise”•Global synchronization (barriers)01/13/19 CS267 Lecure 9 3A Model Problem: Sharks and Fish•Illustration of parallel programming•Original version (discrete event only) proposed by Geoffrey Fox•Called WATOR•Sharks and fish living in a 2D toroidal ocean•We can imagine several variation to show different physical phenomenon•Basic idea: sharks and fish living in an ocean•rules for movement•breeding, eating, and death•forces in the ocean•forces between sea creatures01/13/19 CS267 Lecure 9 4Sharks and Fish as Discrete Event System•Ocean modeled as a 2D toroidal grid•Each cell occupied by at most one sea creature01/13/19 CS267 Lecure 9 5Fish-only: the Game of Life•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 stable•The original Wator problem adds sharks that eat fish01/13/19 CS267 Lecure 9 6Parallelism in Sharks and Fish•The activities in this system are discrete events•The simulation is synchronous•use two copies of the grid (old and new)•the value of each new grid cell in new depends only on the 9 cells (itself plus neighbors) in old grid•Each grid cell update is independent: reordering or parallelism OK•simulation proceeds in timesteps, where (logically) each cell is evaluated at every timestepold ocean new ocean01/13/19 CS267 Lecure 9 7Parallelism in Sharks and Fish•Parallelism is straightforward•ocean is regular data structure•even decomposition across processors gives load balance•Locality is achieved by using large patches of the ocean•boundary values from neighboring patches are needed•although, there isn’t much reuse…•Advanced optimization: visit only occupied cells (and neighbors) load balance is more difficult01/13/19 CS267 Lecure 9 8Particle Systems•A particle system has •a finite number of particles.•moving in space according to Newton’s Laws (i.e. F = ma).•time is continuous.•Examples:•stars in space with laws of gravity.•electron beam and ion beam semiconductor manufacturing.•atoms in a molecule with electrostatic forces.•neutrons in a fission reactor.•cars on a freeway with Newton’s laws plus model of driver and engine.•Many simulations combine particle simulation techniques with some discrete event techniques (e.g., Sharks and Fish).01/13/19 CS267 Lecure 9 9Forces in Particle Systems•Force on each particle decomposed into near and far:force = external_force + nearby_force + far_field_force•External force•ocean current to sharks and fish world (S&F 1).•externally imposed electric field in electron beam.•Nearby force•sharks attracted to eat nearby fish (S&F 5).•balls on a billiard table bounce off of each other.•Van der Wals forces in fluid (1/r6).•Far-field force•fish attract other fish by gravity-like (1/r2 ) force (S&F 2).•gravity, electrostatics•forces governed by elliptic PDE.01/13/19 CS267 Lecure 9 10Parallelism in External Forces•External forces are the simplest to implement.•The force on each particle is independent of other particles.•Called “embarrassingly parallel”.•Evenly distribute particles on processors•Any even distribution works.•Locality is not an issue, no communication.•For each particle on processor, apply the external force.01/13/19 CS267 Lecure 9 11Parallelism in Nearby Forces•Nearby forces require interaction and therefore communication.•Force may depend on other nearby particles:•Example: collisions.•simplest algorithm is O(n2): look at all pairs to see if they collide.•Usual parallel model is decomposition* of physical domain:• O(n2/p) particles per processor if evenly distributed.Need to check for collisions between regions*often called “domain decomposition,” but the term also refers to a numerical technique.01/13/19 CS267 Lecure 9 12Parallelism in Nearby Forces•Challenge 1: interactions of particles near processor boundary:•need to communicate particles near boundary to neighboring processors.•surface to volume effect means low communication.•Which communicates less: squares (as below) or slabs?Communicate particles in boundary region to neighbors01/13/19 CS267 Lecure 9 13Parallelism in Nearby Forces•Challenge 2: load imbalance, if particles cluster:•galaxies, electrons hitting a device wall.•To reduce load imbalance, divide space unevenly.•Each region contains roughly equal number of particles.•Quad-tree in 2D, oct-tree in 3D.Example: each square contains at most 3 particlesSee: http://njord.umiacs.umd.edu:1601/users/brabec/quadtree/points/prquad.html01/13/19 CS267 Lecure 9 14Parallelism in Far-Field Forces•Far-field forces involve all-to-all interaction and therefore
View Full Document
Unlocking...