Lab 4 – Description

Lab 4 – Control and Data hazards in pipe lined architectures
Objectives

In this experiment the control and data hazards are explored winch will occur in pipe-lined processor architectures.

Getting started

The architectures explored in this experiment can be downloaded from this location.

Components – Lab 4

Remark

The mips_bp1 and mips_bp2 architectures don’t have branch delay slots.

Questions
Part 1 – Data hazards

The architecture “mips_pipelined”is loaded in the SIM-PL executer for the first experiment.. Some of the layout may look weird, this is because it has “holes” were new components will appear in the next architecture.

1. Write a small program (2 - 5 instructions) that exhibits a data hazard.
 
2. Solve this data hazard by rewriting your program.
 
3. [advanced] There are three types of data hazard, characterized by what combination of reads and/or writes created it. The data hazard you showed in question 1 will be a load-use hazard (true dependency), because other two cannot occur in this architecture. The other two types of data hazard are the anti-dependency, where a newer write takes effect before the read of an older instruction had taken place, and the output-dependency, where two writes to a register get swapped around in order causing the older write to be done second. Why are anti-dependencies and output-dependencies never a problem on this architecture?

Load the ” mips_pipelined_fw” architecture in the SIM-PL executer and answer the next questions:

4. How does this architecture avoid most data hazards?
5. There are still data hazards possible, give n example and explain how the architecture could be modified to avoid that hazard.
Part 2 –¬† Branch Prediction.

The architectures¬† “mips_bp1” and “mips_bp2” are explored in the second experiment.

The instructions “unconditional jumps” are not implemented in these architectures. Use the “branch” instructions.

For each of the architectures, attempt to discover how their branch predictor works by experimentation, and back up your conclusions with the result from experiments. You can look inside the implementation of the branch predictor with the editor, if you do you will still need to support your conclusions with the results from experiments.

For clarification, a static predictor does not have to make the same prediction for every branch, it only has to be same every time the same branch instruction is executed. “The same” in this context means the instruction at the same address, not an other instruction that has the same textual representation (reminder: branches in MIPS use a relative address, so if you copy and paste a branch the resulting machine code will be different) or even the same machine code. By contrast, a dynamic predictor is dynamic because it (sometimes) changes the prediction of a branch instruction when it is executed multiple times.

You may notice that it is actually impossible to conclusively prove that a predictor is static without looking at its implementation, after all it might be a dynamic predictor that just hasn’t changed its prediction just yet. For these experiments it will count as sufficient evidence that the predictor is static if the prediction it makes for a single branch is wrong at least 10 consecutive times.

For the next questions load the “mips_bp1” architecture in the SIM-PL executer. Answer the following questions:

6. is the prediction static or dynamic?

7. is there a difference in the prediction for forward branches (jumping ahead) and backward branches, and if there is, what's the difference?

8. [only if dynamic] what is the *maximum* number of times a branch can be incorrectly predicted to be not-taken until the prediction changes to taken?

For the next questions load the “mips_bp2” architecture in the SIM-PL executer.

Answer the next questions:

9. See question 6.
10. See question 7.
11. See question 8

For this lab you have to hand in the following:

  • The source code of the programs for questions 1 and 2
  • The report with the answers to the questions (pdf format)
  • The source code of the programs you wrote as experiments for questions 6 through 11.

Source filenames must be conform <labname>-<exercisenumber><YourName>.wasm or sal.

Reports filenames must be conform <Labname>-<YourCompleteName>.pdf