Instruction pipelining

Pipelining redirects here. For HTTP pipelining, see HTTP pipelining.

Basic five-stage pipeline in a RISC machine (IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back). In the fourth clock cycle (the green column), the earliest instruction is in MEM stage, and the latest instruction has not yet entered the pipeline.

An instruction pipeline is a technique used in the design of computers to increase their instruction throughput (the number of instructions that can be executed in a unit of time). Pipelining does not reduce the time to complete an instruction, but increases the number of instructions that can be processed at once.

Each instruction is split into a sequence of dependent steps. The first step is always to fetch the instruction from memory; the final step is usually writing the results of the instruction to processor registers or to memory. Pipelining seeks to let the processor work on as many instructions as there are dependent steps, just as an assembly line builds many vehicles at once, rather than waiting until one vehicle has passed through the line before admitting the next one. As the goal of the assembly line is to keep each assembler productive at all times, pipelining seeks to use every portion of the processor busy with some instruction. Pipelining lets the computer's cycle time be the time of the slowest step, and ideally lets one instruction complete in every cycle.

The term pipeline is an analogy that stems from the fact that each part of the processor is doing work, as there is fluid in each link of a pipeline.

Introduction

Central processing units (CPUs) are driven by a clock. Each clock pulse need not do the same thing; rather, logic in the CPU directs successive pulses to different places to perform a useful sequence. There are many reasons that the entire execution of a machine instruction cannot happen at once. For example, if one clock pulse latches a value into a register or begins a calculation, it will take some time for the value to be stable at the outputs of the register or for the calculation to complete. As another example, reading an instruction out of a memory unit cannot be done at the same time that an instruction writes a result to the same memory unit. In pipelining, effects that cannot happen at the same time are made the dependent steps of the instruction.

Number of steps

The number of dependent steps varies with the machine architecture. For example:

• The IBM Stretch project proposed the terms Fetch, Decode, and Execute that have become common.
• The classic RISC pipeline comprises:
  1. Instruction fetch
  2. Instruction decode and register fetch
  3. Execute
  4. Memory access
  5. Register write back
• 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 (as in the Intel Pentium 4).
• The later "Prescott" and "Cedar Mill" Pentium 4 cores (and their Pentium D derivatives) had a 31-stage pipeline, the longest in mainstream consumer computing.
• The Xelerated X10q Network Processor has a pipeline more than a thousand stages long.

As the pipeline is made "deeper" (with a greater number of dependent steps), a given step can be implemented with simpler circuitry, which may let the processor clock run faster.

A processor is said to be fully pipelined if it can fetch an instruction on every cycle. To the extent that some instructions or some conditions require delays that inhibit fetching new instructions, the processor is not fully pipelined.

Hazards

A human programmer writing an assembly language program on the sequential-execution model assumes that each instruction completes before the next one begins. This assumption is not true on a pipelined processor. A situation where the expected result is problematic is a hazard. Imagine the following two register instructions to a hypothetical RISC processor that has the 5 steps listed above:

 1: Add 1 to R5.
 2: Copy R5 to R6.

Instruction 1 would be fetched at time t₁ and its execution would be complete at t₅. Instruction 2 would be fetched at t₂ and would be complete at t₆. The first instruction might deposit the incremented number into R5 as its fifth step (register write back) at t₅. But the second instruction might get the number from R5 (to copy to R6) in its second step (instruction decode and register fetch) at time t₃. It seems that the first instruction would not have incremented the value by then. The above code invokes a hazard.

A human programmer writing in a compiled language might not have these concerns, as the compiler could be designed to generate machine code that avoids hazards.

Work-arounds

The processor design might deal with the hazard by advising programmers to avoid such dependencies in adjacent and nearly adjacent instructions, declaring that the second instruction uses an old value rather than the desired value (in the example above, the processor might counter-intuitively copy the unincremented value), or that the value it uses is undefined. The programmer may have unrelated work that the processor can do in the meantime; or, to ensure correct results, the programmer may insert NOPs into the code, partly negating the advantages of pipelining.

Solutions

Processors that can compute the presence of a hazard can give the programmer the expected result by stalling — delaying processing of the second instruction (and subsequent instructions) until the values it requires as input are ready. This creates a bubble in the pipeline (see below), also partly negating the advantages of pipelining.

Some processors can not only compute the presence of a hazard but can compensate by having additional data paths that provide needed inputs to a computation step before a subsequent instruction would otherwise compute them, an attribute called forwarding.

Some processors can determine that instructions other than the next sequential one are not dependent on the current ones and can be executed without hazards. Such processors may perform out-of-order execution.

Branches

A branch out of the normal instruction sequence often involves a hazard. Unless the processor can give effect to the branch in a single time cycle, the pipeline will continue fetching instructions sequentially. Such instructions cannot be allowed to take effect because the programmer has diverted control to another part of the program.

A conditional branch is even more problematic. The processor may or may not branch, depending on a calculation that has not yet occurred. Various processors may stall, may attempt branch prediction, and may be able to begin to execute two different program sequences (speculative execution), both assuming the branch is and is not taken, discarding all work that pertains to the incorrect guess.

A processor with an implementation of branch prediction that usually makes correct predictions can minimize the performance penalty from branching. However, if branches are predicted poorly, it may create more work for the processor, such as flushing from the pipeline the incorrect code path that has begun execution before resuming execution at the correct location.

