CS 5220

Applications of Parallel Computers

Discrete Event Simulations

Please click the play button below.

Discrete event systems

May be discrete or continuous time

Game of life, logic-level circuit simulation
Network simulation

By discrete event simulations, I mean simulations where events that do something interesting to the system happen at discrete times. Between events, either nothing happens, or the system behaves in a way that's so simple that we can "jump over" the time between events.

Finite state machines count as discrete event systems in my book. So do some physical systems. Air hockey comes to mind: we only really need any serious computation when there's a collision, and otherwise everything tends to move forward in a straight line at constant speed. Failure cascades can sometimes be modeled in an event-by-event way (or infection cascades, if we want to go there). And there are lots of engineered systems that can be reasoned with this way, too, from logical circuits to computer networks.

Discrete events

Finite set of variables, updated via transition function
Synchronous case: finite state machine
Asynchronous case: event-driven simulation
Synchronous example: Game of Life
Nice starting point — no discretization concerns!

More specifically, I am thinking of a finite set of variables, updated by a transition function. Note that the variables don't have to be drawn from finite sets! They could be real numbers, modulo the fact that we have to approximate the reals by floating point numbers when we compute.

Transitions may happen synchronously, meaning that they are associated with some clock. For example, it might be that we transition whenever the clock ticks, or whenever there is some external stimulus. Then there's the possibility that we might update the system - in part or in whole - asynchronously, based on when some internal event takes place. These aren't hard-and-fast classifications, though, and even synchronous systems may sometimes be simulated asynchronously. A good example is the Game of Life, which we'll talk about for a little while now.

One of the nice things about the Game of Life, and many discrete event systems, is that discrete things can be treated exactly on a computer. In contrast, the other systems we will discuss all involve some type of discretization error that we might have to think about.

Game of Life

Game of Life (John Conway):

Conway's "Game of Life" is a nice example. This is a cellular automata that shows some remarkable emergent behavior. The rules are simple. Every cell starts off in one of two states "alive" or "dead." Time proceeds in steps, or generations. A live cell with too few neighbors (none or one), or two many neighbors (more than three) will not be alive at the next step. A live cell with two or three neighbors will remain live at the next step. And a dead cell with exactly three live neighbors will become live at the next step.

There is clearly a lot of locality in this game. Every cell only interacts with its nearest neighbors at each step. There is also a lot of parallelism available; we can compute the update for one cell independent of the update for any other. That's all relevant for today.

It's also worth thinking about how we'd represent the board in the Game of Life. Each cell really only needs one bit! There is a lot of opportunity for vectorization here, if we're clever. We may talk about this in meeting.

Game of Life

Game of Life (John Conway):

Live cell dies with < 2 live neighbors
Live cell dies with > 3 live neighbors
Live cell lives with 2–3 live neighbors
Dead cell becomes live with exactly 3 live neighbors

Game of Life

Easy to parallelize by domain decomposition.

Update work involves volume of subdomains
Communication per step on surface (cyan)

Game of Life: Pioneers and Settlers

Some areas are more eventful than others!

Glider gun image (By Lucas Vieira - Own work, CC BY-SA
3.0,
https://commons.wikimedia.org/w/index.php?curid=101736)

Game of Life: Pioneers and Settlers

What if pattern is “dilute”?

Few or no live cells at surface at each step
Think of live cell at a surface as an “event”
Only communicate events!
- This is asynchronous
- Harder with message passing — when to receive?

Asynchronous Game of Life

How do we manage events?

Speculative — assume no communication across boundary for many steps, back up if needed
Conservative — wait when communication possible
- possible \(\not \equiv\) guaranteed!
- Deadlock: everyone waits for a send
- Can get around this with NULL messages

OK, so we suppose that we only communicate when a border cell becomes live. How do we manage this? One possibility is to keep computing in each processor's domain under the assumption that nothing interesting is happening at the border. If it turns out that something interesting did happen, we rewind time to when it happened, and go from there. This is speculative execution

Another option is to be conservative. Whenever something might have happened at a boundary, we wait to hear whether it actually did. Of course, if everyone is waiting for everyone else, we get into a deadlock. So we'd usually need a dummy message (sometimes called a NULL message) to tell neighboring processors that nothing interesting happened at an interface, and they should go ahead. Of course, the latency of such a null message might still slow us down, even if the message itself were very short!

Asynchronous Game of Life

How do we manage load balance?

No need to simulate quiescent parts of the game!
Maybe dynamically assign smaller blocks to processors?