Lab Assignment 2: Instruction Pipelining

Objective

The purpose of this lab is to get insight on how pipelines work and on how their performance can be improved by branch prediction.

4 hours (2 lab sessions) are allocated for this lab.

You should review the following resources before you start working on this lab:

Pipeline basics I
Consider a processor with 6 stages, as in the lecture and according to this page of the course book: IF (instruction fetch), DI (instruction decode: determine the opcode and the operand specifiers), CO (calculate the effective address of each source operand), FO (fetch operands from memory), EI (intruction execution), WO (store the result in memory).
- Describe briefly what happens in each stage when the instruction going through the pipeline is an LB (load a byte from the main memory to a register in the CPU) using displacement addressing with an offset? Here is the format for load byte instruction: LB rt, offset(rs), where rt and rs are destination and base address registers, respectively.
- What if the instruction is an ADD (add the values in two registers and store the sum in anothe register)? The instruction format is ADD rd, rs, rt, where rs, rt are the source registers and rd is the destination register.
Consider that the instruction format and semantics are the same as those in the SimpleScalar tool set.

Pipeline basics II
- Solve this problem.
- Solve the above problem assuming that the 2nd instruction is a conditional jump. Assume that taken predictor is implemented in the system, and it makes a wrong prediction. Explain the difference between the two diagrams, if any.
Branch prediction

For this assignment you will use sim-outorder to evaluate the effects of different branch predictors. The sim-outorder simulator allows you to simulate 6 different types of branch predictors. The predictors that you will use in this lab are taken, bimod (bimodal), 2lev (2level, aka local), and perfect.
- For each of these possible branch prediction schemes, run a simulation using the go.ss benchmark.
  Here is an example on how you can run a simulation using taken predictor (which always predicts that the branch will be taken):
- Use a proper branch-prediction metric generated in the output file to compare the accuracy of the prediction schemes. When making the comparison, also consider the algorithm underlying the implementation of each branch predictor. You can find more information about the bimodel and 2level (aka local) predictors in sections 3 and 4 of this document. For each branch perdictor, compute the speed-up relative to the least performant branch predictor.
ATTENTION: You should use the default settings of the simulator for the more complex branch predictors

For Assignment 1: Describe what heppens in each stage of the LB and ADD instructions, respectively. Use figures if needed.
For Assignment 2: Draw the two diagrams representing the flow of instructions through the pipeline, corresponding to the cases with and without the conditional jump, respectively.
For Assignment 3: 1) Report the accuracy of predictors and a comparative evaluation based on the results obtained from the simulation. 2) Analyze the results based on the underlying algorithm implementing the behaviour for each predictor. 3) You should also explain why the bimodal predictor performs better/worse than the taken or why 2level perdictor performs better/worst than the bimodal.

Page responsible: Zebo Peng
Last updated: 2023-10-31