PYTHON:

bp_main.py

#!/usr/bin/python3

import sys, re, fileinput import branchpredictor

def sys_error(s): print ("Error: " + s) exit(1)

def parse_config(s): if s == '': return (0, 0, 0) fields = s.split(",") if (len(fields) != 3): sys_error("Invalid configuration. Need three numbers, like 2,1,10.") m = int(fields[0]) n = int(fields[1]) k = int(fields[2]) assert m >= 0 and m = 1 and n = 0 and k

argc = len(sys.argv) if (argc

config0 or config1 is a string like m,n,k. m : number of bits in global history n : number of bits in counter k : number of bits in the index from branch address

For example, 1,2,10 means 1 bit global history, 2-bit counters, and 10 bits from branch address. The total number of bits in an index is m + k.

tracefile is text file containing branch traces. If no file is specified, the program tries to read from stdin. ''')

verbose = 0 config0 = "" config1 = "" opt_nbts = 10 files = []

for a in sys.argv[1:]: if (a == '-v'): verbose = 1 elif (a.startswith('-t')): opt_nbts = int(a[2:]) elif (',' in a): if (config0 == ''): config0 = a else: config1 = a else: files.append(a)

if verbose: print("nbts={} config0='{}', config1='{}'".format(opt_nbts, config0, config1))

if (config0 == ''): sys_error("Specify at least one configuration.")

if opt_nbts 20: sys_error("The number of bits for selecting a selector in tournament must be between 4 and 20.")

config_parsed0 = parse_config(config0) config_parsed1 = parse_config(config1)

BP = branchpredictor.BranchPredictor()

""" If a second configuration was provided and its BHT index size is greater than zero, use tournament-style predictor. Else use local or global predictor. """ if config_parsed1[2] > 0: # the '*' operator unpacks the tuple into positional arguments for this method BP.configure_tournament(opt_nbts, *config_parsed0, *config_parsed1) else: BP.configure(*config_parsed0)

BP.set_verbose(verbose)

""" This regex pattern matches when the line begins with an address that can (optionally) be prefixed with '0x', followed by one or more alphanumeric characters, followed by whitespace and then either a 1, T, t (taken) or 0, NT, nt (not taken) """ pattern = re.compile('^((0x)*([0-9A-Fa-f]+))\s+(0|1|T|t|NT|nt)\s*$')

n_lines = 0

for line in fileinput.input(files): n_lines += 1 m = re.search(pattern, line) if (m): # in the pattern, each set of parentheses represents a "group" address = int(m.group(1), 0) outcome = 1 if m.group(4)[0] in '1Tt' else 0 # print(address, outcome) BP.predict(address, outcome)

BP.report()

branchpredictor.py

from array import array

class BranchPredictor :

# constructor for tournament predictor def __init__(self): self.mode = -1

def configure_tournament(self, nbts, m0, n0, k0, m1, n1, k1): self.mode = 2 # two because we are using two predictors self.verbose = 0 self.nbts = nbts self.mask_selector_index = (1

# constructor for bimodal predictor def configure(self, m, n, k): self.mode = 1 # one because we are using one predictor self.verbose = 0 self.m = m self.n = n # TODO: add your code here before calling reset # For example, you can generate masks here. # mask_ghr = (1

def reset(self): if (self.mode == 1): self.g_hist= 0 # creates an array of size 2^(nb_i) filled with zeroes, for counters # the data in the array is of type 'signed char', specified by the first argument # you need to calculate the number of counters. Use

def set_verbose(self, v): if (self.mode == 1): self.verbose = v elif (self.mode == 2): self.verbose = v self.prediction0.set_verbose(v) self.prediction1.set_verbose(v)

# return 1 for taken prediction # return 0 for not-taken def predict(self, addr, outcome): self.num_branches += 1 self.num_taken += outcome # remember to set the prediction (the return value) for all cases # it is set to 0 for now, always predicting not-taken. prediction = 0 if (self.mode == 1): # Predict, update, return # TODO # update global history self.g_hist = (self.g_hist

# report the statistics def report(self): if (self.mode == 1): print("Total number of branches = {}".format(self.num_branches)) print("Number of taken branches = {}".format(self.num_taken)) print("Number of untaken branches = {}".format(self.num_branches - self.num_taken)) print("Number of mispredictions = {}".format(self.num_mispredictions)) if (self.num_branches): print("Misprediction rate = {:.2f}%".format(self.num_mispredictions/self.num_branches * 100)) elif (self.mode == 2): print("Predictor 0:") self.predictor0.report() print(" Predictor 1:") self.predictor1.report() print(" ") if (self.num_branches): print("Misprediction rate = {:.2f}%".format(self.num_mispredictions/self.num_branches * 100)) print("Percentage of using 0 = {:.2f}%".format(self.num_selected0/self.num_branches * 100))

OR JAVA:

BPMain.java

import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.regex.Matcher; import java.util.regex.Pattern;

public class BPMain { private static final String usage = new StringBuilder() .append("Usage: bp_main config0 [config1] tracefile ") .append("config0 and config1 are strings like m,n,k. ") .append("\tm : number of bits in global histor y") .append("\tn : number of bits in counter ") .append("\tk : number of bits in the index to BHT. ") .append("-tX\t: use X number of bits to index tournament predictors ") .append("-v\t: verbose mode ") .append("For example, 1,2,10 means 1 bit global history, 2-bit counters, ") .append("and 10 bits from branch address. The total number of bits in ") .append("an index is m + k. ") .toString();

public static void main(String[] args) { if (args.length 20) { systemError("The number of bits for selecting a selector in tournament must be between 4 and 20."); } int[] config0Parsed = parseConfig(config0); int[] config1Parsed = parseConfig(config1); BranchPredictor bp = new BranchPredictor(); /* * If a second configuration was provided and its BHT index size is greater * than zero, use tournament-style predictor. Else use local or global predictor. */ if (config1Parsed[2] > 0) { bp.configureTournament(optNBits, config0Parsed[0], config0Parsed[1], config0Parsed[2], config1Parsed[0], config1Parsed[1], config1Parsed[2]); } else { bp.configure(config0Parsed[0], config0Parsed[1], config0Parsed[2]); } bp.verbose = verbose; readFile(bp, args[args.length - 1]); bp.report(); } private static void readFile(BranchPredictor bp, String filepath) { String line; BufferedReader br; /* * This regex pattern matches when the line begins with an address that can * (optionally) be prefixed with '0x', followed by one or more alphanumeric characters, * followed by whitespace and then either a 1, T, t (taken) or 0, NT, nt (not taken) */ String pattern = "^((0x)*([0-9A-Fa-f]+))\\s+(0|1|T|t|NT|nt)\\s*$"; Pattern r = Pattern.compile(pattern); long addr; int outcome; try { br = new BufferedReader(new FileReader(filepath)); while ((line = br.readLine()) != null) { Matcher m = r.matcher(line); if (m.find()) { // in the pattern, each set of parentheses represents a "group" addr = Long.decode(m.group(1)); outcome = "1Tt".indexOf(m.group(4).charAt(0)) != -1 ? 1 : 0; bp.predict(addr, outcome); } } } catch (IOException e) { System.err.println("Error: " + e.getMessage()); } } private static void systemError(String s) { System.err.println(s); System.exit(1); } private static int[] parseConfig(String s) { if (s.length() == 0) return new int[] { 0, 0, 0 }; String[] fields = s.split(","); if (fields.length != 3) systemError("Invalid configuration. Need three numbers, like 2,1,10."); try { int m = Integer.parseInt(fields[0]); int n = Integer.parseInt(fields[1]); int k = Integer.parseInt(fields[2]); if (m 16 || n 4 || k 16) { systemError("Arguments do not fall within the correct range."); } return new int[] { m, n, k }; } catch (NumberFormatException e) { systemError("Invalid arguments (must be numbers)."); return null; } }

}

BranchPredictor.java

import static java.lang.Math.toIntExact;

public class BranchPredictor {

public int mode; public BranchPredictor predictor0; public BranchPredictor predictor1; public int m, n, nbI, nbA, nbits, gHist, maskGHist, maskAddr, counterMax, maskPrediction, maskSelectorIndex; public int[] bht; public int[] selectors; public int numBranches, numTaken, numMispredictions, numSelected0; public boolean verbose; // constructor for tournament predictor public BranchPredictor() { this.mode = -1; } public void configureTournament(int nbits, int m0, int n0, int k0, int m1, int n1, int k1) { this.mode = 2; // two because we are using two predictors this.nbits = nbits; // maskSelectorIndex = 0b11111... where the number of 1's is equal to nbits this.maskSelectorIndex = (1 0) { double percentage = ((double)this.numMispredictions / (double)this.numBranches) * 100; System.out.printf("Misprediction rate = %.2f%% ", percentage); } } else if (this.mode == 2) { System.out.println("Predictor 0:"); this.predictor0.report(); System.out.println(" Predictor 1:"); this.predictor1.report(); System.out.println(" "); if (this.numBranches > 0) { double mispredictionRate = ((double)this.numMispredictions / (double)this.numBranches) * 100; double percentUsing0 = ((double)this.numSelected0 / (double)this.numBranches) * 100; System.out.printf("Misprediction rate = %.2f%% ", mispredictionRate); System.out.printf("Percentage of using 0 = %.2f%% ", percentUsing0); } } } }

OTHER FILES:

branchtrace1.txt (first 50 lines)

0x8048378 0 0x8048383 1 0x804834e 0 0x4000b488 0 0x4000b496 0 0x4000b4b8 0 0x40007bae 0 0x40007bb6 0 0x40007bc1 0 0x40007bcc 0 0x40007bd7 0 0x40007be4 0 0x40007c03 0 0x40007c41 1 0x40007c6e 0 0x40007c74 1 0x40007c86 0 0x40007c8f 0 0x40007cc6 0 0x40007cda 1 0x40007d0f 0 0x40007d21 0 0x40007d38 0 0x40007d40 0 0x400115bc 1 0x40007d5d 1 0x40007cf7 0 0x40007d0f 1 0x40007cea 0 0x40007cf7 0 0x40007d0f 1 0x40007cea 0 0x40007cf7 1 0x40007dd0 1 0x40007e18 0 0x40007e26 0 0x400115bc 1 0x4000c6b9 0 0x4000c6c0 0 0x400115bc 1 0x4000c6e0 0 0x4000c6e7 0 0x40007e35 1 0x40007c6e 0 0x40007c74 1 0x40007c86 0 0x40007c8f 0 0x40007cc6 0 0x40007cda 1 0x40007d0f 0

branch-trace-gcc.txt (first 50 lines)

0xb7fa3ac8 1 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 1 0xb7fa3adf 0 0xb7fa3ae4 0 0xb7fa3af0 0 0xb7fa3b0c 1 0xb7fa3ae4 0 0xb7fa3af0 0 0xb7fa3b0c 1 0xb7fa3ae4 0 0xb7fa3af0 0 0xb7fa3b0c 1 0xb7fa3ae4 0 0xb7fa3af0 0 0xb7fa3b0c 0 0xb7fa3b18 0 0xb7fa3b22 0 0xb7fa3b2f 0 0xb7fa3b3c 0 0xb7fa3b49 0 0xb7fa3b56 0 0xb7fa3b63 0 0xb7fa3b70 0 0xb7fa3b7d 0 0xb7fa3b83 0 0xb7fa3b91 0

In this project, you will develop a branch predictor simulator, using either Python (Python 3) or Java (Java 8). The simulator can simulate three kinds of branch predictors: simple bimodal BHT, correlating predictor, and tournament predictor. As we have discussed, the bimodal predictor is a special case of correlating predictor (with 0 bit global history). For simplicity, we will use correlating predictor to refer to both The simulator reads branch traces from the standard input and prints out the statistics to the standard output. A template is provided to help you complete the project The link to download the template and branch traces will be announced on Piazza It is highly recommended that you use a version control system (like git) for the project. However, your repository must be private and must not be accessible to other students. Format of branch trace files Branch trace files are text files. At the beginning of each line is the address of a branch instruction, which can be decimal or hexadecimal. Separated from the address by at least one space, a 0 or 1 indicates the outcome of the branch. 1 is for taken, and 0 for not taken. The simulator also recognize T and NT Two trace files are provided. Note that the traces are not from MIPS processors. The branches can be located anywhere. Do not divide the addresses by 4 The trace file can be large. When testing your code, you do not have to feed all the events to the simulator. You can use your favorite text editor to save part of big files to smaller files. You can also use text file tools like 'head' to select the first n lines. For example, the following command prints to the console the first 10 lines from branch-trace.txt head -n 10 branch-trace.txt You can save the 10 lines to a file by redirection Template The template provided can read branch traces from the standard input and feed the addresses and outcome to predictors. After all branches are processed, the program prints out the statistics. Of course, nothing is correct before you implement the predictors There are two files in the template. Do not modify the main file (bp main.py or BPMain.java) A correlating predictor (and a bimodal predictor) maintains a one-dimensional array of counters. It can be configured by a string like m,n,k where m, n, and k are three integers. m is the number of bits in global history. n is the number of bits in the counter (for prediction), and k is the number of bits from the branch address to form the In this project, you will develop a branch predictor simulator, using either Python (Python 3) or Java (Java 8). The simulator can simulate three kinds of branch predictors: simple bimodal BHT, correlating predictor, and tournament predictor. As we have discussed, the bimodal predictor is a special case of correlating predictor (with 0 bit global history). For simplicity, we will use correlating predictor to refer to both The simulator reads branch traces from the standard input and prints out the statistics to the standard output. A template is provided to help you complete the project The link to download the template and branch traces will be announced on Piazza It is highly recommended that you use a version control system (like git) for the project. However, your repository must be private and must not be accessible to other students. Format of branch trace files Branch trace files are text files. At the beginning of each line is the address of a branch instruction, which can be decimal or hexadecimal. Separated from the address by at least one space, a 0 or 1 indicates the outcome of the branch. 1 is for taken, and 0 for not taken. The simulator also recognize T and NT Two trace files are provided. Note that the traces are not from MIPS processors. The branches can be located anywhere. Do not divide the addresses by 4 The trace file can be large. When testing your code, you do not have to feed all the events to the simulator. You can use your favorite text editor to save part of big files to smaller files. You can also use text file tools like 'head' to select the first n lines. For example, the following command prints to the console the first 10 lines from branch-trace.txt head -n 10 branch-trace.txt You can save the 10 lines to a file by redirection Template The template provided can read branch traces from the standard input and feed the addresses and outcome to predictors. After all branches are processed, the program prints out the statistics. Of course, nothing is correct before you implement the predictors There are two files in the template. Do not modify the main file (bp main.py or BPMain.java) A correlating predictor (and a bimodal predictor) maintains a one-dimensional array of counters. It can be configured by a string like m,n,k where m, n, and k are three integers. m is the number of bits in global history. n is the number of bits in the counter (for prediction), and k is the number of bits from the branch address to form the