Finally, An Exciting Project!

Just shot this off to my advisors, and I figure it's accessible enough share here rather than at my (largely ignored) research blog. Hopefully this makes sense to non-CS people. If it doesn't the backtracking posts at said research blog might help.

Using Games to Teach Shared Memory Parallelism

It seems to me that there are two approaches one can take with designing educational games. If you’re simply looking to teach facts (arithmetic, spelling, geography), you can focus on rote skill building. Decades of Math Blaster and Where in the World is Carmen San Diego and who knows what else have made it plain that, if you create a compelling enough environment, you can simply drill basic ideas over and over again and players will eventually learn them. If you’re lucky, they might even begin to pick up on the underlying principles, but this is less essential at the point where such games are generally in play. It doesn’t matter as much if players pursue a trial and error approach so long as they eventually build up the right stimulus-response pairing so that, when presented with “7 + 6”, they spout out “13”.

When teaching concepts, however, things become more difficult. The goal in this instance is to help the player realize that they *already* understand what we’re asking of them by transporting the underlying principles into a familiar environment. This means we’re not just taking some ultimate response into account. The process, and learning how to relate that process to desired domain, becomes the focus. This makes it much harder to properly develop games to teach concepts, since the process and the eventual relationships that form are completely outside of our control. This means that we need to make sure that our games are designed with metaphors that accurately represent the original problem or system and that they main focus is on tasks we actually want to promote.

When we first began discussing ideas for a game to “teach” shared memory concurrency, it was suggested that I work with trains. The basic idea was that trains are exciting and that signals and switches are already built into the system. For a handful of basic ideas, this seemed like a great approach, but as soon as we expand to more complicated problems, it falls apart. Consider, for instance, the most basic problem with shared memory concurrency: race conditions.

For the simplest case, two threads running through the same piece of sensitive code, this makes sense. We can have trains running on parallel tracks that eventually become a single track. If both trains try to do this simultaneously, they will crash. Thus, we need policies to ensure that only one train makes the transition at a time.

Let’s look at a more complicated example, though. Let’s say we have two completely different sections of code, both of which touch the same global variable. Suddenly, our trains are no longer running on parallel tracks. They’re working in completely different regions of space. How, then, do we signify that our two trains need to somehow limit one another’s movement?

Sure, we could introduce new elements -- say, pressure guages rigged to bombs that will cause the track to explode if the weight of more than one train touches any segment to which the sensor is connected. But that starts to expand our metaphor beyond what is reasonable. It makes our metaphor instantly unrelatable, even if somewhat more exciting.

Let’s also consider the basic nature of computer programs as humans write them, which tend to be broken into numerous subroutines. A subroutine is called in one spot, control jumps to that subroutine, and then, when the subroutine is finished, control returns to the spot it which the subroutine was called. This also cannot be readily modeled with the train metaphor, as an actual train moves along a single continuous piece of track. It doesn’t teleport all over kingdom come before eventually reaching its destination.

The underlying problem here is one of metaphor. We have too few types of objects, and they’re related in the wrong way. Let’s take a moment, then, to look at the requirements for an effective metaphor for a shared memory system:

First of all, let’s consider the things that need to be modeled. Obviously, we need multiple actors that can represent our threads, and we need something to guide the behavior of these actors to represent our code. The train metaphor has both of these in the trains and the tracks. It is important to note here that the tracks in the train metaphor can only represent the program, since they fundamentally guide the behavior of the trains. We need more than this, though. We need to be able to see why shared memory, in particular, is difficult. This means that our metaphor needs to contain some way of representing memory and another way of representing the values in that memory so that we see why things are going wrong.

Moreover, since threads operating in a shared memory environment can see virtually any piece of the shared address space at virtually any time, we need this memory to be obviously accessible to our actors. Between this necessity and the obvious requirement that memory somehow contain values, it becomes obvious that memory must be a physical space and not a logical one in our metaphor. Our program, on the other hand, just needs to be some sort of set of instructions that the user can see and augment.

Note that I didn’t include any sort of signals or locks or control statements of any sort as necessities for our basic metaphor. That’s because these control statements are primarily what we want to teach. This means that they are more effective if we highlight them by making them additions to our otherwise familiar situation. Much of the problem with programming shared memory concurrency is that it isn’t ultimately intuitive why we need these sorts of constructs. Our primary experiences of concurrency are physical, and the physical world places obvious, unviolatable limitations on what can and cannot be done in parallel. Chiefly, two objects cannot occupy the same physical space (though I know a handful of metaphysicians who disagree under certain circumstances).

