Understanding Pipelining and Superscalar Execution

Zebulon Prime writes "Hannibal over at Ars has just posted a new article on processor technology. The article uses loads of analogies and diagrams to explain the basics behind pipelining and superscalar execution, and it's actually kind of funny (for a tech article). It's billed as a basic introduction to the concepts, but as a CS student and programmer I found it really helpful. I think this article is a sequel to a previous one that was linked here a while ago."

Comments

P&H - Pipelining

[minesweeper]

from the read-hennessy-and-patterson-first dept.

I just finished a CS course co-taught by Professor Patterson, and our primary text this semester was Patterson and Hennessy's Computer Organization and Design.

When we discussed pipelining this semester, the analogy used was the four stages of doing laundry: washing, drying, folding, and stashing. Here are the lecture notes (both PDF). The notes spend a good deal of time going over the hazards of pipelines and how to avoid them.

Re:P&H - Pipelining

[Jucius Maximus]

"I just finished a CS course [berkeley.edu] co-taught by Professor Patterson, and our primary text this semester was Patterson and Hennessy's Computer Organization and Design [berkeley.edu]. When we discussed pipelining this semester, the analogy used was the four stages of doing laundry: washing, drying, folding, and stashing. Here are the lecture [berkeley.edu] notes [berkeley.edu] (both PDF). The notes spend a good deal of time going over the hazards of pipelines and how to avoid them."

I just finished an engineering course with the exact same book, and we did that exact same pipelining example. I must say that the books is really very good at explaining the workings of the CPU.

The best teacher, though, is design. As part of the course, we all formed groups and actually designed and implemeted basic non-pipelined CPUs in VHDL and, if they fit, we implemented them on FPGA (field programmable gate array) boards. And by 'simple' CPUs, I mean that the CPUs have like 4K RAM, maybe 8 registers, ran at ~3 cycles per instruction, and only have about 12 instructions total. But it was REALLY informative because it forced us to learn the exact purpose of everything in the CPU.

Branch Prediction

[hng_rval]

One thing that his excellent analogy leaves out is the concept of branch prediction.

For those of you who didn't major in CS...

Imagine that we finish the first stage of building our SUV (building the engine) and commence with stage 2 (putting the engine in the stasis). While we are doing that we are building another engine for SUV #2. However, what if the next customer didn't want an SUV, but instead wanted a compact car. We have to throw away our engine for SUV #2 and start over. We wasted an entire stage!!

This analogy doesn't work so well it seems. So we'll stick with computers. If you have 5 instructions in your pipeline and one of them is a conditional branch (think, If the user hit ENTER, print a message to the screen. If they hit escape, BSOD).

If the conditional instruction is high up in the pipeline then every instruction under it could be wasted. Obviously, if the processor could predict which path the branch would follow it would waste less instructions.

Branch predicting algorithms are extremely interesting. The early ones were very simple with:

Prediction: Never take the branch
OR
Prediction: Always take the branch

People soon realized that most branches were in loops, so they came up with a new algorithm

Prediction: If the last time we were here we took the branch, take it again, otherwise don't take it. Basically, repeat what we did the last time we ran this instruction.

IIRC there are lots of branch prediction algorithms, some of which are eerily accuratae (above 90%). Unforunately, branch prediction requires cache which takes away from the cache your programs need.

Re:Branch Prediction

[jbrandon]

Unforunately, branch prediction requires cache which takes away from the cache your programs need.

This notes that the branch prediction unit has some cache that is separate from the other cache. It also notes that the PIII BPU has the "eerily accurate" prediction success you describe.

Holy Crap!

[poshgoat]

I have a final exam on this stuff tomorrow morning... It would seem there is a God...!!

Re:Optimizing

[PurpleFloyd]

What if you just want to understand what your computer does "underneath the hood"? Slashdot has quite a few people reading it who feel this way; they tend to call themselves "geeks". While this might not be that useful to programmers in the course of their jobs, it might be useful to Slashdot's and Ars' audience: people who want to understand.

And you're a CS student?!!!

[sparkz]

I knew this before I did a BSc in CS; what I learned later, was the real stuff - how memory speed affects pipelining; memory has not got significantly faster in the past decade, where CPUs have gone from 30MHz to 3GHz. Therefore even more pipelines are required now, as we sit around, cycle upon cycle, waiting for memory to feed us some data.

In fact, Alan Cox gave a talk on this recently: UMeet2002.