Skip to content
GATETECH
Official PYQ · 2013Q45Instruction PipeliningMCQ1 mark

GATE CS 2013 Q45 — Instruction Pipelining

Explain with AI

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 5 ns, 7 ns, 10 ns, 8 ns and 6 ns,\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 ns.1\ \text{ns}. A program consisting of 1212 instructions I1, I2, I3,…, I12\text{I1, I2, I3,}\ldots,\text{ I12} is executed in this pipelined processor. Instruction I4\text{I4} is the only branch instruction and its branch target is I9.\text{I9}. If the branch is taken during the execution of this program, the time (in ns) needed to complete the program is

Choose one option
View worked solution

Answer: B

To find the total execution time, we first determine the clock cycle time (TpT_p) of the pipeline:

Tp=max⁡(Stage Delays)+Buffer Delay=max⁡(5,7,10,8,6)+1=11 nsT_p = \max(\text{Stage Delays}) + \text{Buffer Delay} = \max(5, 7, 10, 8, 6) + 1 = 11\text{ ns}

Next, we identify the sequence of instructions that successfully complete execution. Since the branch at I4\text{I4} is taken to I9\text{I9}, the completed instructions are:

I1, I2, I3, I4, I9, I10, I11, I12(Total N=8 instructions)\text{I1, I2, I3, I4, I9, I10, I11, I12} \quad (\text{Total } N = 8 \text{ instructions})

Since there is no branch prediction, instructions I5, I6,\text{I5, I6,} and I7\text{I7} are speculatively fetched. The branch outcome and target address are resolved at the end of the 4th stage, i.e., the Execute Instruction (EI) stage. This introduces a branch penalty of 4−1=34 - 1 = 3 stall cycles to flush the incorrect instructions.

The total number of clock cycles required for a kk-stage pipeline to execute NN instructions with SS stall cycles is:

Total Cycles=(k+N−1)+S=(5+8−1)+3=15 cycles\text{Total Cycles} = (k + N - 1) + S = (5 + 8 - 1) + 3 = 15\text{ cycles}

Thus, the total execution time is:

Total Time=15×11 ns=165 ns\text{Total Time} = 15 \times 11\text{ ns} = 165\text{ ns}

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Instruction Pipelining questions