Lectures 3 and 4 - Pipelining

Question 0

Hazard Classes

Answer 0

Structural Hazards - arise from resource conflicts

Data Hazards - Arise from inter-instruction dependencies

Control Hazards - Cause by instructions that change the program counter

Question 1

Pipeline hazards

Answer 1

Situations that arise that force the pipeline to stall.

Question 2

Data dependencies

Answer 2

Real - If j uses the result of i then it is data dependent on i. They are also dependent if there is a chain of dependencies.

Name - simply a result of register reuse with no data actually communicated.

Question 3

Data Hazard

Answer 3

Created whenever the parallel execution of instructions makes it possible for a dependency to be violated.

Question 4

Methods for Avoiding Data Hazards

Answer 4

Add hardware to avoid hazard such as data forwarding or bypass paths

Transform or schedule the code in order to prevent a data dependence becoming a data hazard, this could be done by inserting independent instructions to separate dependent instructions that would cause a stall. It can be performed by the compiler or by hardware.

Hazards arising from name dependencies can be avoided by renaming either in compiler or hardware.

Question 5

Load-use Data Hazard

Answer 5

ALU operation must wait for result from load, it cannot execute in same lock cycle even with forwarding.

Cukd insert independent instructions or do nothing instructions in load-delay slot.

Alternatively hardware could detect hazard and stall pipeline

Question 6

Control Hazards

Answer 6

Branch instructions may or may not change the value of the PC so how do we know what to do after we fetch a branch. Simplest approach is to just stall until outcome of branch is known.

Question 7

Precise Exceptions

Answer 7

A processor is said to support precise exceptions if it can guarantee all instructions prior to the faulting instruction have executed and all those prior to it have not begun to execute.

Question 8

Method of handling exceptions

Answer 8

Tag instruction if it causes an exception.

Deal with exception when instruction reaches the write back stage.

Faulting instructions are prevented from updating state. They’re handled at WB stage to ensure they’re handle in order. We save the program counter of the faulting instruction and use it to restart the program after the exception handler had completed.
Flush remaining instructions from pipeline.

Question 9

Alternative approaches to exception handling

Answer 9

Settle for imprecise exceptions.

Use special hardware for handling exceptions which doesn’t require flushing but just stalling while dedicated hardware deals with exception.

Question 10

Limits of pipelining

Answer 10

Difficult to achieve linear performance gains with deeper pipelines because:

• pipelining registers introduce overheads and it is difficult to provide low-skew global clock within a reasonable power budget
• adding stages may increase complexity
• must balance logic in each stage
• number of stalls due to pipeline hazards grow

Question 11

Optimal Pipeline Depth

Answer 11

Throughout = 1/(1+(s-1)b) x 1/(t/s+c)

Then can differentiate to get ideal pipeline length ends up being approximately 23 stages.

Question 12

Condition codes or flags

Answer 12

Branches test special flags set by ALU operations. These usually include zero, carry, negative and overflow.

CCs may constrain instruction ordering.

Question 13

Condition Registers

Answer 13

Perform comparison and place condition codes in general purpose registers. This permits a simple implementation but costs the use of a register.

Question 14

Compare and branch

Answer 14

Performs compare and branch in single instruction. This however potentially complicates pipelining.

Question 15

Predict-not-taken scheme

Answer 15

Assume branch won’t be taken and continue fetching instructions. This means the penalty for intakes branches is now zero.

Question 16

Evaluate branch earlier in pipeline.

Answer 16

Move branch test to decode stage.

Add an additional adder to calculate new pc in decode stage.

The branch penalty is now reduced to 1 cycle.

This requires a simple to evaluate branch condition. The tested condition must be ready during instruction decode. A data hazard is introduced if an instruction that sets the condition is followed by a branch.

Question 17

Delayed Branch

Answer 17

Assume instruction after branch is always executed regardless of the branch condition. This slot is then filled with independent instruction by the compiler if one exists otherwise with no-op. The compiler can fill a single branch delay slot around 60-70% of the time.

Question 18

Static branch prediction

Answer 18

Exploits observation that a given branch instruction is likely to be highly biased in one direction. Displacement-based prediction - predict branch taken if target address < program counter. Alternatively have compiler set prediction bit in instruction. If prediction incorrect then cancel branch. It can be improved using information collected during a profiling run.

Question 19

Bi-modal prediction

Answer 19

1-bit:

Store branch outcome
Use state as prediction next time is taken.

2-bit:

Use 2-bit saturating counter which prevents prediction being flipped in case of single misprediction.

Question 20

Local History Predictor

Answer 20

If branch behaviour has a repetitive pattern in its local history this can be used to improve prediction accuracy.

Question 21

Global correlating predictor

Answer 21

Behaviour of branch is often correlated with behaviour of other recent branches so can access a different counter dispensing on behaviour of recent branches. It’s is because an individual branch can be reached along different paths so maintain unique prediction for particular path. History of recent branches is stored in k-bit register.

Question 22

Tournament predictor

Answer 22

For particular branches global or local predictors will be superior so implement both and see which performs best on a per branch basis. This requires local predictor, global predictor and 2-bit saturating counter per branch to decide between them.

Question 23

Limits to ranch prediction

Answer 23

Some branches are unpredictable and will appear random.

Time is needed to train predictor before correct predictions can be made

Limited Size - history and number of predictors

Aliasing/interference -

Negative aliasing - branches map to same entry in table and move counter in opposite directions. There’s also positive/neutral aliasing.

Question 24

Determining branch target

Answer 24

To avoid stalling on branch we need to known the next address to be fetched by end of IF stage. We use a small cache indexed by the PC of recent branches and their most recent target addresses.

Question 25

Return Address Predictors

Answer 25

Procedures and functions may be called from multiple places in th program. Accuracy of branch target stored in BTB may be very low. This can be solve by using a small hardware stack to store these addresses.

Question 26

Avoiding branches

Answer 26

Loop count register - decrement and branch instruction

Predicated execution - execution of all instructions is conditional this transforms control dependency into data dependency but costs opcode bits and nullified instructions in pipeline.

Conditional moves - move if flag/nominated reg is set.