Finally, arriving somewhere that's here

Topic of the week : Pipelining, von Neumann, et cetera

Ok, this is easy. Ever went to subway for a dinner when you're hungry and that paper is due next week and you didn't like cooking anyway? The queue is long, and the superefficient workers still manage it somehow. The first one asks for your order and gets a bread. The second one puts the meat and the cheese inside and puts it in the oven. The third one puts in lettuce, tomatoes and the sauces for you, and you pay to the fourth one. Now, one way could be to do this entire process just for you, then for the next guy and then for the next guy. Of course, that'd take almost four times as much time as when every worker works on a different order at the same time. You don't want that.

We don't either. This is the basic principle behind most modern processors. Multiple instructions are processed at the same time, rather than one by one. While One instruction is being fetch, a previously fetched instruction is decoded, a previously decoded instruction is being executed, the result of a previously executed instruction is written back to the memory if needed, and another instruction writes its result to a register in the processor. Thus this makes it a five-stage pipeline, with the stages being instruction fetch (IF), instruction decode (ID), execute (EX), memory (MEM) and write back to register (WB). Ideally, this machine would run at 5 times the speed of another CPU which does all this one at a time.

Now, if you are with a girl you are dating, you may like to see what fillings she asks for, and you may ask for the same and say, "hey, we're so similar!". One way is to let her order while you wait in the line, and when she finishes and pays (aren't you a stupid boy! well, what were you doing taking a girl out to subway anyway :P ) and comes back you go ahead and order yours. Another way is to follow just behind her and see what she orders and you order accordingly. No unnecessary waiting! Such a situation is called a "dependency" and this measure to use the result of her action even before she has finished is called forwarding.

Of course, not everything is perfect. Maybe someone wants his sandwich baked which takes more time, while you standing behind him don't. So you'd like to go ahead, but this would break the pipeline. So you and everyone behind you have to "stall".

Well some chap named Tomasulo came along and said, ok, you can go ahead. you don't have to wait for him if you're not depending on him. So you're happy and all. But the other guy goes, hey, I came before him, why is he leaving before me? So you may have to wait before you pay and leave, i.e., finally, you go out in the order you came in, but in between you are free to execute in any order. This ordering of instructions is kind of important in most situations for programs as most of the times they are written assuming such an order.

Some people just don't like this. I mean, this kind of thing, where you have to stand in a line and wait for your turn when you don't give a rat's ass about the guy before you. This kind of architecture is called a von Neumann architecture - where you fetch instructions one by one from a stream and then execute it. I mean, what if you have a hundred people waiting in the line? You can increase the number of workers, but if everyone has to wait in a single line to come to them, that's just a waste.

It just so happens that this process of bringing in instructions one by one, cute as it is, is not infinitely scalable. The memory is not as fast as the CPU, and can't keep up. What's with all this bringing in and storing back? Why can't you just do the work where your instructions are?

Well, you could have the workers come to them. Like in a restaurant, get it? Well, yeah if the waiters cook at the table, that'd be pretty similar to it. These are called dataflow architectures; small processing elements reside where the memory is, and everything gets done in situ. Why dataflow? well you're not worried about a stream of instructions, which would be control flow - rather, you just worry about from whom you want to get the data, i.e. what are your friends getting, who decides what you order?

Too much for one sitting, eh? adieu.