6.823 Problem Set 5

Chris Laas

April 24, 2000

Problem 5-1

(a) Jz-Jump Rule

Proc(nextPc, pc, rf, im) if im[pc] = Jz(r_{c}, r_{a}) and rf[r_{c}] = 0

→ Proc(rf[r_{a}], nextPc, rf, im)

Op Rule

Proc(nextPc, pc, rf, im) if im[pc] = r := Op(r_{1}, r_{2})

→ Proc(nextPc + 1, nextPc, rf[r := v, im]) where v = \underline{Op}(rf[r_{1}], rf[r_{2}])

(b) Jz-Jump Rule, non-empty bsE

Proc(pc, rf, bsD, Itb(ia_{J}, r := Jz(0, npc)); Itb(ia_{E}, insn_{E}); bsE, bsM, bsW, im)

→ Proc(npc, rf, ε, Itb(ia_{E}, insn_{E}), bsM, bsW, im)

Jz-Jump Rule, empty bsE

Proc(pc, rf, Itb(ia_{D}, insn_{D}); bsD, Itb(ia_{J}, r := Jz(0, npc)), bsM, bsW, im)

→ Proc(npc, rf, Itb(ia_{D}, insn_{D}), ε, bsM, bsW, im)

(c) If both bsD and bsE are empty, i.e. the pipeline behind the Jz is empty, then the processor still won’t stall, because the fetch rule will fetch an instruction, causing bsD to become non-empty, causing the second of the above rules to fire.

(d) The state given doesn’t give us a reasonable way to signify the validity of jumpPc: instructions need some way of telling whether they should jump to jumpPc. Here, I simply use the symbol ε to signify “no jump”; it would be more explicit to use a separate jumpPc-valid-bit, which is equivalent. Jz-Jump Rule

Proc(pc, rf, bsD, Itb(ia_{J}, r := Jz(0, npc)); bsE, jumpPc, bsM, bsW, im)

→ Proc(pc, rf, bsD, bsE, npc, bsM, bsW, im)

Op-Execute Rule, with Jump

Proc(pc, rf, bsD, Itb(ia, r := Op(v_{1}, v_{2})); bsE, jumpPc, bsM, bsW, im)

→ Proc(jumpPc, rf, bsD, bsE, ε, bsM; Itb(ia, r := v), bsW, im) where v = Op(v_{1}, v_{2})

Op-Execute Rule, no Jump

Proc(pc, rf, bsD, Itb(ia, r := Op(v_{1}, v_{2})); bsE, ε, bsM, bsW, im)

→ Proc(pc, rf, bsD, bsE, ε, bsM; Itb(ia, r := v), bsW, im) where v = Op(v_{1}, v_{2})

Problem 5-2

(a) In general, the BTB performs a very simple prediction heuristic; then, when the BHT is used to refine the prediction by looking at the branch history, the BTB’s prediction might be overruled. Then, finally, the execute stage either confirms the branch prediction or nullifies it, killing everything in the prediction pipeline as well. UpdateBTB and UpdateBHT are only used in the execute stage. UpdateBTB(btb, pc, ppc, Taken/NotTaken) updates the BTB by putting the entry < pc, ppc, Valid > in slot pc[r-1:0] if Taken, or by putting the entry < pc, −, NotValid > in slot pc[r-1:0] if NotTaken and the slot currently has pc as its tag. UpdateBHT(bht, pc, p, Taken/NotTaken) updates entry pc[s-1:0] in the usual way, based on the old value p and the jump result Taken/NotTaken. If the BTB is hit, then the predicted next PC goes into PC and into bsPC. BTB Hit Rule

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if v = Valid and pc = entryPC where ⟨entryPC, targetPC, v⟩ = btb[pc[r − 1 : 0]]

→ Proc(targetPC, btb, enq(⟨pc, targetPC⟩, bsPC), imem, bht, bsI, rf)

If, upon fetch, the BHT agrees with the BTB that the branch will be Taken or NotTaken, then the pipeline is undisturbed. Fetch Rule for BZ, BHT Agrees with BTB on Taken

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if imem[ipc] = BZ(r_{c}, offset) and (p = WT or p = ST) and ipc + offset = ippc where ⟨ipc, ippc⟩ = first(bsPC) and p = bht[ipc[s − 1 : 0]]

→ Proc(pc, btb, deq(bsPC), imem, bht, enq(⟨ipc, ippc, p, BZ(r_{c}, offset)⟩, bsI), rf)

Fetch Rule for BZ, BHT Agrees with BTB on NotTaken

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if imem[ipc] = BZ(r_{c}, offset) and (p = WNT or p = SNT) and ipc + 1 = ippc where ⟨ipc, ippc⟩ = first(bsPC) and p = bht[ipc[s − 1 : 0]]

→ Proc(pc, btb, deq(bsPC), imem, bht, enq(⟨ipc, ippc, p, BZ(r_{c}, offset)⟩, bsI), rf)

