FATIMA JINNAH WOMEN UNIVERSITY
Department Of Software Engineering
SEMESTER PROJECT
BRANCH PREDICTION IN PIPELINING
Submitted To: Ma’am Irum Matloob
Submitted By: Aimma Butt (2020-BSE-038)
Amna Zaheer (2020-BSE-041)
Mahnoor Mustafa (2020-BSE-051)
Saba Tariq (2020-BSE-061)
Course: Computer Architecture and Logic Design
Semester: III-B
Table of Contents
INTRODUCTION:..........................................................................................................................2
Pipeline:...........................................................................................................................................2
Stages of Pipelining:........................................................................................................................2
Instruction fetch:..........................................................................................................................2
Instruction decode:.......................................................................................................................3
Instruction execute:......................................................................................................................3
Memory Access:..........................................................................................................................3
Write back:...................................................................................................................................3
Hazards of Pipelining:.....................................................................................................................3
1. Structural Hazard:.................................................................................................................3
2. Data Hazard:.........................................................................................................................3
3. Control Hazard:....................................................................................................................4
Prevention of Pipeline Hazards.......................................................................................................4
Branch Prediction:...........................................................................................................................4
Comparison of Branch Prediction Techniques:...............................................................................4
1. Static Branch Prediction:......................................................................................................4
2. Dynamic Branch Prediction:.................................................................................................5
CONCLUSION:..............................................................................................................................6
REFERENCES:...............................................................................................................................6
1|Page
BRANCH PREDICTION IN PIPELINING
INTRODUCTION:
In process of execution, a one cycle may have to wait for complete process to execute again.
For example: if there are three stages; inserting the bottle (A), filling the bottle (B), and sealing
the bottle (B). In simple process, when bottle pass through stage A and go to stage B, stage A
will remain idle until all three stages complete, this decreases the efficiency of process. In order
to increase the utilization of processor or CPU, we have two options;
1. Apply hardware with faster circuit.
2. Arrange hardware components in such a way that more than one operation can be
performed simultaneously.
First technique with faster circuits is costly, so second technique is the most adopted technique
which is known as pipelining.
Pipeline:
Pipeline is a technique where several instructions are overlapped during execution. It is a process
where hardware components of CPU are arranged in such a way that increase overall throughput
of instruction. It increases performance of process and increase utilization.
In pipeline, each system consists of input register and combinational circuit. The register holds
the data and circuit perform operation and output of circuit is the input of other register.
Stages of Pipelining:
Pipeline consist of 5 stages;
Instruction fetch:
CPU read instruction from address in the memory whose value present in program counter.
2|Page
Instruction decode:
Instruction is decoded and registered file is used to get values from register.
Instruction execute:
Operation is performed.
Memory Access:
Memory operands are written or read from/to the memory.
Write back:
Fetched value is written back to register.
Sometimes, problem with pipeline arise which effect normal performance of pipelining. These
problems are called as hazards of pipelining.
Hazards of Pipelining:
There are three hazards which are as follows;
1. Structural Hazard:
When a planned instruction cannot execute in a proper clock cycle because hardware
does not support the combination of instructions that are set to execute.
2. Data Hazard:
When a planned instruction cannot execute in a proper clock cycle because data that is
needed to execute instruction is not yet analyzed. Most of the time it occurs when the
pipeline must be stalled as one step must wait for another to complete.
The solution for this type of hazard is forwarding and bypassing. It can be done by
adding extra hardware to retrieve the missing data early from internal resources.
3|Page
3. Control Hazard:
Control hazard is also called as branch hazard. When a planned instruction cannot
execute in a proper clock cycle because the instruction that was fetched is not is needed
yet.
The solution for this type of hazard is branch prediction that whether a branch is taken or
not taken.
Prevention of Pipeline Hazards
To keep away from manipulate hazards, microarchitectures can:
1. Insert a pipeline bubble, assured to increase latency, or.
2. Use branch prediction and basically make knowledgeable guesses approximately which case a
pipeline bubble may be wanted withinside the case of a wrong prediction.
When a branch is taken, the program counter PC of CPU is ready to the argument of the jump
instruction. So, the following instruction turns into the instruction at that address in memory.
Therefore, a glide of manipulate changes. When a branch isn't always taken, the CPU’s software
counter is unchanged.
Branch Prediction:
Branch prediction is a technique that speeds up the processing of branch instructions with CPU
using pipelining. This involves the executing particular instructions if particular predicts are true.
Thus this is implemented in hardware using branch predictor.
This technique is used to speed up execution of instructions on processer.
Comparison of Branch Prediction Techniques:
The schemes of branch prediction is of two types that are static and dynamic branch prediction
schemes.
1. Static Branch Prediction:
Static prediction strategies is a software technique that is very simple and easy. This scheme does
not require any hardware as this is a software technique. It accumulates the majority of data and
information preceding to the execution of program or during compile time. Moreover, static
4|Page
prediction techniques are easy to evaluate with low cost and less energy to execute instructions
as it does not require any hardware component and table of instructions. In these systems,
compilers provide good handling for such branches.
There are four main schemes of branch prediction;
1. Single direction prediction:
This is the easiest strategy in which all the directions will go dependably in same way
regardless of whether branch prediction took place or not. The results are better in branch
prediction as compare to the situation when branch prediction is not taken.
2. Backward taken forward not taken (BTFT):
In this scheme, most of the loops are backward jump loops and which will be taken more
often than forwarding loops. Thus it will upgrade the execution of prediction.
3. Program based prediction:
Structural based information of the program is used in this scheme of branch prediction.
They are basically based on operands, opcode and information of executed branches.
4. Profile based prediction:
In this scheme, branch prediction contains information from previous execution of
program with multiple inputs.
2. Dynamic Branch Prediction:
It is a hardware technique. This scheme accumulates the data and information during compile
time of program. They keep the track during run time of program execution so they are more
assorted. Due to this reason of data accumulation during run time, most of the modern
processors relies upon dynamic branch prediction. This requires hardware to save some
previous data and then uses that data for prediction of branches.
This kind of branch scheme has two interacting method;
1. Branch outcome prediction: It refers to foreknow that the branch direction whether it is
taken or not.
2. Target prediction: This prediction predicts the target when any branch prediction is
taken.
There are six main schemes of branch predictor are;
1. Basic Predictor:
The basic branch predictor include Smith algorithm and two level algorithm that are used
in dynamic branch prediction.
Smith algorithm: This is the most simple and primitive algorithm according to which a
single level predictor consists of a branch history table that keeps a record of each of the
branch in both cases (if a branch is taken or not taken). It consist of a table of 2 m counters,
where every counter tracks the past directions.
5|Page
Two level algorithm: This algorithm was proposed to show better improvement in
accuracy of prediction as compare to Smith algorithm. It is because it requires two level
of storage.
a. History register (HR maintains the information of last m branches)
b. Pattern table
2. Two level prediction table:
Two separate tables are defined to analyze the prediction of the branch instructions. That
are local and pattern history table. The local table contains the address of lowest bits of
every branch instruction and records the history of most current execution of branch
instruction. Pattern history table has different entries of each branch and the appropriate
entries are selected by counter.
3. Hybrid branch predictor:
This idea is used to implement more than one prediction mechanism and the last
prediction depends upon the predictors which predicts the best prediction in the past. In
such predictors different predictors give a better outcome for different branches. It also
helps in reducing time by using more than one predictor at a time. The only
disadvantages of hybrid branch predictors are that it needs selection counter and larger
access latency.
4. Neutral predictor:
This is one of the predictor chosen to check the performance of branch prediction. It
depends upon the number of layers, number of neurons in each layer and neuron
connection types. Elman network is the advanced type of neural method in which better
accuracy is observed and less miss-prediction rate in branch prediction.
CONCLUSION:
REFERENCES:
1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
7.
6|Page