Computer Architecture Assesment 3

What is one of the simplest (and oldest) techniques for exploiting parallelism among instructions?

pipelining

Which is on average less effective, dynamic or static branch prediction?

static

When dealing with control hazards, it is not enough to predict whether or not the branch is taken - what else must we know?

branch target address

What is the definition of a precise interrupt? (Not the one from the book, the one from class)

complete all instructions before, squash all afterwards

What is a BTB, and what does it do?

Branch target buffer

a table of addresses corresponding to branch location

What is a BTC, and what does it do?

Branch Target Cache

contains target PC

What three things do you need to know in order to appropriately service an interrupt? (Hint - the description of each starts with the letter "W")

What happened, where it happened, where to go

What are the 3 pipeline hazards? Which one can be eliminated by providing more resources?

structural, data, control; structural

What are the 3 pipeline hazards? Which one can be dealt with by using prediction?

structural, data, control; control

We talked in class about the need to be able to disable interrupts, at least temporarily. Why is this so important? What will happen if you cannot disable interrupts?

If we are unable to disable interrupts, we would go back to the same interrupt, resulting in an infinite loop.

There is a constraint when doing branch prediction that keeps more accurate advanced techniques (using artificial intelligence, for example) from being incorporated in actual designs. What is the constraint? (What is the problem, in other words?)

AI takes a long time, we do not have enough time in a balanced pipeline

Branch prediction requires the ability to squash (or undo) instructions. How do you "squash" an instruction in a pipelined machine? (What must be prevented from happening?)

prevent it from changing the state of the machine

Why do most pipelined machines avoid the use of condition codes?

condition codes are part of the state, so changing the state at multiple stages makes squashing instructions difficult

List two Static Branch Prediction schemes

predict taken

predict not taken

What is a predicated instruction? Why is it useful?

an instruction that is executed but conditionally written based on the results of something else

it is useful because branch doesn’t have to be done/table not filled so it reduces the number of conflicts in branch table

Intel uses a Tournament predictor in some of their processors. Describe what a tournament predictor is, and why it is used. Your description can (and probably should) include sketches/drawings, and an explanation of why a single predictor is not enough.

A tournament predictor is when a meta tracks 2 predictors, 2 bit and G share. 2 bit quickly picks up a patters (learns quick) while G share is reactive, and struggles when the program jumps to a new place (learns better)

In your first design of a 5-stage pipeline (F,D,E,M,W), F takes 29 time units, D takes 32, E takes 66, M takes 31, and W takes 28.

a) What will the clock cycle time be for this pipeline?

b) Is it a balanced pipeline? If not, explain what you could do to fix it. What would the cycle time be now?

a) 66

b) No, split E into E1 and E2. 33

Indirect branches are a problem for branch predictors.

a) Why are they a problem?

b) What hardware structure can be used to help with the most common form of indirect branches?

a) Indirect branches do not have a branch target address.

b) The most common form of indirect branches are returns from subroutines which can be helped by the return address stack.

The standard MIPS implementation has a 5-stage pipeline, writes to the register file during the first half of the D cycle and reads during the second half. If the machine is redesigned to be a 6-stage pipeline, with the following stages:

F D E M1 M2 WB

a) Assuming this machine has a branch predictor and the branch condition is calculated by the end of the E stage, how big is the branch penalty (measured in cycles) when the prediction is incorrect? What if the branch condition is calculated by the end of D?

b) How many load delay stalls would this machine need (assuming it has forwarding logic and you are forwarding to E) if the memory returns the value by the end of M2? M1?

a) 2, 1

b) 2, 1

There are two ways to deal with interrupts. What are they?

Vectored interrupts

Cause Registers

Compilers have trouble scheduling code that involves reads and writes to memory. Why?

There could be a hazard through the memory system, which happens a lw or a sw unknowingly uses the same address since the compiler does not know what value the register is.

Once the trap handler has begun, what two things does it need to know in order to deal with an interrupt?

The cause of the interrupt and the program state at the time of the interrupt

Why is there a desire to create larger basic blocks? Give one example of a way to create a bigger basic block.

More code can be scheduled with a larger basic block leading to a faster program; loop unrolling

Supporting precise interrupts in a machine that allows out of order completion is a challenge. Why do we care? Why is it important to support precise interrupts?

Virtual Memory, which is practically on every machine nowadays, has a lot of instructions that need to be resumed because memory contents are dynamically challenging

If a pipeline were modified to support out of order completion, what new data hazard would be introduced?

WAW

If a pipeline were modified to support out of order issue, what new data hazard would be introduced?

WAR

What are two types of dynamic branch prediction?

1-bit global counter

2-bit global counter

Branch History

What is a BHT, and what does it do?

Branch History Table (2 level branch predictor where some subset of the pc accesses a table containing 2 bit counters of how the branch performed)

What is a Branch History Register?

a shift register, sequence of branch taken/ not taken as 0s and 1s. (also known as correlating predictor)

What is a Gshare?

XOR the instruction address (PC) and the Branch History register and store it into the Branch Predict/History Table

What is one upside and one downside of the Branch History Table?

upside: accuracy levels are really high, close to 99%

downside: if the table is too small, lots of collisions, if the table is big enough, the size of the table grows wayy too high

What is a vectored interrupt?

table accessed by the type of interrupt (know what happened and where to go)

What is a cause register?

contains “what happened”

What is an os call

when a user wants to access something done that only os can do

How to disable interrupt?

make it part of the interrupt (load pc, disable interrupts)

What is a user maskable interrupt

can be temporarily ignored