Consider an instruction pipeline with five stages without any branch prediction:
Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) and Write Operand (WO). The stage delays for FI, DI, FO, EI and WO are $\text{5 ns, 7 ns, 10 ns, 8 ns and 6 ns},$ respectively. There are intermediate storage buffers after each stage and the delay of each buffer is $1\ \text{ns}.$ A program consisting of $12$ instructions $\text{I1, I2, I3,}\ldots,\text{ I12}$ is executed in this pipelined processor. Instruction $\text{I4}$ is the only branch instruction and its branch target is $\text{I9}.$ If the branch is taken during the execution of this program, the time (in ns) needed to complete the program is
There are intermediate storage buffers after each stage and the delay of each buffer is 1 ns.
What is the significance of this statement in given problem?
Where are we using this information?
Hi @Arjun Sir, First of all thanks for sharing following example -->
JZ LOOP ADD X, Y Here we can know whether we have to do a Jump or not only after the Execute stage of the JZ (Jump on Zero) instruction. Similar is the case for any conditional branch instruction.
JZ LOOP ADD X, Y
Here we can know whether we have to do a Jump or not only after the Execute stage of the JZ (Jump on Zero) instruction. Similar is the case for any conditional branch instruction.
Good point but in case of unconditional branch i think till ID phase decision could be taken. Please correct me if i am wrong.
Chhotu yes in case of unconditional branch by decoding itself we can take decision IFF the operand fetch phase is merged with the decode phase then we can directly get the location (target ) by decode phase itself hence once this decode phase is done we can flush the pipleline and restart from I9
Why Instruction I8 is not considered in Instruction cycle ? The question should not mention so Please clear in topics Very deep. @Arjun Sir
@Ritik Jain RJ because it is the best case, that we come to know about branch decision in EX stage
@Abhrajyoti00 bro we are starting I9 after EI because it is clearly mentioned in question that we have to branch during the execution of the program .
@abir_banerjee That’s not exactly correct. The meaning of that sentence is we have a conditional branch instruction like “Jump on Carry” and the condition is true during the execution of the program and thus the branch is taken.
@Abhrajyoti00 Even without a branch predictor can’t we start I9 as soon as we know it is the branch target? Which pipeline feature facilitates this?
@shashi7893 I have been searching for this for a while did u get any answer to this ?
answer = option B
cycles in pink are stall cycles, at EI-4 it was notified to the system that instruction 9 has to be loaded next. We have completed execution in a total of 15 cycles where each cycle was (10+1)ns long,
Hence, answer = $15 \times 11 = 165$ns
Short Trick :
Branching descion will be taken in Execute Instruction (EI) phase (4th phase) so there will be 3 stalls first I1 will complete in 5 cycles + (I2,I3,I4,3 STALLS,I9,I10,I11,I12) WILL TAKE ONE-ONE CYCLE=15 CYCLE cycle time=(largest cycle time + buffer delay)=10+1=11 Execution time =11*15=165
64.3k questions
77.9k answers
244k comments
80.0k users