Branch Prediction question

Question

My question relates to a video I watched on YouTube.

The pipeline is a 5-stage pipeline which include fetch, decode, ALU, Mem (data), and Write.

It mentions that nothing is fetched until we're sure what to fetch. How can that be though? Won't you need to fetch and decode an instruction first to know what to fetch?

He mentions that the ADDI instruction gets fetched, but then goes in a bubble since it's not a branch. I really do not understand what is happening here and why the CPI for each instruction are ADDI=2, ADD=2, and BNEZ=3.

Can any explain to me what's going on here? Maybe a table with cycle iteration would be helpful.

Here's the video link: Branch Prediction question

Answer 1

I figured out what he means: fetch the instruction and decode it, but do not fetch the next instruction until you've determined whether it's a branch or non-branch instruction.

For the non-branch instructions, it will fetch next instruction after the decode stage. But for the branch instruction, it will require an extra cycle to determine it should stay in the loop or not.

The CPI does add up if I do follow through with what I've mentioned. I've added a picture to give you a better picture of what's happening at each cycle.

Answer 2

I think the answer posted is correct in the demonstration of the 7 cycles. On the other hand the processor with the perfect predictor should consume 5 cycles not 3. The reason for that is the dependency between I1 (Add r1,r1,-1) and I3 (bnez r1,loop). This dependency will halt I3 at the fectch stage until I1 passes the write-back stage (final or 5th stage in the pipeline) which causes 2 stale cycles so the speedup should be 7/5 = 1.4 here is a demonstration for my answer using a cycle by cycle pipeline