FACTOID # 11: Oklahoma has the highest rate of women in State or Federal correctional facilities.
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
People who viewed "Pipelining" also viewed:


FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:



(* = Graphable)



Encyclopedia > Pipelining

An instruction pipeline is a technology used on modern 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 new 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).

Pipelines as long as 7, 10 and even 20 stages (like in the Intel Pentium 4) are common in modern designs. 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).

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

The LOAD instruction is fetched from memory.

Clock 2
Load Execute Store

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

Clock 3
Load Execute Store

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

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). In this case, a pipeline stall will happen, where a pipeline will stop, waiting for the offending instruction to finish before resuming work. The throughput of the processor is not changed: one instruction is executed every clock cycle. But actually every instruction has been worked on for many cycles before.

Here is an entertaining animation illustrating the pipelining concept.

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 pipeline

  Results from FactBites:
Pipeline - Wikipedia, the free encyclopedia (190 words)
Pipeline (computer), as used in computer science, electrical engineering, and general manufacturing, is a metaphor for a chain of transformative stages where the output of one stage is input for the next one.
The Banzai Pipeline is a surfing spot of Oahu's North Shore.
The Pipeline Plots are alleged political plots related to the oil economy.
  More results at FactBites »



Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m