Programs written for a pipelined processor deliberately avoid branching to minimize possible loss of speed. For example, the programmer can handle the usual case with sequential execution and branch only on detecting unusual cases. Using programs such as gcov to analyze code coverage lets the programmer measure how often particular branches are actually executed and gain insight with which to optimize the code.

Special situations

Self-modifying programs

The technique of self-modifying code can be problematic on a pipelined processor. In this technique, one of the effects of a program is to modify its own upcoming instructions. If the processor has an instruction cache, the original instruction may already have been copied into a prefetch input queue and the modification will not take effect.

Independent pipelines

Mathematical pipelines, such as the arithmetic processors in the Intel Pentium products, process large arrays or vectors by repeating a process such as multiplication thousands of times. Video processors likewise perform many computations in parallel with the execution of processor instructions. These situations do not inherently pose hazards to the execution of instructions. However, they are similar in that, after starting an operation, the programmer must consider or test whether the operation is complete before starting another operation that depends on the results of the first one, or the processor must be designed to detect and stall the dependent operation until its inputs are ready.

Advantages and disadvantages

Advantages of pipelining

The main advantage of pipelining is that it keeps all portions of the processor occupied and increases the amount of useful work the processor can do in a given time.

• Reducing the processor's cycle time usually increases the throughput of instructions.
• By making each dependent step simpler, pipelining can enable complex operations more economically than adding complex circuitry, such as for numerical calculations.

The advantages of a pipelined processor are diminished to the extent that execution encounters hazards that require execution to slow below its ideal rate.

Advantages of the non-pipelined processor

A non-pipelined processor executes only a single instruction at a time. Declining to pursue increased speed with pipelining may make the resulting design simpler and cheaper to manufacture.

• A non-pipelined processor never encounters a hazard. For example, there are never branch delays. (In effect, every branch is delayed.) The consequences of this are as follows:
  • Programming, and training programmers, may be easier.
  • It is easier to predict the exact timing of a given sequence of instructions.
• A pipelined processor's need to organize all its work into modular steps may require the duplication of registers that increases the latency of some instructions.

Illustrated example

Generic 4-stage pipeline; the colored boxes represent instructions independent of each other

To the right is a generic pipeline with four stages:

1. Fetch
2. Decode
3. Execute
4. Write-back

The top gray box is the list of instructions waiting to be executed; the bottom gray box is the list of instructions that have been completed; and the middle white box is the pipeline.

Execution is as follows:

Time	Execution
0	Four instructions are waiting to be executed
1	the green instruction is fetched from memory
2	the green instruction is decoded the purple instruction is fetched from memory
3	the green instruction is executed (actual operation is performed) the purple instruction is decoded the blue instruction is fetched
4	the green instruction's results are written back to the register file or memory the purple instruction is executed the blue instruction is decoded the red instruction is fetched
5	the green instruction is completed the purple instruction is written back the blue instruction is executed the red instruction is decoded
6	The purple instruction is completed the blue instruction is written back the red instruction is executed
7	the blue instruction is completed the red instruction is written back
8	the red instruction is completed
9	All four instructions are executed

A bubble in the pipeline

A bubble in cycle 3 delays execution.

Main article: Bubble (computing)

A pipelined processor may deal with hazards by stalling and creating a bubble in the pipeline, resulting in one or more cycles in which nothing useful happens.

In the illustration at right, in cycle 3, the processor cannot decode the purple instruction, perhaps because the processor determines that decoding depends on results produced by the execution of the green instruction. The green instruction can proceed to the Execute stage and then to the Write-back stage as scheduled, but the purple instruction is stalled for one cycle at the Fetch stage. The blue instruction, which was due to be fetched during cycle 3, is stalled for one cycle, as is the red instruction after it.

Because of the bubble (the blue ovals in the illustration), the processor's Decode circuitry is idle during cycle 3. Its Execute circuitry is idle during cycle 4 and its Write-back circuitry is idle during cycle 5.

When the bubble moves out of the pipeline (at cycle 6), normal execution resumes. But everything now is one cycle late. It will take 8 cycles (cycle 1 through 8) rather than 7 to completely execute the four instructions shown in colors.

History

Seminal uses of pipelining were in the ILLIAC II project and the IBM Stretch project, though a simple version was used earlier in the Z1 in 1939 and the Z3 in 1941.

Pipelining began in earnest in the late 1970s in supercomputers such as vector processors and array processors. One of the early supercomputers was the Cyber series built by Control Data Corporation. Its main architect, Seymour Cray, later headed Cray Research. Cray developed the XMP line of supercomputers, using pipelining for both multiply and add/subtract functions. Later, Star Technologies added parallelism (several pipelined functions working in parallel), developed by Roger Chen. In 1984, Star Technologies added the pipelined divide circuit developed by James Bradley. By the mid 1980s, supercomputing was used by many different companies around the world.

Today, pipelining and most of the above innovations are embedded inside most microprocessors.

See also

• Wait state
• Classic RISC pipeline
• Pipeline (computing)
• Parallel computing
• Instruction unit

External links

• Branch Prediction in the Pentium Family (Archive.org copy)
• ArsTechnica article on pipelining
• Counterflow Pipeline Processor Architecture