Assignment 2: Pipelined Processors

Table of Contents

Purpose

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

Two hours (one lab session) are allocated for this lab.

Theoretical Background

You should review one of the folowing resources before you start working on this lab: Also, before you start working on the 3rd problem for this lab, you should read the instructions on how you can access the SimpleScalar tool set on IDA 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 that goes through the pipeline is an LD? What if the instruction is an ADD? Consider that the instruction format and semantics are the same as those in the SimpleScalar architecture.
  2. Pipeline basics II
    Problem 12.7 from the course book (8th edition). For older versions of the book, look for problem 12.2 in the 6th edition, or 11.2 in the 5th edition. In addition, solve the same problem considering that the 2nd instruction is a conditional jump. Explain the difference between the two diagrams, if any.

    If you do not have the book, you can ask for the problem text from the lab assitants or you can get it from /home/TDTS55/docs/lab_problems.txt

  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/TDTS55/spec95-big/go.ss 3 8

    Use the branch-prediction metrics generated in the output file in order to compare the accuracy of the prediction schemes. When making the comparision, also take into consideration the algorithm underlying the implementation of each branch predictor.
    For each case, compute the speed-up relative to the least performant branch predictor case.
    Note: You should use the default settings of the simulator for the more complex branch predictors
    NEW: If you feel that the simulations take too much time, you can use the output files existing in the /home/TDTS55/www-pub/labs/pipeline/out directory

What to Hand-In

  1. The explanations for LD and ADD as required. Use pictures if necessary.
  2. The two diagrams representing the flow of instructions through the pipeline, one for the case with and one for the case withouth the conditional jump.
  3. The the output files for each of the six simulations. 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 (a description of the bimodal, 2level and combined predictors can be found here).

Resources