代写Lab 5: Branch Prediction

2023-11-23 代写Lab 5: Branch Prediction

Lab 5: Branch Prediction

In this lab you will implement a simulator for a 2-level branch predictor with a 2-

bit saturating counter. You are provided with a text file containing a trace of branch

instructions consisting of the PC at which each branch occurs, and whether the

branch is Taken (1) or Not Taken (0).

Your goal is to write code to simulate a branch predictor on this trace. Your output

file indicates, for each branch in the trace, whether it was predicted as Taken or Not

Taken.

Two-Level Branch Predictor

Your design must consist of a PHT that has 2m 2-bit saturating counter, and a

global BHT that has 2

h w-bit branch history. Each saturating predictor in the PHT

should be initialized in 2-bit-“10” (Predict Weak Taken) state and is updated as per

the finite state machine discussed in class. The value of m is specified in the

config.txt.

00 01 10 11

Strong Not Taken Weak Not Taken Weak Taken Strong Taken

Each BHT entry should be initialized to 0.

000

001

010

011

100

101

110

111

Architecture

PC:

0 ... 0 0 0 1 0 1 0 0

LSB

010

BHT

w bit

h bit

(m-w) bit

0101 010

w bit

Example: h=3 w=3 m=7

0000000

...

0101010

1111111

10

PHT

2 bit

We will start from the branch address (PC) to access the saturating counter for a

prediction. Here are more details for the figure:

Step 1: The BHT is indexed using h bits from the PC, starting from the 3rd LSB.

The BHT has 2

h entries with each entry having w bits.

Step 2: The w bits from the BHT are concatenated with (m-w) bits from the PC

(again starting from the 3rd LSB) as shown in the figure. Be careful to place the

(m-w) bits in the upper portion of the concatenation and the w bits from the

BHT into the lower portion of the concatenation as shown in the Figure.

Step 3: We use these m bits to index into the PHT which has 2m entries. Each PHT

entry gives us our 2-bit prediction for the current branch. Both Strong Not Taken

(00) and Weak Not Taken (01) mean we predict the branch to be Not Taken. On the

other hand, both Strong Taken (11) and Weak Taken (10) indicate that we predict

the branch to be Taken.

Step 4: Compare the prediction with the actual branch action as provided in the

trace file. If the branch was indeed taken, update the PHT entry towards the taken

side. If the branch was not taken, update the PHT entry towards the not taken side.

Example: Suppose our PHT entry was 01 (Weak Not Taken) and the actual branch

action was Taken (1). We would update the PHT entry to be 10 (Weak Taken).

Step 5: Update the BHT. Example: Suppose the current BHT entry is 010 and the

branch action is Not Taken (0), then you need to update the BHT entry to 100 by

left-shifting the BHT and placing 0 in the LSB.

Config File

The config file config.txt contains 3 lines with the value of m, h, w.

Trace File

The trace file, trace.txt, contains one branch per line. Each line has the branch

address (PC) for the corresponding branch (in hex format) followed by a single bit

indicating Taken (1) or Not Taken (0). A sample trace file is provided.

Output Format

The output from your simulator should be a file trace.txt.out that has one line per

branch. Each line has a single bit that indicates whether that branch was predicted

as Taken (1) or Not Taken (0).

What to Submit

1. Code

a. Your source code. On compilation, we should be able to execute your

simulator with the following command

./branchsimulator.out config.txt trace.txt

b. Your simulator should output a file trace.txt.out in the same directory.

c. You must upload ONLY one file on Gradescope:

“branchsimulator.cpp”. Do not zip the file or upload any other file.