代做 program、代写 c/c++,Python 程序

日期：2023-11-24 11:10

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 2h 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. Architecture Example: h=3 w=3 m=7

h bit

000 001 010 011 100 101 110 111

w bit

PC:

LSB 0 ... 0 0 0 1 0 1 0 0

      10

     BHT

PHT

0000000

... 0101010

1111111

2 bit

     010

  0101

010

(m-w) bit

w 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 2h 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.