7.1 Parallelism
| The most obvious way to implement parallelism would be to have a dedicated processor for each simulation object, and to have an operating system that keeps all these processors running in lockstep synchronization with each other. At this stage in the history of computer science, of course, our computers are serial. At best you might have four processors running on your desktop machine. We simulate parallelism by keeping a master array of our 'physics objects' and trying to arrange our program so that the updates of the objects happen in a parallel fashion. But why use an array? Why not give each object a concurrent execution thread, and let the threads execute in parallel? The fact is, by default, threads aren't really parallel. There's no way for them to get around the fundamental fact that your machine's computations are being carried out by, normally, a single processor that works its way down a long one-dimensional column of machine-code instructions, now and then jumping up and down the column, but never carrying out more than one instruction at once. The operating system gives first one thread a little execution time, then another, then another, with the actual scheduling being something that's fairly fluid and hard to control. Indeed, if you give each of your objects its own thread, you'll find that the activities of the threads are far from parallel. One thread may get, say, two hundredths of a second in which to execute, the next thread may get three hundredths of a second, a third may get one hundredth of a second, and so on. For certain kinds of simulations this disorder doesn't matter. But if you want your simulation to be as close to a parallel physical process as possible, you'll have more success if you keep the simulation objects in a single array and maintain a strict, logical control over the order in which the objects execute their individual simulation steps. When we simulate physics objects, we an regard our objects as having two main simulation- related methods : (a) an update() method in which they look at all the objects around them, detecting forces, collisions, etc. and (b) a move(dt) method in which they change their positions . The dt argument is the current timestep that has been passed down from the application as described in Chapter 6: Animation. A little more generally , if we think of our physics objects as active critters, we might say that (a) the update method incorporates looking, thinking, feeling, deciding and any other kind of individual behavior, while (b) the move method incorporates Newton's laws of motion. In the Pop Framework, the programmer overrides the update method to individualize the critters. And the move method is a non-virtual method which we don't intend to override. If we have a collection of objects numbered, say, from 0 to COUNT-1, there are various ways that we might systematically make an update and a move method call for each object. On the one hand, we could do something like the following. This is an approach that we would consider wrong.
The problem with the approach just described is that, although object 0 sees the old position of object 1, object 1 will only see the new, moved position of object 0. Instead we could do something more parallel, something like this.
In this second approach, all of the objects look at and react to each other in the initial position. All the updates happen before anything moves. They don't actually carry out their motions until they've all had a look and decided what to do. This is a more parallel approach to the simulation. To make these ideas clear, consider the following situation. Critter #0 is chasing critter #1. Critter #0's goal is to touch critter #1 as often as possible, critter #1's goal is to run away from critter #0. In Figure 7.1, we show the effects of the two different ways of grouping the various update and move calls. In the figure, we draw an arrow to indicate the current ' intention ' of a critter regarding its next move step, and we erase the arrow once the intended move has been carried out. Figure 7.1. The wrong and the right way to simulate At the bottom of the left-hand column of events drawn in Figure 7.1, critter #0 does not think it has tagged critter #1, and critter #1 feels it's been tagged once. At the bottom of the right-hand column, critter #0 feels it hasn't tagged critter #1, and critter #1 feels it hasn't been tagged. The right-hand column shows a parallel simulation, the simulation in the left-hand column is not parallel. In thinking this over, remember that
In terms of code, to say that we want to have a parallel simulation means that we don't want to have a runcycle like this: for (i=0; i<COUNT; i++) { physicsobject[i].update(); physicsobject[i].move(dt); } Instead we want to do something more like this: for (i=0; i<COUNT; i++) physicsobject[i].update(); for (i=0; i<COUNT; i++) physicsobject[i].move(dt); Again, what's wrong with the first approach is that here the physicsob ject[0] would already be at its new position before physicsobject[1] looks at it. So the behavior of the simulation would depend heavily on the order in which the physicsobject members happen to be listed in the array. We want to try and design our simulation so that the behavior is independent of the order in which the objects happen to be listed. Now why exactly do we speak of this kind of simulation as 'parallel'? The idea is that we are emulating parallelism by repeatedly freezing and thawing the flow of simulated time. We freeze the flow of simulated time while our processor takes the time to let each critter look at the others and decide what to next. Then we thaw the simulated time and give a dt tick to each of the critters to move with. Then we freeze time again and let the critters evaluate the new state of affairs. And so on.  |
