method of improving instruction-level parallelism From Wikipedia, the free encyclopedia
Instruction pipelining is a technique used in the design of modern microprocessors, microcontrollers and CPUs to increase their instruction throughput (the number of instructions that can be executed in a unit of time).
The main idea is to divide (termed "split") the processing of a CPU instruction, as defined by the instruction microcode, into a series of independent steps of micro-operations (also called "microinstructions", "micro-op" or "µop"), with storage at the end of each step. This allows the CPUs control logic to handle instructions at the processing rate of the slowest step, which is much faster than the time needed to process the instruction as a single step.
The term pipeline refers to the fact that each step is carrying a single microinstruction (like a drop of water), and each step is linked to another step (analogy; similar to water pipes).
Most modern CPUs are driven by a clock. The CPU consists internally of logic and memory (flip flops). When the clock signal arrives, the flip flops store their new value then the logic requires a period of time to decode the flip flops new values. Then the next clock pulse arrives and the flip flops store another values, and so on. By breaking the logic into smaller pieces and inserting flip flops between pieces of logic, the time required by the logic (to decode values till generating valid outputs depending on these values) is reduced. In this way the clock period can be reduced.
For example, the RISC pipeline is broken into five stages with a set of flip flops between each stage as follows:
Processors with pipelining consist internally of stages (modules) which can semi-independently work on separate microinstructions. Each stage is linked by flip flops to the next stage (like a "chain") so that the stage's output is an input to another stage until the job of processing instructions is done. Such organization of processor internal modules reduces the instruction's overall processing time.
A non-pipeline architecture is not as efficient because some CPU modules are idle while another module is active during the instruction cycle. Pipelining does not completely remove idle time in a pipelined CPU, but making CPU modules work in parallel increases instruction throughput.
An instruction pipeline is said to be fully pipelined if it can accept a new instruction every clock cycle. A pipeline that is not fully pipelined has wait cycles that delay the progress of the pipeline.
Advantages of Pipelining:
Disadvantages of Pipelining:
To the right is a generic pipeline with four stages:
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 awaiting to be executed |
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 | All instructions are executed |
When a "hiccup" (interruption) in execution occurs, a "bubble" is created in the pipeline in which nothing useful happens. In cycle 2, the fetching of the purple instruction is delayed and the decoding stage in cycle 3 now contains a bubble. Everything behind the purple instruction is delayed as well but everything in front of the purple instruction continues with execution.
Clearly, when compared to the execution above, the bubble yields a total execution time of 8 clock ticks instead of 7.
Bubbles are like stalls (delays), in which nothing useful will happen for the fetch, decode, execute and writeback. It is like a NOP (short for No OPeration) code.
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 tasks similar to:
LOAD A, R1 LOAD B, R2 ADD R1, R2, R3 STORE R3, C LOAD next instruction
The locations 'R1' and 'R2' are registers in the CPU. The values stored in memory locations labeled 'A' and 'B' are loaded (copied) into these registers, then added, and the result is stored in a memory location labeled 'C'.
In this example the pipeline is three stages long- load, execute, and store. Each of the steps are called pipeline stages.
On a non-pipelined processor, only one stage can be working at a time so the entire instruction has to complete before the next instruction can begin. On a pipelined processor, all of the stages can be working at once on different instructions. So when this instruction is at the execute stage, a second instruction will be at the decode stage and a 3rd instruction will be at the fetch stage.
To better understand the concept, we can look at a theoretical 3-stage 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:
Load | Execute | Store |
---|---|---|
LOAD |
The LOAD instruction is fetched from memory.
Load | Execute | Store |
---|---|---|
MOVE | LOAD |
The LOAD instruction is executed, while the MOVE instruction is fetched from memory.
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.
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 the hazards situation (mentioned above).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.