CONDITIONAL

BRANCHES IN PIPELINED
COMPUTERS
Presented by:-
Dilip Mathuria

M.Tech (VLSI)
 OVERVIEW
In this presentation we are going to discuss about the :-

1. Pipelining used in computers.

How instruction pipelining works?
Various stages of instruction pipelining.

2. What is conditional branches in pipelined computers?

Types of conditional instructions
Effects of conditional branch on instruction pipelining.
How to deal with the effects?

3. What is internal forwarding of instructions?

 WHAT IS PIPELINING?
The greater performance of the CPU is achieved by
instruction pipelining.
8086 microprocessor has two blocks

BIU(BUS INTERFACE UNIT)

EU(EXECUTION UNIT)

The BIU performs all bus operations such as instruction

fetching, reading and writing operands for memory and
calculating the addresses of the memory operands. The
instruction bytes are transferred to the instruction
queue.
EU executes instructions from the instruction system
byte queue.
 INSTRUCTION PIPELINING

First stage fetches the instruction and buffers

it.
When the second stage is free, the first stage
passes it the buffered instruction.
While the second stage is executing the
instruction, the first stage takes advantages of
any unused memory cycles to fetch and buffer
the next instruction.
This is called instruction pre fetch or fetch
overlap.
 SIX STAGE OF INSTRUCTION
PIPELINING
Fetch Instruction(FI)
Read the next expected instruction into a buffer
Decode Instruction(DI)
Determine the op code and the operand specifies.
Calculate Operands(CO)
Calculate the effective address of each source operand.
Fetch Operands(FO)
Fetch each operand from memory. Operands in registers need not be
fetched.
Execute Instruction(EI)
Perform the indicated operation and store the result
Write Operand(WO)
Store the result in memory.
Timing diagram for instruction pipeline
operation
 CONDITIONAL BRANCH

A branch is an instruction in a computer

program that can cause a computer to begin
executing a different instruction sequence and thus
deviate from its default behavior of executing
instructions in order.

Branch (or branching, branched) may also refer to

the act of switching execution to a different
instruction sequence as a result of executing a branch
instruction.
 CONDITIONAL BRANCH
A branch instruction can be either an unconditional
branch, which always results in branching,

or a conditional branch, which may or may not cause

branching, depending on some condition.

Branch instructions are used to implement control

flow in program loops and conditionals (i.e., executing a
particular sequence of instructions only if certain
conditions are satisfied).
 CONDITIONAL BRANCH
INSTRUCTION
Condition Codes
BRP X
Branch to location X if result is positive
BRZ X
Branch to location X if result is zero
BRE R1,R2,X
Branch to location X if contents of R1 = R2
Branch Condition Test Meaning Uses

Always take the

B No test Unconditional
branch
Always take the
BAL No test Always
branch
Comparison equal or
BEQ Z=1 Equal
zero result

Comparison not equal

BNE Z=0 Not equal
or non-zero result

Arithmetic operation
BCS C=1 Carry set
gave carry out
Arithmetic operation
BCC C=1 Carry clear did not produce a
carry

Unsigned comparison
BHS C=1 Higher or same gave higher or same
result
 Unsigned
