Description

Devise a Branch Predictor

Architecture of High Performance
Computers

This assignment has 2 parts. In the first part, you need to devise a branch
predictor, that satisfies the given area constraints and achieves a given
minimum accuracy. Then you have to compare the results obtained using a
predictive algorithm from the WEKA toolkit or the Caffe toolkit. In the second
part, you have to install the Tejas architectural simulator, and understand its
operation. This assignment is to be done individually.

1 Implement a Branch Predictor
Framework

• Download the assignment and extract it.
• The folder traces contains five traces of branch instructions against which
your predictor is to be tested. You DO NOT have to perform any file
operations. The given framework does all that for you. Please concern
yourself with only modifying the files Predictor2400.java,
Predictor6400.java, Predictor9999.java, and Predictor32000.java. No other
file is to be modified.

• Run the following commands:

– ant clean: to clean class files and jar files from previous builds.
– ant: to compile the java files.
– ant make-jar: to create a jar file (akin to an X86 executable).
– java -jar jar/BranchPredictor.jar traces/trace1 2400: this runs the
simulator with the input trace trace1. It also tells the simulator that
the maximum allowed predictor size is 2400 bits. More on this later.

Designing a Branch Predictor

As mentioned earlier, you need to design a branch predictor that achieves good
accuracy within an area budget. Specifically, the question has four subparts:
1
maximum predictor size = (i) 2400 bits, (ii) 6400 bits and (iii) 9999 bits
(iv)32000 bits. So, you need to design a predictor with any number of tables and
registers with the constraint the sum of the table sizes (number of entries in the
table bits per entry) and register sizes (number of bits in the register) MUST be
less than the specified maximum.

Implementing your Design

• All your changes are to be limited to the filesPredictor2400.java,
Predictor6400.java, Predictor9999.java and Predictor32000.java. DO NOT
change any other file.
• For sub-part:
– (i), viz. 2400 bits, implement your predictor in the file
Predictor2400.java .
– (ii), viz. 6400 bits, implement your predictor in the file
Predictor6400.java .
– (iii), viz. 9999 bits, implement your predictor in the file
Predictor9999.java .
– (iv), viz. 32000 bits, implement your predictor in the file
Predictor32000.java. Implement either the Tage [5] or the
Preceptron [6] predictor.

• Each of these Predictor .java files have three functions that need to
be implemented:

– Predictor(): This is the constructor. Here you instantiate your tables
and registers. IMPORTANT: you are allowed to instantiate objects of
only the given Table and Register classes. Instantiating any objects or
arrays of your own will result in a zero. You may declare your own
variables, both as class members and locally in the functions.
– boolean predict(long address): Perform the branch prediction based on
the branch instructions program counter, i.e. address. Return true for
taken, false for not taken. To access your tables and registers, use the
public functions defined in Table.java and Register.java.
– void train(long address, boolean outcome, boolean predict): Train the
predictor. address refers to the branch instructions program counter,
outcome is the actual outcome of the branch, predict is the prediction
your predictor made.
2
• You may declare any other functions you may need within the
Predictor.java files. You may declare your own variables, both as
class members and locally in the functions.
• Run the commands specified above (ant clean, ant….) to run the simulator.
Try for the five different traces, as well as the three different values for the
maximum predictor size.

Evaluating your design

Create a .tar.gz archive of the files Predictor2400.java, Predictor6400.java,Predictor9999.java
and Predictor32000.java. Name it .tar.gz . Run the command python test.py
. It should tell you for the twenty different runs (five traces, four predictor
sizes):
• if you instantiated objects or arrays other than Table and Register
• if compilation succeeded
• if there was a runtime error
• if you violated the maximum size constraint
• number of branches simulated and the accuracy achieved
• if the achieved average accuracy for each predictor size (calculated over
the five traces) is greater than the stipulated minimum. Run the command
python test.py clean to clean the logs, class files and jar files from the
previous runs (deletes the directories bin, jar and logs).
Comparing with a Machine Learning Algorithm
Use a prediction algorithm from either of the toolkits WEKA [1] or Caffe [2].
Report the accuracy obtained and the confusion matrix. Specify the classification
algorithm and test options chosen. Are the predictions skewed towards one of
the classes?

2 Install the Tejas Simulator and Understand its
operation

1. Tejas is an open-source, Java-based multicore architectural simulator
developed in-house by the Srishti group. It will be used in the subsequent
assignments. The instructions to set up Tejas can be found at
http://www.cse.iitd.ac.in/tejas/install.html. Additional details about Tejas
can be found in [3] and [4].
3
2. Run ‘HelloWorld.c’ program on the simulator.
3. Explore the simulator’s working and summarize your findings.

Submitting Your Assignment

We will be evaluating using the same test.py script, but with a different set of
traces. So, make sure your implementation does not violate any of the rules.
Submit only the .tar.gz archive, created and named as described above on
Moodle. The deadline is September 5, 2022.

Grading Scheme

The marks will be based on your accuracy achieved relative to the other https://programmingmag.com
students in the class as well as creativity. The top submission achieving the
maximum accuracy will receive bonus marks. Also, you need to make a report
which includes all the information related to the branch predictors you designed
and the findings of the Tejas simulator. programmingmag.com http://col-718-assignment-1-devise-a-branch-predictor

References

1. www.cs.waikato.ac.nz/ml/weka/
2. http://caffe.berkeleyvision.org/
3. www.cse.iitd.ac.in/srsarangi/files/papers/patmospaper.pdf: Sarangi,
Smruti R., et al. Tejas: A java based versatile micro-architectural simulator.
Power and Timing Modeling, Optimization and Simulation (PAT- MOS),
2015 25th International Workshop on. IEEE, 2015.
4. http://www.cse.iitd.ac.in/tejas/overview.html
5. Seznec A. A case for (partially)-tagged geometric history length predictors.
Journal of Instruction Level Parallelism. 2006.
6. Jimnez DA, Lin C. Dynamic branch prediction with perceptrons.
InProceedings HPCA Seventh International Symposium on HighPerformance Computer Architecture 2001 Jan 19 (pp. 197-206). IEEE.
4