README.md 3.75 KB
Newer Older
Lawrence Li's avatar
Lawrence Li committed
1
# CSCI 320 Project 2 - Branch predictors
Lawrence Li's avatar
Lawrence Li committed
2
3
4

Bucknell University

Lawrence Li's avatar
Lawrence Li committed
5
6
7
Fall 2021 Semester

## Group members
Jacky Lin's avatar
Jacky Lin committed
8
9
10
11
12
| Names       |
| :---------- |
| Edward Chen |
| Jacky Lin   |
| Lawrence Li |
Lawrence Li's avatar
Lawrence Li committed
13

Lawrence Li's avatar
Lawrence Li committed
14
## Project description
Lawrence Li's avatar
Lawrence Li committed
15

Jacky Lin's avatar
Jacky Lin committed
16
This RISC-V project aims to implement all branch predictors we learned from class and evaluate them on the benchmark programs. We have implemented 6 types of branch predictors each as a class in [branch_predict](branch_predict.py), including static, global, local, Gshare, Pshare, and tournament. 
Edward(Yida) Chen's avatar
Edward(Yida) Chen committed
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

The branch predictors are tested on the [hello](riscv_isa/programs/hello), [return](riscv_isa/programs/return), and 7 benchmark programs in [riscv_isa/programs/benchmarks](riscv_isa/programs/benchmarks). The index bits of PC, size of correlation register, and size of saturation counters are all set to 2 in our experiments. The initial value of the saturation counter is 00.

The result of branch prediction outcomes and the actual branch results are saved in the csv files in [results](results) directory. The first column of all csv files contains the branch predictions, and the second column of all csv files contains the actual branch outcomes. 

<figure class="image">
    <img src="figures/overall_predictions.png" width="500" height="" />
    <figcaption>Fig 1. Overall Performance of Branch Predictors on Selected Programs</figcaption>
</figure>

To further investigate the influence of predictor size on the prediction accuracy, we test BHT and PHT predictors with different PC index bits and correlation register sizes (2, 4, and 8 bits). The results of this experiment can be found in the directory, [Results_BHT_PHT_48](Results_BHT_PHT_48).

<figure class="image">
    <img src="figures/compare_BHT_predictions.png" width="500" height="" />
    <figcaption>Fig 2. Compare the BHT Prediction Accuracy with Different Numbers of Index bits</figcaption>
</figure>

<figure class="image">
    <img src="figures/compare_PHT_predictions.png" width="500" height="" />
    <figcaption>Fig 3. Compare the PHT Prediction Accuracy with Different Sizes of Correlation Registers</figcaption>
</figure>
Lawrence Li's avatar
Lawrence Li committed
38

Jacky Lin's avatar
Jacky Lin committed
39

Jacky Lin's avatar
Jacky Lin committed
40
## Usage 
Lawrence Li's avatar
Lawrence Li committed
41

Jacky Lin's avatar
Jacky Lin committed
42
43
44
We generated the branch result file from the `onestage_elf_project2.py` and dumped all the files (`pkl` format ) into a folder called `all_pkl_files/`. 

After that, run `main.py` . User can select which branch predictor to use as specified below (default is Static):
Lawrence Li's avatar
Lawrence Li committed
45

Jacky Lin's avatar
Jacky Lin committed
46
47
48
49
50
51
52
| Branch Predictor | Option |
| :--------------: | :----: |
|      Static      |  `s`   |
|       BHT        |  `b`   |
|       PHT        |  `p`   |
|      GShare      |  `g`   |
|      PShare      |  `x`   |
Lawrence Li's avatar
Lawrence Li committed
53
|    Tournament    |  `t`   |
Jacky Lin's avatar
Jacky Lin committed
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

```bash
python main.py [-h] [-s] [-b] [-p] [-g] [-x] [-t] [path [path ...]]
```
Where `path` is the input file name or directory.

Note that if multiple predictor is specified, it uses the first one.

Docs
```
usage: main.py [-h] [-s] [-b] [-p] [-g] [-x] [-t] [path [path ...]]

The following arguments can help debug and test the program

positional arguments:
  path        input filepath

optional arguments:
  -h, --help  show this help message and exit
  -s          if use static predictor mode
  -b          if use BHT predictor mode
  -p          if use PHT predictor mode
  -g          if use GShare predictor mode
  -x          if use PShare predictor mode
  -t          if use Tournament predictor mode
```

## Develop Mode

To use our branch predictor in your own project, you can import need predictor class in [branch_predict.py](branch_predict.py) and instantiate. All the predictor classes have 3 methods: `__init__`, `predict`, `update`. To use our class, you need to use the `Instruction` class as input to `predict()` method. After that input whether the branch is taken or not as a `int` into `update()` method. For example,

```python
bht = BHT()
bht.predict(instr)
bht.update(is_taken)
```