Skip to content
GATETECH
Official PYQ · 2009Q28Instruction PipeliningMCQ1 mark

GATE CS 2009 Q28 — Instruction Pipelining

Explain with AI

Consider a 44 stage pipeline processor. The number of cycles needed by the four instructions I1,I2,I3,I4I1, I2, I3, I4 in stages S1,S2,S3,S4S1, S2, S3, S4 is shown below:

S1S2S3S4 I12111I21322I32113I41222\begin{array}{|c|c|c|c|c|} \hline \textbf{} & \textbf{S1} &\textbf{S2} & \textbf{S3} & \textbf{S4 } \\ \hline \textbf{I1}& 2 & 1 & 1 & 1 \\ \hline \textbf{I2} & 1 & 3 & 2 & 2\\ \hline \textbf{I3}& 2 & 1 & 1 & 3 \\ \hline \textbf{I4} & 1 & 2 & 2 & 2 \\ \hline \end{array}

 

What is the number of cycles needed to execute the following loop?

For (i=1 to 2) {I1; I2; I3; I4;}

Choose one option
View worked solution

Answer: B

The loop executes the sequence of instructions: I1,I2,I3,I4,I1,I2,I3,I4I_1, I_2, I_3, I_4, I_1, I_2, I_3, I_4 (a total of 8 instructions). Let S(k,j)S(k, j) and E(k,j)E(k, j) denote the start and end times of instruction kk in stage jj.

The scheduling constraints are:

  • An instruction can only enter stage jj after it finishes stage j−1j-1: S(k,j)≥E(k,j−1)S(k, j) \ge E(k, j-1)
  • A stage jj can only process instruction kk after instruction k−1k-1 has cleared it: S(k,j)≥E(k−1,j)S(k, j) \ge E(k-1, j)

Tracing the execution cycle-by-cycle for all 8 instructions:

Inst. Stage S1 (cycles) Stage S2 (cycles) Stage S3 (cycles) Stage S4 (cycles)
I1 [0, 2] [2, 3] [3, 4] [4, 5]
I2 [2, 3] [3, 6] [6, 8] [8, 10]
I3 [3, 5] [6, 7] [8, 9] [10, 13]
I4 [5, 6] [7, 9] [9, 11] [13, 15]
I1 [6, 8] [9, 10] [11, 12] [15, 16]
I2 [8, 9] [10, 13] [13, 15] [16, 18]
I3 [9, 11] [13, 14] [15, 16] [18, 21]
I4 [11, 12] [14, 16] [16, 18] [21, 23]

The final instruction completes stage S4S4 at cycle 23.

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

Published
Report a correction
Keep exploringMore Instruction Pipelining questions