Ratatouille: Rats doing massively parallel computing

The Pixar film, Ratatouille, goes where no rat has gone before: the kitchen. It is the story of Remy, a gastro-rat with a taste for cooking, and how he becomes a Chef in a 5-star parisian restaurant. It's a brilliant film whether or not you are interested in cooking (or computing), but how is Remy's progress linked to a massively important computer science problems that has remained essentially unsolved for half a century?

The computer science problem boils down to how best to get work done quickly when you have lots of helping hands: how to write massively parallel programs. We may be struggling but the rats obviously have a handle on the problem: at least those in Ratatouille did. When it comes to the crunch and the rats need to cook, they all wade in - hundreds of them, all continually busy, swarming over the kitchen, all playing a useful part to get the meals ready. They had 'parallelism' down to a tea!

It turns out that parallelism is more important now than ever before because of the rise of 'multicore' chips. They are essentially just computer chips with lots of processors allowing them to do multiple things at once. So what can we learn from the rats of Ratatouille about multi-core? Well, the cooking we see in the film follows the progression of computers from single, simple processors towards multi-core chips and massive parallelism.

Early in the film, gastro-rat Remy learns to cook from reading an old lady's cookery bookswhile she sleeps. At this point he cooks just like a traditional computer computes. Both he and the computer can do only one thing at a time. A computer follows a program - a series of steps to follow to get something done - and Remy does too. Recipes are just instructions to make a dish so basically just programs for cooks rather than computers to follow. Follow the instructions precisely and you should end up with the same tasty dish as the expert chef. Remy cooks by following the recipes of the great chef, Gusteau. The key thing in a recipe, for beginners at least, is that it not only tells you exactly what to do in what order but only gives you one thing to do at once. After all a budding chef can't easily do two things at once. Neither can a traditional computer. Programs generally just say how to do things one after another. In most programming languages there is no way even to say how to do several things at the same time.

Humans are great at multitasking so as a cook becomes more confident they start to overlap some of the tasks, checking what to do next while stirring the pot perhaps, or leaving a sauce to simmer while chopping the herbs. Computers do similar things. Even though the pragram says to do things one after another, one part of the processor might be fetching the next instruction while the main part is carrying out the last one, for example. This isn't multi-core - there is still just one processor. It is just that the processor is more complicated so can do some simple things at the same time. It still only really follows one instruction at once even if it is doing some multitasking. Even a ratty chef, cant chop carrots and peel potatoes at the same time.

Raising the temperature

That's ok as far as it goes. But what happens when you raise the temperature. What happens when you are not just preparing one meal but are the chef running a whole restaurant. Then you have to cook dozens of meals: starters, main courses and desserts. Everyone at a table wants their meals to arrive together...and they don't want any to be cold. Nor will they be happy to have to sit around for hours waiting just because the restaurant is busy. Doing one thing at a time doesn't cut the mustard.

The solution is to go parallel as we see in Gusteau's restaurant later in the film after Remy's colony on being discovered by the old lady (with a shotgun) flee to Paris. As Remy notes looking down on Gusteau's kitchen the cooking there is done by a team of chefs each with a specific role. Some are specialists - great at their own thing - while others are more generalist, able to fill in as needed. The Chef de Cuisine (Skinner in the film) runs the whole thing - deciding the menus, organising the rest of the team, managing the process. The Sous-chef (here called Horst) is the second in command, filling in for the Chef de Cuisine or supporting any of the other chefs when they are busy. The main cooking is done by station chiefs: the Chef de Partie. Each (such as Colette, a female chef who has made it in a man's world) runs a station. Each station usually covers a particular kind of cooking and so that Chefs follows particular kinds of recipes. One might be responsible for preparing fish, another for the sauces, another for cold dishes, and so on. A series of other people (like Linguine in the film) act as the dogs bodies doing unskilled work like washing up, peeling potatoes, chopping vegetables and so on.

