CS 5220

Applications of Parallel Computers

Locality and Parallelism in Simulations

Please click the play button below.

Parallelism and locality

Real world exhibits parallelism and locality

Particles, people, etc function independently
Near-field interactions stronger than far-field
Can often simplify dependence on distant objects

The basic premise this week is that we can organize our simulation algorithms for high performance by recognizing that they, like the physical world, exhibit parallelism and locality. That is: our models often involve things that are independent except through a few careful modes of interaction. That's not just physical objects like air hockey pucks or elementary particles, but also people, vehicles, etc. There's a natural decomposition to lots of the world. Moreover, when we think about how things in the world interact, we find that the short-range interactions are often a lot stronger and more complicated than far-range interactions. Even when there is significant interaction at a long range, it's often simplified. If we're modeling the motion of the earth through space, we might need to keep track of gravitational interactions with all the other planets in our solar system. But to the extent that we need to keep track of nearby solar systems at all, we can probably just treat them as single point masses in space. Distance blurs things out.

Parallelism and locality

Can get more parallelism / locality through model

Limited dependency between adjacent time steps
Can neglect or approximate far-field effects

Parallelism and locality

Often get parallelism at multiple levels

Hierarchical circuit simulation
Interacting models for climate
Parallelizing individual experiments in MC or optimization

Basic styles of simulation

Often more than one type of simulation appropriate.
Sometimes more than one at a time!

The rest of the lecture-lets this week dig into four classes of simulations in a little more detail, with an eye to different ways of thinking about locality and parallelism in each.

We'll start with discrete event systems, with Conway's "Game of Life" as a convenient example. Then we'll talk about particle systems, where "particles" is a general term that refers not only to discrete particles in physics, but also to discrete entities like people in a simulation of a crowd. It also can refer to "chunks" of matter in a simulation of something that we usually consider as a continuum - we'll see such a method, sometimes called smoothed particle hydrodynamics, in the next project. Then we'll talk about lumped parameter systems and distributed parameter systems - or, if you prefer, ODE and PDE models.

There's a lot here. I hope you'll find it as entertaining as I do!