Instruction pipeline

Template:Mergewith

An instruction pipeline is a technology used on microprocessors to enhance their performance. Pipelining greatly improves throughput.

Instructions consist of a number of steps. Practically every CPU ever manufactured is driven by a central clock. Each step requires at least one clock cycle. Each step of an instruction is performed by a different piece of hardware on the CPU. Early, non-pipelined, processors did only one step at a time. For example, they might perform these steps sequentially in order:

1. Read the next instruction
2. Read the operands, if any
3. Execute the instruction
4. Write the results back out

This approach, while simple, is wasteful. While the processor is adding numbers, for instance, the hardware dedicated to loading data from computer memory is idle, waiting for the addition to complete.

Pipelining improves performance by reducing the idle time of each piece of hardware. Pipelined CPUs include circuitry that examines the instructions and breaks them down into their sub-instructions. Some sub-instructions of different instructions can be executed simultaneously by different pieces of hardware, exploiting more parallelism in the hardware. A control unit called the pipeline controller ensures that this is done in a safe way that does not change the end result.

For instance, a typical instruction to add two numbers might be ADD A, B, C, which adds the values found in memory locations A and B, and then puts the result in memory location C. In a pipelined processor the pipeline controller would break this into a series of instructions similar to:

LOAD A, R1
LOAD B, R2
ADD R1, R2, R3
STORE R3, C
LOAD next instruction

The R locations are registers, temporary memory inside the CPU that is quick to access. The end result is the same, the numbers are added and the result placed in C, and the time taken to drive the addition to completion is no different from in the non-pipelined case.

The key to understanding the advantage of pipelining is to consider what happens when this ADD instruction is "half-way done", at the ADD instruction for instance. At this point the circuitry responsible for loading data from memory is no longer being used, and would normally sit idle. In this case the pipeline controller fetches the next instruction from memory, and starts loading the data it needs into registers. That way when the ADD instruction is complete, the data needed for the next ADD is already loaded and ready to go. The overall effective speed of the machine can be greatly increased because no parts of the CPU sit idle.

Each of the simple steps are usually called pipeline stages, in the example above the pipeline is three stages long, a loader, adder and storer.

Every microprocessor manufactured today uses at least 2 stages of pipeline. (The Atmel AVR and the PIC microcontroller each have a 2 stage pipeline).

Many designs include pipelines as long as 7, 10 and even 20 stages (like in the Intel Pentium 4). The Xelerator X10q has a pipeline more than a thousand stages long[1] (http://www.mdronline.com/watch/watch_Issue.asp?Volname=Issue+%23171&on=1#item13).

To better visualize the concept, we can look at a theoretical 3-stages pipeline:

Stage	Description
Load	Read instruction from memory
Execute	Execute instruction
Store	Store result in memory and/or registers

and a pseudo-code assembly listing to be executed:

	LOAD  #40,A      ; load 40 in A
	MOVE  A,B        ; copy A in B
	ADD   #20,B      ; add 20 to B
	STORE B, 0x300   ; store B into memory cell 0x300

This is how it would be executed:

Clock 1

Load	Execute	Store
LOAD

The LOAD instruction is fetched from memory.

Clock 2

Load	Execute	Store
MOVE	LOAD

The LOAD instruction is executed, while the MOVE instruction is fetched from memory.

Clock 3

Load	Execute	Store
ADD	MOVE	LOAD

The LOAD instruction is in the Store stage, where its result (the number 40) will be stored in the register A. In the meantime, the MOVE instruction is being executed. Since it must move the contents of A into B, it must wait for the ending of the LOAD instruction.

Clock 4

Load	Execute	Store
STORE	ADD	MOVE

The STORE instruction is loaded, while the MOVE instruction is finishing off and the ADD is calculating.

And so on. Note that, sometimes, an instruction will depend on the result of another one (like our MOVE example). When more than one instruction references a particular location for an operand, either reading it (as an input) or writing it (as an output), executing those instructions in an order different from the original program order can lead to problems, also known as hazards. There are several established techniques for either preventing hazards from occurring, or working around them if they do.

The higher throughput of pipelines falls short when the executed code contains many branches: the processor cannot know where to read the next instruction, and must wait for the branch instruction to finish, leaving the pipeline behind it empty. After the branch is resolved, the next instruction has to travel all the way through the pipeline before its result becomes available and the processor appears to "work" again. Popular ways of mitigating this problem include branch prediction and branch predication.

Because of the instruction pipeline, code that the processor loads will not immediately execute. Due to this, updates in the code very near the current location of execution may not take effect because they are already loaded into the Prefetch Input Queue. Instruction caches make this phenomenon even worse. This is only relevant to self-modifying programs such as operating systems.

See also: Wait state, classic RISC pipelineuk:Конвеєр команд it:Pipeline dati