BLO C=0 Lower comparison gave
lower result
Result is minus or
BMI N=1 Minus
negative
Result is positive
BPL N=0 Plus
(plus) or zero
Signed integer
BVS V=1 Overflow Set operation: overflow
occurred
Signed integer
BVC V=0 Overflow Clear operation: no
overflow occurred
((NOT C) OR Z) =0 Unsigned comparison
BHI Higher
{C set and Z clear} gave higher
((NOT C) OR Z) =1 Unsigned comparison
BLS Lower or same
{C set or Z clear} gave lower or same
(N EOR V) =0 Signed integer
BGE {(N and V) set or (N Greater or Equal comparison gave
and V) clear} greater than or equal
(N EOR V) =1
Signed integer
{(N set and V clear)
Effect of conditional branch on
instruction pipeline operation
 Conditional branch instructions
Assume that the instruction 3 is a conditional branch to
instruction 15.
Until the instruction is executed there is no way of
knowing which instruction will come next
The pipeline will simply loads the next instruction in the
sequence and execute.
Branch is not determined until the end of time unit 7.
During time unit 8,instruction 15 enters into the
pipeline.
No instruction complete during time units 9 through 12.
This is the performance penalty incurred because we
could not anticipate the branch.
 Dealing with Branches
A major problem in designing an instruction pipeline is
assuring a steady flow of instructions to the initial stages of
the pipeline.

Since conditional branches alter the steady flow of

instructions, we must come up with ways to execute them
efficiently.
 Dealing with branches

A variety of approaches have been taken for dealing with

conditional branches.

Multiple streams
Pre fetch branch target.
Loop buffer
Branch prediction
Delayed branch
 Multiple streams
In simple pipeline, it must choose one of the two
instructions to fetch next and may make wrong choice.
In multiple streams allow the pipeline to fetch both
instructions making use of two streams.
Problems with this approach
With multiple pipelines there are contention delays for the
access to the registers and to memory.
Additional branch instructions may enter the pipeline(either
stream)before the original branch decision is resolved. Each
such instructions needs an additional branch.
Examples:
IBM 370/168 AND IBM 3033.
 Prefetch Branch Target
When a conditional branched is recognized, the target of the
branch is prefetched, in addition to the instruction following
the branch.

This target is then saved until the branch instruction is

executed.

If the branch is taken, the target has already been prefetched.

The IBM 360/91 uses this approach.

 Loop buffer
A loop buffer is a small, very high-speed memory
maintained in instruction fetch stage.

It contains n most recently fetched instructions in sequence.

If a branch is to be taken, the hardware first checks whether

the branch target is within the buffer.

If so, the next instruction is fetched from the buffer.

 Benefits of loop buffer
Instructions fetched in sequence will be available without
the usual memory access time
If the branch occurs to the target just a few locations ahead
of the address of the branch instruction, the target will
already be in the buffer. This is useful for the rather
common occurrence of IF-THEN and IF-THEN-ELSE
sequences.
This is well suited for loops or iterations, hence named loop
buffer.If the loop buffer is large enough to contain all the
instructions in a loop,then those instructions need to be
fetched from memory only once,for the first iteration.
For subsequent iterations,all the needed instructions are
already in the buffer.
 Cont..,
Loop buffer is similar to cache.
Least significant 8 bits are used to index the buffer and
remaining MSB are checked to determine the branch
target.

Branch address

8 Instruction to be
Loop buffer decoded in case of
hit (256 bytes)

Most significant address bits

compared to determine a hit
 Branch prediction
Various techniques used to predict whether a branch will be
taken. They are

Predict Never Taken

Predict Always Taken STATIC
Predict by Opcode
Taken/Not Taken Switch
Branch History Table DYNAMIC
 Static branch strategies
STATIC(1,2,3)-They do not depend on the execution
history
Predict Never Taken
Always assume that the branch will not be taken and
continue to fetch instruction in sequence.
Predict Always Taken
Always assume that the branch will be taken and
always fetch from target.
Predict by Opcode
Decision based on the opcode of the branch
instruction. The processor assumes that the branch will be
taken for certain branch opcodes and not for others.
 Dynamic branch strategies
DYNAMIC(4,5)-They depend on the execution history.
They attempt to improve the accuracy of prediction by recording
the history of conditional branch instructions in a program.
For example, one or more bits can be associated with conditional
branch instruction that reflect the recent history.
These bits are referred as taken/not taken switch.
These history bits are stored in temporary high-speed memory.
Then associate the bits with any conditional branch instruction and
make decision.
Another possibility is to maintain a small table for recent history
with one or more bits in each entry.
 Cont..,
With only one bit of history, an error prediction will occur twice
for each use of the loop: once on entering the loop and once on
exiting.
The decision process can be represented by a finite-state
machine with four stages.
 Cont..,
If the last two branches of the given instruction have taken
same path, the prediction is to make the same path again.
If the prediction is wrong it remains same for next time
also
But when again the prediction went wrong, the opposite
path will be selected.
Greater efficiency could be achieved if the instruction
fetch could be initiated as soon as the branch decision is
made.
For this purpose, information must be saved, that is known
as branch target buffer, or a branch history table.
Dealing with Branches
 Intel Pentium Branch

The prediction of whether a jump will

occur or not, is based on the branchs
previous behavior. There are four possible
states that depict a branchs disposition to
jump:

Stage 0: Very unlikely a jump will occur

Stage 1: Unlikely a jump will occur
Stage 2: Likely a jump will occur
Stage 3: Very likely a jump will occur
Intel Pentium Branch
It is actually believed
that Pentiums original
algorithm for branch
prediction was
incorrect. (Left)
Internal Forwarding of Instructions
Forward result from ALU/Execute unit to execute unit in
next stage
Also can be used in cases of memory access
in some cases, operand fetched from memory has been
computed previously by the program
can we forward this result to a later stage thus
avoiding an extra read from memory ?
Who does this ?
Internal forwarding cases
Stage i to Stage i+k in pipeline
store-load forwarding
load-store forwarding
store-store forwarding
 Internal Forwarding
Internal Forwarding: It is replacing unnecessary memory
accesses by register-to-register transfers.

Memory access is slower than register-to-register

operations.

Performance can be enhanced by eliminating unnecessary

memory accesses
 Internal Forwarding
This concept can be explored in 3 directions:

1. Store Load Forwarding

2. Load Load Forwarding

3. Store Store Forwarding

Store Load Forwarding
Load Load Forwarding
Store Store Forwarding
Thank You