Lab Assignment 2: Instruction Pipelining
Table of Contents
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
- Lab 0: Using SimpleScalar at IDA's Machines
Assignments
- 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)
, wherert
andrs
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 isADD rd, rs, rt
, wherers, rt
are the source registers andrd
is the destination register.
Consider that the instruction format and semantics are the same as those in the SimpleScalar tool set.
- Describe briefly what happens in each stage when the instruction going through the pipeline is an
- 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. Thesim-outorder
simulator allows you to simulate 6 different types of branch predictors. The predictors that you will use in this lab aretaken
,bimod (bimodal)
,2lev (2level, aka local)
, andperfect
.- 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 usingtaken
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
more information about the
bimodel
and2level (aka local)
predictors in sections 3 and 4 of this document. - For each branch predictor, compute the speed-up relative to the least performant branch predictor (Hint: use the metric "sim_cycle").
- For each of these possible branch prediction schemes,
run a simulation using the
What to report
- For Assignment 1: Describe what heppens in each stage of the
LB
andADD
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 thetaken
or why2level
perdictor performs better/worst than thebimodal
.
Page responsible: Zebo Peng
Last updated: 2024-12-03