If, on the other hand, the BHT disagrees with the BTB’s prediction (or if, for some unusual reason, the BTB predicts neither ipc+1 nor ipc+offset), the PC pipeline before the BTB is flushed (killing one potential instruction), the PC is reset to what the BHT thinks it should be, and the branch is passed on to the execute unit. Fetch Rule for BZ, BHT says Taken but BTB doesn’t

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if imem[ipc] = BZ(r_{c}, offset) and (p = WT or p = ST) and ipc + offset ≠ ippc where ⟨ipc, ippc⟩ = first(bsPC) and p = bht[ipc[s − 1 : 0]]

→ Proc(ipc + offset, btb, clear(bsPC), imem, bht, enq(⟨ipc, ippc, p, BZ(r_{c}, offset)⟩, bsI), rf)

Fetch Rule for BZ, BHT says NotTaken but BTB says Taken

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if imem[ipc] = BZ(r_{c}, offset) and (p = WNT or p = SNT) and ipc + 1 ≠ ippc where ⟨ipc, ippc⟩ = first(bsPC) and p = bht[ipc[s − 1 : 0]]

→ Proc(ipc + 1, btb, clear(bsPC), imem, bht, enq(⟨ipc, ippc, p, BZ(r_{c}, offset)⟩, bsI), rf)

There needs also be a fetch rule for Ops.

Fetch Rule for Op

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if imem[ipc] = Op(r_{d}, r_{1}, r_{2}) where ⟨ipc, ippc⟩ = first(bsPC)

→ Proc(pc, btb, deq(bsPC), imem, bht, enq(⟨ipc, ippc, SNT, Op(r_{d}, r_{1}, r_{2})⟩, bsI), rf)

In case we do jump and the prediction was good, we merely update the prediction tables to reflect that.

BZ-Jump Execute Rule, Good Predict

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if inst = BZ(r_{c}, offset) and rf[r_{c}] = 0 and ipc + offset = ippc where ⟨ipc, ippc, ip, inst⟩ = first(bsI)

→ Proc(pc, UpdateBTB(btb, ipc, ippc, Taken), bsPC, imem,

UpdateBHT(bht, ipc, ip, Taken), deq(bsI), rf) If we jump but that wasn’t predicted correctly, kill the queued instructions and PCs, jump, and update the tables.

BZ-Jump Execute Rule, Mispredict

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if inst = BZ(r_{c}, offset) and rf[r_{c}] = 0 and ipc + offset ≠ ippc where ⟨ipc, ippc, ip, inst⟩ = first(bsI)

→ Proc(ipc + offset, UpdateBTB(btb, ipc, ippc, Taken), clear(bsPC), imem,

UpdateBHT(bht, ipc, ip, Taken), clear(bsI), rf) If we don’t jump and the prediction was good, we merely update the prediction tables to reflect that.

BZ-No-Jump Execute Rule, Good Predict

Proc(pc, btb, bsPC, imem, bht, bsI, rf) if inst = BZ(r_{c}, offset) and rf[r_{c}] ≠ 0 and ipc + 1 = ippc where ⟨ipc, ippc, ip, inst⟩ = first(bsI)

→ Proc(pc, UpdateBTB(btb, ipc, ippc, NotTaken), bsPC, imem,

UpdateBHT(bht, ipc, ip, NotTaken), deq(bsI), rf) If we don’t jump but that wasn’t predicted correctly, kill the queued instructions and PCs, change the PC to undo the jump, and update the tables.

BZ-No-Jump Execute Rule, Mispredict Proc(pc, btb, bsPC, imem, bht, bsI, rf)

if inst = BZ(r_{c}, offset) and rf[r_{c}] ≠ 0 and ipc + 1 ≠ ippc where ⟨ipc, ippc, ip, inst⟩ = first(bsI)

→ Proc(ipc + 1, UpdateBTB(btb, ipc, ippc, NotTaken), clear(bsPC), imem,

UpdateBHT(bht, ipc, ip, NotTaken), clear(bsI), rf)

(b) This is an improvement over a BTB alone, because the BHT stage (which comes pretty much for free, since it’s in parallel with the IMEM lookup) can prevent certain (previously) pessimal branching patterns from hosing the branch prediction.

On the other hand, it is also an improvement over a BHT alone, because if there were no BTB, the branch predictor would have to wait on the IMEM lookup to determine the branch target to feed to the PC when the BHT speculates Taken.

(c) We could easily move the BHT into the earlier stage, as the only input to the BHT is the PC. This might actually improve performance, as one PC wouldn’t need to be killed when a BTB Taken prediction is overruled by a BHT NotTaken prediction.

(d) Moving the BTB to the later stage (containing the IMEM) would completely defeat its purpose, which is to provide the branch target before it is available from the IMEM.

(e) We don’t know for certain whether the branch is taken until the Execute stage, which is the last stage in this pipeline.

Problem 5-3

(a) The problem here is that, when the memory returns its data response < t, v >, the dispatched Load that initiated the query will no longer exist if the ROB has been rolled back, and thus the Load-Retire rule will not be able to fire, and thus the MPB buffer will not be able to advance, leading to deadlock. Possibly even worse, there might be a different Load instruction using the tag t in the ROB by then, and it would incorrectly be given the value v returned by the memory in response to the speculative query. This second possibility would lead to corruption.

