Dealing with Branches Computer Science Engineering (CSE) Notes | EduRev

Digital Electronics

IT & Software : Dealing with Branches Computer Science Engineering (CSE) Notes | EduRev

The document Dealing with Branches Computer Science Engineering (CSE) Notes | EduRev is a part of the IT & Software Course Digital Electronics.
All you need of IT & Software at this link: IT & Software

Dealing with Branches
Until the instruction is actually executed, it is impossible to determine whether the branch will be taken or not. A variety of approaches have been taken for dealing with conditional branches:
• Multiple streams
• Prefetch branch target
• Loop buffer
• Branch prediction
• Delayed branch 

Multiple Streams
 A simple pipeline suffers a penalty for a branch instruction because it must choose one of two instructions to fetch next and may make the wrong choice.

A brute-force approach is to replicate the initial portions of the pipeline and allow the pipeline to fetch both instructions, making use of two streams. There are two problems with this approach:
• With multiple pipelines there are contention delays for 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 instruction needs an additional stream.

Examples of machines with two or more pipeline streams are the IBM 370/168 and the IBM 3033.

PREFETCH BRANCH TARGET When a conditional branch 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. 

Loop Buffer
 A loop buffer is a small, very-high-speed memory maintained by the instruction fetch stage of the pipeline and containing the 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.

The loop buffer has three benefits:
1. With the use of prefetching, the loop buffer will contain some instruction sequentially ahead of the current instruction fetch address.
2. If a branch occurs to a target just a few locations ahead of the address of the branch instruction,the target will already be in the buffer.
3. This strategy is particularly well suited to dealing with loops, or iterations; hence the name 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.

Figure 3.8 gives an example of a loop buffer

Dealing with Branches Computer Science Engineering (CSE) Notes | EduRev

Branch Prediction
 Various techniques can be used to predict whether a branch will be taken. Among the more common are the following:
• Predict never taken
• Predict always taken
• Predict by opcode
• Taken/not taken switch
• Branch history table

The first three approaches are static: they do not depend on the execution history up to the time of the conditional branch instruction. The latter two approaches are dynamic: They depend on the execution history.

The first two approaches are the simplest. These either always assume that the branch will not be taken or continue to fetch instructions in sequence, or they always assume that the branch will be taken and always fetch from the branch target. The predict-never-taken approach is the most popular of all the branch prediction methods.

Delayed Branch
 It is possible to improve pipeline performance by automatically rearranging instructions within a program, so that branch instructions occur later than actually desired.

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

shortcuts and tricks

,

pdf

,

video lectures

,

Important questions

,

Objective type Questions

,

mock tests for examination

,

Exam

,

MCQs

,

ppt

,

Dealing with Branches Computer Science Engineering (CSE) Notes | EduRev

,

practice quizzes

,

Previous Year Questions with Solutions

,

Dealing with Branches Computer Science Engineering (CSE) Notes | EduRev

,

study material

,

Extra Questions

,

Sample Paper

,

Free

,

Summary

,

Dealing with Branches Computer Science Engineering (CSE) Notes | EduRev

,

past year papers

,

Semester Notes

,

Viva Questions

;