Lab Assignment 2: Instruction Pipelining

Table of Contents

• Objective
• Time allocation
• Theoretical background
• Assignments
• What to report

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.

Time Allocation

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

Theoretical background

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

• Notes from the lecture on pipelining and branch prediction
• Chapter 14.4 (on instruction pipelining) in the course book
• A description of the bimodal, 2level (local predictor) and combined predictors
• Lab 0: Using SimpleScalar at IDA's Machines

Assignments

1. 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), CO (calculate the effective address of operands in memory), 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 with displaced addressing (i.e., 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? 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.


2. 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.
3. 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 a set of different types of branch predictors. The predictors that you will use in this lab are taken, bimod, 2lev, comb, 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):
     ./sim-outorder -bpred taken go.ss 3 8
   • 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 information about the bimodel and 2level (aka local), and combined predictors in sections 3, 4 and 8 of this document, respectively. For each case, compute the speed-up relative to the least performant branch predictor case.
   ATTENTION: You should use the default settings of the simulator for the more complex branch predictors.

What to report

• Explanations for LB and ADD. Use figures if needed.
• The two diagrams representing the flow of instructions through the pipeline, corresponding to the cases with and without the conditional jump, respectively.
• Report the accuracy of predictors and a comparative evaluation based on the results obtained from the simulation.
• Analyze the results based on the underlying algorithm implementing the behaviour for each predictor. For example, you must explain why the 2level predictor performs better/worse than the bimodel.

Page responsible: Zebo Peng
Last updated: 2023-09-27