DOC PREVIEW
Berkeley COMPSCI C267 - Lecture Notes

This preview shows page 1-2-3-4-5-38-39-40-41-42-43-77-78-79-80-81 out of 81 pages.

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

Unformatted text preview:

02/14/2007 CS267 Lecture 9 1CS 267Sources of Parallelism and Locality in SimulationKathy Yelickwww.cs.berkeley.edu/~yelick/cs267_sp0702/14/2007 CS267 Lecture 9 2Parallelism 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/14/2007 CS267 Lecture 9 3Basic 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/14/2007 CS267 Lecture 9 4Example: Circuit Simulation • Circuits are simulated at many different levelsExamplesPrimitivesLevelElectrons, siliconDevice levelSpiceResistors, capacitors, etc.Circuit levelCosmosIdeal transistorSwitch levelThorGate, flip-flop, memory cellGate LevelVHDLRegister, counter, MUXRegister Transfer Level (RTL)VIRAM-pFunctional unitsCycle levelSimOS, SPIMInstructionsInstruction level02/14/2007 CS267 Lecture 9 5Outline• 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/14/2007 CS267 Lecture 9 6A 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)• See http://www.cs.berkeley.edu/~demmel/cs267/Sharks_and_Fish02/14/2007 CS267 Lecture 9 7Sharks 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/14/2007 CS267 Lecture 9 8Discrete Event Systems02/14/2007 CS267 Lecture 9 9Discrete 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 functiondepending 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/14/2007 CS267 Lecture 9 10Parallelism 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 P8 P9Repeatcompute locally to update local systembarrier()exchange state info with neighborsuntil done simulating02/14/2007 CS267 Lecture 9 11Regular Meshes (eg Game of Life)• Suppose graph is nxn mesh with connection NSEW neighbors• Which partition has less communication?n*(p-1)edge crossings2*n*(p1/2 –1)edge crossings• Minimizing communication on mesh ≡minimizing “surface to volume ratio” of partition02/14/2007 CS267 Lecture 9 12Synchronous 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) of subcircuits.• Parallel algorithm is timing-driven or synchronous:• Evaluate all components at every timestep (determined by known circuit delay)• Graph partitioning assigns subgraphs to processors• Determines parallelism and locality.• Attempts to evenly distribute subgraphs to nodes (load balance).• Attempts to minimize edge crossing (minimize communication).• Easy for meshes, NP-hard in generaledge crossings = 6edge crossings = 1002/14/2007 CS267 Lecture 9 13Sharks & Fish in Loosely Connected Ponds• Parallelization: each processor gets a set of ponds with roughly equal total area•work is proportional to area, not number of creatures• One pond can affect another (through streams) but infrequently02/14/2007 CS267 Lecture 9 14Asynchronous Simulation• Synchronous simulations may waste time:• Simulates even when the inputs do not change,.• Asynchronous (event-driven) simulations update


View Full Document

Berkeley COMPSCI C267 - Lecture Notes

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 Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?