A simple solution would be to, before rolling back the ROB, first wait for the memory to finish responding to all dispatched speculative loads.

A more complicated solution would be to attempt to pluck out the speculative queries from the PMB. A much more complicated solution would be to try to keep track of the tags associated with outstanding speculative queries (so as not to reuse them in the ROB and to be able to accept responses from the MPB). These solutions would require much more complicated circuitry and TRS’s, and are probably not worth the effort.

(b) Assume the Load-Dispatch rule has been changed by substituting “U ∉ rob_{1}” for “U, Jz ∉ rob_{1}”. The rules for completion of incorrectly-speculated branches must be modified to allow for the simple solution I describe above, by not firing until there are no dispatched speculative loads left in the ROB. In the following rules,

btb′ = updateBTB(btb, ia, npc, taken/nottaken)

Ps-Jz-Jump-WrongSpec Rule

Proc(pc, rf, rob_{1}; Itb(ia, Jz(0, npc), Sp(ppc)); rob_{2}, btb, im)

if ppc ≠ npc and D ∉ rob_{2}

→ Proc(pc, rf, rob_{1}, btb′, im)

Ps-Jz-NoJump-WrongSpec Rule

Proc(pc, rf, rob_{1}; Itb(ia, Jz(v, −), Sp(ppc)); rob_{2}, btb, im)

if v ≠ 0 and ppc ≠ ia + 1 and D ∉ rob_{2}

→ Proc(pc, rf, rob_{1}, btb′, im)

Additionally, if one assumes that the memory subsystem processes the PMB and the MPB atomically, and that any given memory request is either in the PMB or the MPB at any point (i.e the memory system does not keep requests hidden inside itself ever), then we can pluck the speculative loads out of the PMB. This allows us to remove the corresponding loads from the ROB, allowing the above branch completion rules to fire sooner. In terms of real circuitry, this might make the implementation of PMB much more complicated, and might not be playing fair with the memory subsystem (which might expect the PMB and MPB to be FIFO queues which the processor can’t touch); nevertheless, the TRS rules to do this follow. (These new rules are in addition to the two modified rules above.)

Ps-Jz-Jump-WrongSpec-PluckPMB Rule

Sys(Proc(pc, rf, rob_{1}; itb_{J}; rob_{2}; itb_{L}; rob_{3}, btb, im), pmb_{1}; ⟨t, Load(a)⟩; pmb_{2}, mpb)

if itb_{J} = Itb(ia, Jz(0, npc), Sp(ppc)) and ppc ≠ npc and itb_{L} = Itb(ia, t := Load(a, D), Wr(r))

→ Sys(Proc(pc, rf, rob_{1}; itb_{J}; rob_{2}; rob_{3}, btb, im), pmb_{1}; pmb_{2}, mpb)

Ps-Jz-NoJump-WrongSpec-PluckPMB Rule

Sys(Proc(pc, rf, rob_{1}; itb_{J}; rob_{2}; itb_{L}; rob_{3}, btb, im), pmb_{1}; ⟨t, Load(a)⟩; pmb_{2}, mpb)

if itb_{J} = Itb(ia, Jz(v, −), Sp(ppc)) and v ≠ 0 and ppc ≠ ia + 1

and itb_{L} = Itb(ia, t := Load(a, D), Wr(r))

→ Sys(Proc(pc, rf, rob_{1}; itb_{J}; rob_{2}; rob_{3}, btb, im), pmb_{1}; pmb_{2}, mpb)

Problem 5-4

(a) A Fence instruction can be fetched just like any normal instruction; it is its mere presence in the ROB that affects the memory dispatch order. The template for a Fence instruction is Itb(pc, Fence, -).

Ps-Fence-Fetch Rule

Proc(pc, rf, rob, btb, im) if im[pc] = Fence

→ Proc(pc + 1, rf, rob; Itb(pc, Fence, −), btb, im)

(b) In these memory access rules, the current state is Sys(Proc(ia, rf, rob_{1}; irb; rob_{2}, btb, im), pmb, mpb). The only change from the standard version is the replacement of “Fence,Jz ∉ rob_{1}” for “U,Jz ∉ rob_{1}” in the predicates for dispatching.

Rule Name itb  pmb Next itb  Next pmb
Load-Dispatch Itb(ia_{1}, t:=Load(a,U),Wr(r)) pmb Itb(ia_{1}, t:=Load(a,D),Wr(r)) pmb;⟨t,Load(a)⟩
Fence,Jz ∉ rob_{1}
Store-Dispatch Itb(ia_{1}, t:=Store(a,v,U)) pmb Itb(ia_{1}, t:=Store(a,v,D)) pmb;⟨t,Store(a,v)⟩
Fence,Jz ∉ rob_{1}

(c) A Fence instruction can be retired only after all loads and stores coming before it in program order have been retired.

Ps-Fence-Retire Rule

Proc(pc, rf, rob_{1}; Itb(ia, Fence, −); rob_{2}, btb, im) if Load, Store ∉ rob_{1}

→ Proc(pc, rf, rob_{1}; rob_{2}, btb, im)