Our goal was always to make control of these constructs one of the chief mechanisms of “play”, and by injecting the constructs into the situation as somehow unintuitive and alien, we increase the strength of the relationship between our metaphor and our “real world” circumstances.

If all that we were trying to teach was concurrency, this would be sufficient, but we’re looking to teach parallelism, the use of concurrency to provide improved performance via domain decomposition. This means that we want to place one more restriction on our metaphor. We want our “instructions” to be something that the player can actively divvy up between our actors to see how different approaches work. This was, in my opinion, another failing of the train metaphor for this particular problem. Establishing conditions for different signals to be sent between trains doesn’t do anything to modify the way the routes themselves operate. There is no obvious domain to decompose.

With all of these considerations in place, I would like to suggest the basic framework for a new game to teach parallelism in a shared memory environment, one I like to call Too Many Cooks!

The basic idea is that you control a kitchen with several cooks, all working together to produce enough food of a minimum quality to satisfy a given number of customers within a certain time limit. You begin with a certain number of cooks and a list of recipes. Recipes are divided into steps, and each recipe has its own quality ranking and will feed a different number of people.

At each level, your goal is to select recipes that meet or exceed the level requirements and divide the work of preparing them up among your chefs (by assigning either whole recipes or tasks within recipes to individual chefs) so as to finish under the time limit. At the end of each level, you recieve a score based on the average quality of your food and how far under the time limit you came.

So, we have our two foundational ideas that make this a metaphor for a (parallel) computer program: our actors and our instructions. We also have the task of domain decomposition. What makes this a shared memory system, then, are the limitations of physical space.

The kitchen is divided up into regions for different tasks. Counters for chopping. Ovens for baking. Stove tops for simmering. Freezers for cooling. Chefs will retrieve ingredients (values) from some bottomless pantry or from other workstations and transfer them around from chef to chef and station to station as the recipe is completed. Every time you assign a chef an instruction, you tell him where (s)he will find the necessary ingredients and where (s)he will work at the task. However, our chefs, much like computers, are a little bit stupid and do not communicate directly.

This means that, if Chef A needs onions that Chef B is chopping, but Chef B is not finished chopping them, Chef A may suddenly find himself fingerless as he intrudes on Chef B’s activities and the level will be failed. Similarly, if Chef A is expecting tomatoes at a given workstation, but Chef C hasn’t yet gotten around to preparing them but the cucumbers that Chef D had just finished up for Chef E are still sitting there, Chef A will gladly take them, ruining his recipe and resulting in unhappy (vomitting) customers and another failure of the level. There can be all sorts of other situations like this where things go wrong because of a lack of communication and timing.

What this means is that players needs to do two more things. First of all, they must be intentional in their assignment of tasks between chefs in order to minimize such conflicts (especially of the second sort described). More important, though, it is their job, after assigning tasks and locations to the chefs, to annotate the recipe with a number of markers that result in indirect communication between chefs. In the first example, for instance, Chef B could put up a sign that would prevent other chefs from intruding on his space.

Again, it would seem somewhat non-intuitive to players why they would need these signs. In the real world, chefs wouldn’t be so stupid. But that’s the entire point. It makes the task memorable and thus, ideally, helps in its transfer to the actual domain of writing programs.

The game will begin in a small kitchen with only two chefs and requirements that allow them to work on individual recipes with no communication in order to simply pass. But, as time progresses, you will unlock a larger stable of chefs and more elaborate recipes and requirements will mandate complicated distribution of work and consistent use of signals in recipe preparation. This larger grouping of chefs and recipes will remain available for the player to go back and complete earlier challenges with more elaborate approaches for a higher score.

There are lots of specifics yet to be worked out, and I feel like I’m neglecting to mention things that I’d already thought of. Even once I figure out all of the foundational ideas, development of this game will not be a simple task. Tweaking and balancing everything in this system from level requirements to recipe complexity to interface in order to make it engaging and reasonable is going to be terribly difficult, but that’s a problem faced by any game devloper, particularly, I would imagine, those working on educational games. Still, it seems to me like a solid beginning point, and I would welcome any criticisms or suggestions for its improvment as I get things hashed out on paper and start to figure out a development platform.