Lab Assignment 2: Instruction Pipelining

Table of Contents

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

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 folowing resources before you start working on this lab:

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

Assignments

1. Pipeline basics I
   Consider a processor with 6 stages: IF(instruction fetch), DA(instruction decode), CO(calculate operands addresses), FO(fetch operands), EX(intruction execution), WB(write results).
   • Describe briefly what happens in each stage when the instruction going through the pipeline is an LB?
   • What if the instruction is an ADD?
   • Consider that the instruction format and semantics are the same as those in the SimpleScalar tool set.
2. Pipeline basics II
   
   • Solve problem 14.7 in the 9th edition of the course book. It is the same as problem 12.7 in the 7th/8th edition, problem 12.2 in the 6th edition, and problem 11.2 in the 5th edition of the book. You can also downlaod the text of the problem from this URL.
   • Solve the same problem while considering 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 6 different types of branch predictors.

   • 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 /home/TDTS08/spec95-big/go.ss 3 8
   • Use the branch-prediction metrics generated in the output file to compare the accuracy of the prediction schemes. When making the comparision, also consider the algorithm underlying the implementation of each branch predictor. 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, conrresponding to the case with and without the conditional jump, respectively.
• Report the accuracy of predictors and a comparative evaluation based on the results obtained from the simulation and on the algorithm implementing the behaviour for each predictor. Print the output files for each of the six simulations, if needed.

Resources

• Lecture notes on instruction pipelining.
• S. McFarling, Combining Branch Predictors.
• D. Burger, and T. M. Austin, The SimpleScalar Tool Set, Version 2.0, 1997.
• T. M. Austin, A User's and Hacker's Guide to SimpleScalar Architectural Tool Set, 1997.
• William Stallings, Computer Organization and Architecture, 9th edition.

Page responsible: Zebo Peng
Last updated: 2012-11-27