Instruction Pipelining

Question 1

what are the basic ideas of instruction pipelining

Answer 1

1. split instructions into independent stages
2. execute stages concurrently

Question 2

what are the limiting factors of instruction pipeling

Answer 2

1. execution time longer than fetch time
2. branches may invalidate fetched operations

Question 3

what are the 6 steps of a realistic pipeline

Answer 3

1. FI = fetch instruction
2. DI = decode instruction
3. CO = calculate operations
4. FO = fetch operands
5. EI = execute instructions
6. WO = write operands

Question 4

draw a timing diagram for a simple programme using a realistic pipeline

Question 5

what are the realistic assumptions that break down the ‘realistic pipeline’

Answer 5

• not all instructions require all 6 pipeline stages
• not all stages can be performed in parallel
• not all stages have equal duration
• interrupts may invalidate the pipeline
• branching may invalidate the pipeline

Question 6

what are 3 things that can affect pipeline performance

Answer 6

1. cycle time
2. total pipeline time
3. speedup

Question 7

what is the formula of the cycle time

Answer 7

T = max ti + d = Tm + d
where:
- ti = time delay of ith pipeline stage
- k = number of pipeline stages
- d = delay of a latch
- Tm = maximum stage delay

Question 8

total pipeline time formula

Answer 8

Tk, n = (k + n - 1).t
where:
- Tk,n = execution time of n instructions in k-stage pipeline
- t = cycle time
- k = number of pipeline stages
- n = number of instructions

Question 9

speedup formula

Answer 9

Sk = T1,n/Tk,n
= n.k.t/(k + n - 1).t
= n.k/(k + n - 1)

Question 10

what is the limit of speedup

Answer 10

lim Sk = lim (n.k/k + n - 1) = k

Question 11

what are pipeline hazards

Answer 11

the pipeline must stall because conditions do not permit continued execution

Question 12

what are the 3 main pipeline hazards

Answer 12

1. resource
2. data
3. control

Question 13

what is a resource hazards

Answer 13

2 instructions in the same pipeline need the same resources
- instruction 1 must source operands, so instruction 3 cannot be fetched when there is only one memory

Question 14

what is a data hazard

Answer 14

2 instructions in the pipepline access the same memory location

Question 15

what are the 3 data hazards

Answer 15

1. RAW - read after write
2. WAR - write after read
3. WAW - write after write

Question 16

what is a read after write data hazard

Answer 16

read takes place before preceding write is complete

Question 17

what is a write after read data hazard

Answer 17

write operation completes before read has taken place

Question 18

what is a write after write data hazard

Answer 18

2 writes happen in the wrong order

Question 19

what is a control hazard

Answer 19

wrong branch is taken in the pipeline

Question 20

what is the most serious data hazard

Answer 20

control - pipeline must be completely flushed

Question 21

what are some solutions to control hazards

Answer 21

• multiple pipelines for branches
• prefetch branch target
• instruction buffer (loop buffer)
• branch prediction - static or dynamic
• reordering of branches

Question 22

what are some static approaches of branch prediction

Answer 22

• ‘always taken’
• ‘never taken’
• predict by opcode

Question 23

what are some dynamic approaches of branch prediction

Answer 23

• ‘taken/not taken’ switch
• branch-history table