DOC PREVIEW
Berkeley COMPSCI C267 - Source of Parallelism

This preview shows page 1-2-3 out of 10 pages.

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

Unformatted text preview:

CS267 Lecture 2 13/1/2004 CS267 Lecure 10 1CS 267Source of ParallelismKathy Yelickhttp://www.cs.berkeley.edu/~yelick/cs2673/1/2004 CS267 Lecure 10 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, temporal domain 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.3/1/2004 CS267 Lecure 10 3Example: 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 level3/1/2004 CS267 Lecure 10 4Basic 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.3/1/2004 CS267 Lecure 10 5Outline• Discrete event systems• Time and space are discrete• Particle systems• Important special case of lumped systems• Previous lecture• Ordinary Differential Equations (ODEs)• Lumped systems• Location/entities are discrete, time is continuous• Partial Different Equations (PDEs)• Time and space are continuous• Next lecturediscretecontinuous3/1/2004 CS267 Lecure 10 6Review on Particle Systems• In particle systems there are • External forces are trivial to parallelize• Near-field forces can be done with limited communication• Far-field are hardest (require a lot of communication)•O(n2) algorithms require that all particles “talk to” all others• Expensive in computation on a serial machine• Also expensive in communication on a parallel one• Clever algorithms and data structures can help• Particle mesh methods• Tree-based methodsCS267 Lecture 2 23/1/2004 CS267 Lecure 10 7Discrete Event Systems3/1/2004 CS267 Lecure 10 8Discrete 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: http://www.cs.berkeley.edu/~yelick/cs267/SharksAndFish• Space divided into cells, rules govern cell contents at each step3/1/2004 CS267 Lecure 10 9Parallelism in Sharks and Fish (Recap)• 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• Locality is achieved by using large patches of the ocean• Only boundary values from neighboring patches are needed.P4P1 P2 P3P5 P6P7 P8 P9Repeatcompute locally to update local systembarrier()exchange state info with neighborsuntil done simulating3/1/2004 CS267 Lecure 10 10Synchronous 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 (NP-complete)• Determines parallelism and locality.• Attempts to evenly distribute subgraphs to nodes (load balance).• Attempts to minimize edge crossing (minimize communication).edge crossings = 6edge crossings = 103/1/2004 CS267 Lecure 10 11Asynchronous Simulation• Synchronous simulations may waste time:• Simulate even when the inputs do not change,.• Asynchronous simulations update only when an event arrives from another component:• No global time steps, but individual events contain time stamp.• Example: Game of life in loosely connected ponds (don’t simulateempty ponds).• Example: Circuit simulation with delays (events are gates changing).• Example: Traffic simulation (events are cars changing lanes, etc.).• Asynchronous is more efficient, but harder to parallelize• In MPI, events are naturally implemented as messages, but how do you know when to execute a “receive”?3/1/2004 CS267 Lecure 10 12Scheduling Asynchronous Circuit Simulation• Conservative:• Only simulate up to (and including) the minimum time stamp of inputs.• May need deadlock detection if there are cycles in graph, or else “null messages”.• Example: Pthor circuit simulator in Splash1 from Stanford.• Speculative (or Optimistic):• Assume no new inputs will arrive and keep simulating.• May need to backup if assumption wrong.• Example: Timewarp [D. Jefferson], Parswec [Wen,Yelick].• Optimizing load balance and locality is difficult:• Locality means putting tightly coupled subcircuit on one processor.• Since “active” part of circuit likely to be in a tightly coupledsubcircuit, this may be bad for load balance.CS267 Lecture 2 33/1/2004 CS267 Lecure 10 13Summary of Discrete Even Simulations• Model of the world is discrete• Both time and space• Approach• Decompose domain, i.e., set of objects• Run


View Full Document

Berkeley COMPSCI C267 - Source of Parallelism

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 Source of Parallelism
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 Source of Parallelism 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 Source of Parallelism 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?