Computer design followed a similar path. As the speed demands increased - people wanting fast, realistic games, for example - the computer designers went parallel. Rather than have a single processor chip doing one thing at a time they started to include other specialist chips that were good at a single job. Graphics processors for example could prepare the graphics to appear on the screen while the main chip was getting on with something else. A special floating-point unit could deal with complex arithmetic when needed. The programs giving the instructions didn't really change though - they still set out things to be done one at a time. It was left to specialist software - acting a bit like the Chef de Cuisine - to manage the process and ensure things ran smoothly with jobs being dished out appropriately. For computers that means analysing those programs and converting them into instructions that keep all the separate units busy. As the separate specialist units available are fixed, dividing up the jobs just has to be done once, as the way the chefs work from one day to the next is fairly stable even though different dishes will be ordered.

The thirst for more

Unfortunately, we never stop thirsting for more juice from our applications. There is always something more we could do if the computer could just go that little bit faster. Making processors go faster and adding specialist chips only takes you so far. What happens when you run out of specialist jobs you can identify when you design the computer? What happens when you have periods where your specialists are sitting around with nothing to do - perhaps no one orders fish today - while others are struggling to cope. The chip designers have stepped up to the plate and solved this problem with the newest computer designs. This is where multi-core enters the scene. Devising ever more specialist roles in advance, with ever more complex schemes to keep each busy starts to feel like a lost cause. Multi-core is a little like having lots and lots of cheap but highly skilled, generalist chefs, each willing and able to do anything: from peeling potatoes to putting the final touches to a fine sauce. As they come free from what they were doing, they step forward to do whatever needs doing next. If you have lots of help, this only works well if you can chop the jobs to be done into small chunks so no one is ever left waiting for something new.

In Ratatouille, a similar situation arises when the cooks walk out leaving the rats to run the kitchen and get the meals ready in a hurry. None are specialists but there are hundreds of them. As long as something can constantly be found for each and every one to do, with none left idle then the customers will maybe, just maybe get their meals. That is what happens. They swarm over the kitchen getting jobs done. They worked out a way to break all the big jobs down into little ones: chopping herbs, washing vegetables, fetching, frying, stirring: everything ready just when its needed by another rat to do its bit. No rat ever with nothing to do.

The multi-core solution is the equivalent of filling the kitchen with rats, except instead of lots of rats in a kitchen you have lots of processors on the chip. Imagine having a thousand processors available all capable of running their own program, the computer can potentially go a thousand times faster...but only if you can keep them all busy all the time.

That is where the unsolved problem comes in. To get that thousand times speed up, something as clever as Remy is needed that can take any task (like prepare the ordered meals as they come in) and tell every processor (every rat) exactly what to do and when. The rats have never cooked before so without instructions from Remy to follow they would have been lost. Likewise all those cores will sit idle unless their instructions give them something to do all the time.

The problem then is how do you create programs that make use of all this parallelism. One way is for programmers to write new kinds of programs that say explicitly how to split up the task amongst all the processors. Remy - obviously a wizard of a parallel programmer - apparently could do that in the kitchen as he did give all the rats instructions to keep them busy. Humans aren't so good at it it turns out as for real programs it is devilishly hard. You have to deal with the fact that when writing the program you won't know how many processors are actually available. We also haven't even really come up with a really good language for writing down such instructions yet, never mind writing the instructions themselves.

Another way is for the compilers to take normal serial programs and automatically split them up, creating a specific program from it for each core to follow. Unfortunately, we don't know how to do that well in general either! The solution may be to create special languages for each kind of application. Building sites are highly parallel too, for example, but the precise way they share out the work is not the same as in a kitchen. Similarly perhaps it would be better to have different languages and compilers for writing highly parallel software to simulate the aerodynamics of an aircraft than that for business applications. Perhaps the specialist knowledge of the specific kinds of jobs the programs are doing can make the job of splitting it up simpler.

That then is the challenge for a current generation of computer scientists - find a way to solve the one Remy solved for Gusteau's kitchen (but for any problem not just for kitchens). Come up with ways that make it possible for humans to more easily write massively-parallel programs, create new programming languages so these programs can be written more easily, and develop better compilers that can automatically split up the programs to make maximum use of however many processors are available.

The rats can do it, let's hope we can too. After all, as Gusteau always said, "Anyone can cook!" Hopefully one day anyone will be able to parallel program too.

This article is inspired by a talk by Fran Allen, the Turing Award winner who spent 45 years working at IBM. The talk was given at Queen Mary, University of London in May 2011 (oh and it was inspired by the rats of Ratatoulle too, of course).