Branch Predictor

Introduction

This project implements a branch predictor simulator that implements the following branch prediction algorithms:

• Always Taken
• Standard 2-bit predictor
• gshare
• Profiled

The main goal of this project is to compare the performance of the different branch prediction algorithms, identifying key strengths and weaknesses of each.

Project Structure

The project is structured as follows:

• main.go: The main entry point of the program. This file reads the trace file and configuration file, and runs the branch predictor simulator.
• branchpred/: This directory contains the implementation of the branch prediction algorithms.
• instruction/: This directory contains the implementation of the reading of trace files in instruction structures.
• utils/: This directory contains utility functions used by the branch predictor simulator.
• configs/: This directory contains example configuration files for each algorithm. These examples can be modified to test different configurations of the algorithms.
• outputs/: This directory contains the output files generated by the branch predictor simulator. Within this directory are two subdirectories:
  • results/: This directory contains the results of the simulation in JSON format. Each algorithm has its won subdirectory within this directory displaying its results for each trace file.
  • metadata/: This directory contains the output files in JSON format. Each algorithm has its own subdirectory within this directory displaying the metadata for each trace file.
• trace-files/: This directory contains the trace files used. Unzip the trace_files.zip file to access the trace files folder.

Instructions

To run using the executable:

./branch-predictor trace_files/<trace-file> configs/<config-file>

To compile and run:

go run main.go trace_files/<trace-file> configs/<config-file>

To build the executable:

go build -o branch_predictor main.go

Documentation

To view documentation:

godoc -http=:6060 -index

Then navigate to http://localhost:6060/pkg/github.com/nsengupta5/Branch-Predictor/

Creating a Config File

The config file for each algorithm is a JSON file detailing the configuration settings for the algorithm. The configs directory contains sample configuration files for each algorithm. These examples can be modified to test different configurations of the algorithms.

The config file has the following fields:

• algorithm: The name of the algorithm to use. This can be one of always-taken, two-bit, gshare, or profiled.
• max_lines: A list of the maximum number of lines to read from the trace file. For each number in the list, the branch predictor simulator will run a simulation of the algorithm for that number of lines. If the value is -1, the simulator will run the simulation for the entire trace file.
• configs: A list of configuration objects for the algorithm. Each configuration object represents a particular configuration settings for the various fields of the algorithm. The branch predictor simulator will run a simulation of the algorithm for each configuration oject specified. The fields in each configuration object depend on the algorithm. These fields are described in the following section.

Always Taken

The always-taken algorithm does not require any configuration settings.

An example configuration file for the always-taken algorithm is as follows:

{
    "algorithm": "always-taken",
    "max_lines": [1000, 5000],
    "configs": []
}

Two-Bit

The two-bit algorithm requires the following configuration settings:

• table_size: The size of the branch prediction table. This can be one of 512, 1024, 2048, or 4096.
• initial_state: The initial state of the branch prediction table. This can be one of StronglyTaken, WeaklyTaken, WeaklyNotTaken, or StronglyNotTaken.

An example configuration file for the two-bit algorithm is as follows:

{
    "algorithm": "two-bit",
    "max_lines": [10000, -1],
    "configs": [
        {
            "table_size": 512,
            "initial_state": "StronglyNotTaken"
        },
        {
            "table_size": 2048,
            "initial_state": "WeaklyNotTaken"
        }
    ]
}

Gshare

The gshare algorithm requires the following configuration settings:

• table_size: The size of the branch prediction table. This can be one of 512, 1024, 2048, or 4096. This will also be the size of the global history register.
• initial_state: The initial state of the branch prediction table. This can be one of StronglyTaken, WeaklyTaken, WeaklyNotTaken, or StronglyNotTaken.

An example configuration file for the gshare algorithm is as follows:

{
    "algorithm": "gshare",
    "max_lines": [10, 1000, 5000, -1],
    "configs": [
        {
            "table_size": 1024,
            "initial_state": "StronglyTaken"
        },
        {
            "table_size": 2048,
            "initial_state": "WeaklyTaken"
        },
        {
            "table_size": 4096,
            "initial_state": "WeaklyNotTaken"
        }
    ]
}

Profiled

The profiled algorithm requires the following configuration settings:

• table_size: The size of the branch prediction table. This can be one of 512, 1024, 2048, or 4096.
• initial_state: The initial state of the branch prediction table. This can be one of StronglyTaken, WeaklyTaken, WeaklyNotTaken, or StronglyNotTaken.
• strata_size: The number of strata to use for the profiled branch prediction algorithm.
• strata_proportion: The proportion of the branch prediction table to use for each strata. This should be a list of floats that sum to 1.0.

An example configuration file for the profiled algorithm is as follows:

{
    "algorithm": "profiled",
    "max_lines": [1000, 5000],
    "configs": [
        {
            "table_size": 1024,
            "initial_state": "StronglyTaken",
            "strata_size": 10,
            "strata_proportion": 0.2
        },
        {
            "table_size": 2048,
            "initial_state": "WeaklyTaken",
            "strata_size": 8,
            "strata_proportion": 0.3
        }
    ]
}