Pipelining

Introduction to pipelining, Instruction level pipelining (ILP), ompiler techniques for ILP, Data hazards,
Dynamic scheduling, Dependability, Branch cost, Branch Prediction, Influence on instruction set

Concept of Pipelining | Computer Architecture Tutorial

What is Pipelining?
Pipelining is the process of accumulating instruction from the processor through a pipeline. It
allows storing and executing instructions in an orderly process. It is also known as pipeline
processing.
Before moving forward with pipelining, check these topics out to understand the concept better :
 Memory Organization
 Memory Mapping and Virtual Memory
 Parallel Processing
Pipelining is a technique where multiple instructions are overlapped during execution. Pipeline is
divided into stages and these stages are connected with one another to form a pipe like structure.
Instructions enter from one end and exit from another end.
Pipelining increases the overall instruction throughput.
In pipeline system, each segment consists of an input register followed by a combinational
circuit. The register is used to hold data and combinational circuit performs operations on it. The
output of combinational circuit is applied to the input register of the next segment.

Pipeline system is like the modern day assembly line setup in factories. For example in a car
manufacturing industry, huge assembly lines are setup and at each point, there are robotic arms
to perform a certain task, and then the car moves on ahead to the next arm.

Types of Pipeline
It is divided into 2 categories:
1. Arithmetic Pipeline
2. Instruction Pipeline

Arithmetic Pipeline
Arithmetic pipelines are usually found in most of the computers. They are used for floating point
operations, multiplication of fixed point numbers etc. For example: The input to the Floating
Point Adder pipeline is:
X = A*2^a
Y = B*2^b
Here A and B are mantissas (significant digit of floating point numbers), while a and b are
exponents.
The floating point addition and subtraction is done in 4 parts:
1. Compare the exponents.
2. Align the mantissas.
3. Add or subtract mantissas
4. Produce the result.
Registers are used for storing the intermediate results between the above operations.

Instruction Pipeline
In this a stream of instructions can be executed by overlapping fetch, decode and execute phases
of an instruction cycle. This type of technique is used to increase the throughput of the computer
system.
An instruction pipeline reads instruction from the memory while previous instructions are being
executed in other segments of the pipeline. Thus we can execute multiple instructions
simultaneously. The pipeline will be more efficient if the instruction cycle is divided into
segments of equal duration.

Pipeline Conflicts
There are some factors that cause the pipeline to deviate its normal performance. Some of these
factors are given below:

1. Timing Variations
All stages cannot take same amount of time. This problem generally occurs in instruction
processing where different instructions have different operand requirements and thus different
processing time.

2. Data Hazards
When several instructions are in partial execution, and if they reference same data then the
problem arises. We must ensure that next instruction does not attempt to access data before the
current instruction, because this will lead to incorrect results.

3. Branching
In order to fetch and execute the next instruction, we must know what that instruction is. If the
present instruction is a conditional branch, and its result will lead us to the next instruction, then
the next instruction may not be known until the current one is processed.

4. Interrupts
Interrupts set unwanted instruction into the instruction stream. Interrupts effect the execution of
instruction.

5. Data Dependency
It arises when an instruction depends upon the result of a previous instruction but this result is
not yet available.

Advantages of Pipelining
1. The cycle time of the processor is reduced.
 2. It increases the throughput of the system
3. It makes the system reliable.

Disadvantages of Pipelining
1. The design of pipelined processor is complex and costly to manufacture.
2. The instruction latency is more.

Instruction pipelining
From Simple English Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Basic five-stage pipeline in a RISC machine (IF = Instruction Fetch, ID = Instruction Decode,
EX = Execute, MEM = Memory access, WB = Register write back). The vertical axis is
successive instructions, the horizontal axis is time. So in the green column, the earliest
instruction is in WB stage, and the latest instruction is undergoing instruction fetch.

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:

1. Instruction fetch
2. Instruction decode and register fetch
3. Execute
4. Memory access
5. Register write back

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 and Disadvantages of Pipelining

Advantages of Pipelining:

1. The cycle time of the processor is reduced; increasing the instruction throughput.
Pipelining doesn't reduce the time it takes to complete an instruction; instead it increases
the number of instructions that can be processed simultaneously ("at once") and reduces
the delay between completed instructions (called 'throughput').
The more pipeline stages a processor has, the more instructions it can process "at once"
and the less of a delay there is between completed instructions. Every predominant
general purpose microprocessor manufactured today uses at least 2 stages of pipeline up
to 30 or 40 stages.
2. If pipelining is used, the CPU Arithmetic logic unit can be designed faster, but will be
more complex.
3. Pipelining in theory increases performance over an un-pipelined core by a factor of the
number of stages (assuming the clock frequency also increases by the same factor) and
the code is ideal for pipeline execution.
4. Pipelined CPUs generally work at a higher clock frequency than the RAM clock
frequency, (as of 2008 technologies, RAMs work at a low frequencies compared to CPUs
frequencies) increasing computers overall performance.

Disadvantages of Pipelining:
 Pipelining has many disadvantages though there are a lot of techniques used by CPUs and
compilers designers to overcome most of them; the following is a list of common
drawbacks:

1. The design of a non-pipelined processor is simpler and cheaper to manufacture, non-

pipelined processor executes only a single instruction at a time. This prevents branch
delays (in Pipelining, every branch is delayed) as well as problems when serial
instructions being executed concurrently.
2. In pipelined processor, insertion of flip flops between modules increases the instruction
latency compared to a non-pipelining processor.
3. A non-pipelined processor will have a defined instruction throughput. The performance
of a pipelined processor is much harder to predict and may vary widely for different
programs.
4. Many designs include pipelines as long as 7, 10, 20, 31 and even more stages; a
disadvantage of a long pipeline is when a program branches, the entire pipeline must be
flushed (cleared). The higher throughput of pipelines falls short when the executed code
contains many branches: the processor cannot know in advance where to read the next
instruction, and must wait for the branch instruction to finish, leaving the pipeline behind
it empty. This disadvantage can be reduced by predicting whether the a conditional
branch instruction will branch based on previous activity. 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 resumes "working" again. In such extreme cases, the
performance of a pipelined processor could be worse than non-pipelined processor.
5. Unfortunately, not all instructions are independent. In a simple pipeline, completing an
instruction may require 5 stages. To operate at full performance, this pipeline will need to
run 4 subsequent independent instructions while the first is completing. Any of those 4
instructions might depend on the output of the first instruction, causing the pipeline
control logic to wait and insert a stall or wasted clock cycle into the pipeline until the
dependency is resolved. Fortunately, techniques such as forwarding can significantly
reduce the cases where stalling is required.
6. Self-modifying programs may fail to execute properly on a pipelined architecture when
the instructions being modified are near the instructions being executed. This can be
caused by the instructions may already being in the Prefetch Input Queue, so the
modification may not take effect for the upcoming execution of instructions. Instruction
caches m

6. ake the problem even worse.

7. Hazards: When a programmer (or compiler) writes assembly code, they generally
assume that each instruction is executed before the next instruction is being executed.
When this assumption is not validated by pipelining it causes a program to behave
incorrectly, the situation is known as a hazard.
Various techniques for resolving hazards or working around such as forwarding and
delaying (by inserting a stall or a wasted clock cycle) exist.