Result of increasing number of stages in pipeline processor

We are learning about singlecycle/multicycle processors and in the book it is said

Pipeline processor is k(number of stages) times faster than single cycle processor.

However at a later point it is said that the number of stages doesn't matter, clock's period is the only thing affecting the speedup. Which one is it I'm confused.

• We are learning about single cores. So if the clock speed remains the same an increase in K would yield an insignificant decrease in time of execution for N instructions? – k.S Mar 20 at 0:56
• I think they mean that a pipelined processor is faster than a multicycle processor. If multicycle means that each instruction has to take multiple cycles to do all of that stuff. – Oskar Skog Mar 20 at 4:34

3 Answers

Ideally, it can be simplified a lot. Suppose there are these classic five steps needed to complete an instruction:

1. IF -- instruction fetch from instruction memory (also increment PC)
2. DECODE -- instruction decode
3. EXEC -- instruction execution (ALU operation, for example)
4. MEM -- memory read or write
5. WRITE BACK -- register write-back from ALU

(Sometimes, a separate 6th item is required to increment the PC.)

Not every instruction requires all of these, of course. But that's the basic layout.

Suppose this is NOT pipelined. Then the fastest clock cycle you can use is the longest propagation delay of the above (usually external data memory fetching or writing or instruction reading.) So you will need at least 5 cycle times, with each cycle time being the worst case of any one of the above. Let's call the worst case delay $$\t_\text{worst}\$$. So this means $$\5\times t_\text{worst}\$$ is your total execution time for an instruction and you'll require 5 clock cycles per instruction.

Now, suppose you can pipeline things so that all five of the above stages can execute in parallel. You still have to make the clock cycle be the worst case value, $$\t_\text{worst}\$$. But now the instructions can overlap. When one instruction is in its $$\IF\$$ phase, the prior instruction is now in its $$\DECODE\$$ phase. So the effect now is that each instruction overlaps its various steps with other instructions. The result is that the processor appears to execute 5 times faster. The price of achieving this is to make sure that up to 5 steps (if all different) can be performed in parallel. And that requires some extra logic.

Also, one can either deal with hazards or not deal with them (leaving the problem to the compiler and assembler, for example.) Dealing with hazards can be tricky and almost always lengthens the worst case magnitude of $$\t_\text{worst}\$$, too. Forcing the compiler/assembler to deal with hazards instead of added logic and stall cycles permits a smaller value for $$\t_\text{worst}\$$ and therefore a faster clock rate. Dealing with these in hardware increases $$\t_\text{worst}\$$ and makes for a worse clock rate. These are balancings a designer deals with based upon statistics about expected program code.

Pipelining does help a lot. And choices about how much is handled in hardware vs software also matters (because it changes $$\t_\text{worst}\$$.) But a simplistic view would say that for a given $$\t_\text{worst}\$$, pipelining helps by a factor of the number of parallel stages you can achieve (ignoring hazards.)

• I like your way of organizing complex details. CPU cores are easy to choke on. +1. – Sparky256 Mar 20 at 15:53
• @Sparky256 Thanks for the kind note. I spend time at MIPS getting 1:1 teaching from Dr. Hennessey, directly. We started the first morning with a huge wall mural of the Motorola 68020 processor die. He walked me through the waste of die space (about 70-80%) used for sequencing and emulation. Only 20-30% of the die actually did any work, he said. This was the inspiration for the MIPS R2000 to be able to compete against the majors of Intel and Motorola using hand-me-down FAB processing. He was able to out-perform their products using worse FABs by far. Those days stay well in my memory. – jonk Mar 20 at 15:59

Do not be confused by semantics. For k number of stages there is an initial delay of k stages while the pipeline fills up. A 'stage' is a buffer in a pipeline, like a FIFO queue. It cannot run faster than the system clock. If you have 4,6, or 8 cores, then you can get more work done for the same clock speed.

Instruction queues feed the hungry CPU pre-fetched instructions. It is to assist the fetch/decode/execute/store phases in the CPU core, which handle one instruction per 4 master clock cycles, though extended addressing modes can require an extra cycle to complete. The instruction queue is useful, by cutting access time for new instructions, but a change in threads (context) can flush this buffer, thus it has to fill up again.

A pipeline allows for parallel execution of instructions, but dependency and out-of-order issues come into play. Also the pipeline has to fill up before it becomes effective in terms of instructions-per-second boost. Very deep pipelines are shunned, as too much overhead is needed to check and correct out-of-order execution.

Finally, there is an output queue used to determine if results are both dependant and out-of-order, which is fixed here. CPU clock speed still drives this train.

Pipeline processor is k(number of stages) times faster than single cycle processor.

Bleurgh. This has been simplified to the point of unhelpfulness.

Suppose you have some digital logic. There is a propagation delay through this logic. The worst path through that logic takes some time T. Therefore you set the clock frequency to be 1/T or slower.

Suppose you then pipeline this into two stages by placing some registers in the middle. It still takes T for a result to move from input to output. But the worst path delay is now T/2. So you can clock it twice as fast, but the output arrives two cycles after the input.

This kind of thing is why people should be careful to quantify what they're measuring when they say "speedup". Sometimes it's worst path delay; sometimes it's total throughput.