Branch_Predictors

#!/usr/bin/python
import sys

class gshare():
    def __init__(self, num_entries):
    self.num_entries = num_entries
    self.predictions = [0]*self.num_entries

    def get_prediction(self, index):
    if self.predictions[index] > 1:
        return 1
    else:
        return 0

    def update(self, index, branch_outcome):
    if branch_outcome == 1 and self.predictions[index] < 3:
        self.predictions[index] += 1

    if branch_outcome == 0 and self.predictions[index] > 0:
        self.predictions[index] -= 1



class local():
    def __init__(self, num_entries):
    self.num_entries = num_entries
    self.predictions = [0]*self.num_entries

    def get_prediction(self, index):
    if self.predictions[index] > 1:
        return 1
    else:
        return 0

    def update(self, index, branch_outcome):
    if branch_outcome == 1 and self.predictions[index] < 3:
        self.predictions[index] += 1

    if branch_outcome == 0 and self.predictions[index] > 0:
        self.predictions[index] -= 1



class tournament():
    def __init__(self, num_entries):
    self.num_entries = num_entries
    self.predictions = [0]*self.num_entries

    def get_prediction(self, index):
    if self.predictions[index] > 1:
        return 1
    else:
        return 0

    def update(self, index, global_pred, local_pred, branch_outcome):
    if branch_outcome == global_pred and branch_outcome != local_pred and self.predictions[index] < 3:
        self.predictions[index] += 1

    if branch_outcome != global_pred and branch_outcome == local_pred and self.predictions[index] > 0:
        self.predictions[index] -= 1




def main():

    predictor3 = gshare(4096)
    predictor4 = local(256)
    predictor5 = tournament(1024)

    local_hist_length = 8
    local_table_size = 1024

    global_hist_length = 12

    total_predictions = 0
    max3 = max4 = max5 = 0
    wrong3 = wrong4 = wrong5 = 0

    misslist3 = []
    misslist4 = []
    misslist5 = []

    global_history = [0]*global_hist_length

    local_table = [[0]*local_hist_length for x in xrange(local_table_size)]

    _ = sys.stdin.readline()  # throw away first line

    for line in sys.stdin:  # get the two feilds and convert them to integers
    [pc, branch_outcome] = [int(x,0) for x in line.split()]   #int(x,0) - "look at the string, and guess the base"

    global_hist_string = ''.join([str(x) for x in global_history])  #convert list to string
    global_hist_pattern = int(global_hist_string, 2)    #convert string to binary number
    global_index = ((pc>>2) % 4096) ^ global_hist_pattern    #XOR history pattern with lower bits of PC

    local_table_index = (pc>>2) % local_table_size
    local_hist_string = ''.join([str(x) for x in local_table[local_table_index]])
    local_index = int(local_hist_string, 2)

    tour_index = global_index >> 2

    this_prediction3 = predictor3.get_prediction(global_index)
    this_prediction4 = predictor4.get_prediction(local_index)
    this_prediction5 = predictor5.get_prediction(tour_index)

    if this_prediction5 == 1:
        this_prediction5 = this_prediction3
    else:
        this_prediction5 = this_prediction4

    total_predictions += 1


    if this_prediction3 != branch_outcome:
        wrong3 += 1
            misslist3.append(pc)

    if this_prediction4 != branch_outcome:
        wrong4 += 1
            misslist4.append(pc)

    if this_prediction5 != branch_outcome:
        wrong5 += 1
            misslist5.append(pc)


    predictor3.update(global_index, branch_outcome)
    predictor4.update(local_index, branch_outcome)
    predictor5.update(tour_index, this_prediction3, this_prediction4, branch_outcome)

    global_history.append(branch_outcome)   #update history tables
    local_table[local_table_index].append(branch_outcome)

    global_history = global_history[1:]    #discard the oldest outcomes
    local_table[local_table_index] = local_table[local_table_index][1:]


    print "\nTotal predictions:", total_predictions

    print "wrong predictions3:", wrong3
    print "wrong predictions4:", wrong4
    print "wrong predictions5:", wrong5
    print

    print predictor3.__class__.__name__, 100* (total_predictions-wrong3) / float(total_predictions)
    print predictor4.__class__.__name__, 100* (total_predictions-wrong4) / float(total_predictions)
    print predictor5.__class__.__name__, 100* (total_predictions-wrong5) / float(total_predictions)
    print

    for addr in set(misslist3):
        count = misslist3.count(addr)
        if count > max3:
            max3 = count
            worst_pc3 = addr

    for addr in set(misslist4):
        count = misslist4.count(addr)
        if count > max4:
            max4 = count
            worst_pc4 = addr

    for addr in set(misslist5):
        count = misslist5.count(addr)
        if count > max5:
            max5 = count
            worst_pc5 = addr

    print "global:      ", hex(worst_pc3), max3
    print "local:       ", hex(worst_pc4), max4
    print "tournament   ", hex(worst_pc5), max5
    print



if __name__ == "__main__":
       main()