CO-Grand Test 1-Q13

+1 vote

Consider the following instruction sequence for a hypothetical RISC processor.

$T. R_1 \leftarrow R_2+R_3$

$U. R_4 \leftarrow R_5+R_6$

$V. R_5 \leftarrow R_7+R_8$

$W. R_9 \leftarrow R_5+R_1$

$X. R_{10} \leftarrow R_4+R_1$

$Y.R_{11}\leftarrow R_{10}+R_1$

$Z. R_{9} \leftarrow R_1+R_4$

Which of the following is a possible legal execution order for this instruction on an out-of-order processor without register renaming?

$(A) T,U,X,V,W,Z,Y$

$(B) T,U,X,V,Z,W,Y$

$(C) T,V,U,X,W,Y,Z$

$(D) U,T,V,Y,X,W,Z$

edited Jun 26

–1 vote

(A)

$T. R_1 \leftarrow R_2+R_3$

$U. R_4 \leftarrow R_5+R_6$    Here is a dependency between U and X so there must be 2 stall

$X. R_{10} \leftarrow R_4+R_1$

$V. R_5 \leftarrow R_7+R_8$    Here is a dependency between V and W so there must be 2 stall

$W. R_9 \leftarrow R_5+R_1$

$Z. R_{9} \leftarrow R_1+R_4$

$Y.R_{11}\leftarrow R_{10}+R_1$

(B)

$T. R_1 \leftarrow R_2+R_3$

$U. R_4 \leftarrow R_5+R_6$    Here is a dependency between U and X so there must be 2 stall

$X. R_{10} \leftarrow R_4+R_1$

$V. R_5 \leftarrow R_7+R_8$   Dependency between V and W there is one stall

$Z. R_{9} \leftarrow R_1+R_4$

$W. R_9 \leftarrow R_5+R_1$

$Y.R_{11}\leftarrow R_{10}+R_1$

(C)

$T. R_1 \leftarrow R_2+R_3$

$V. R_5 \leftarrow R_7+R_8$  Here is a dependency between V and U so 2 stalls

$U. R_4 \leftarrow R_5+R_6$   Here is a dependency between U and X so 2 stalls

$X. R_{10} \leftarrow R_4+R_1$  Here is a dependency between X and Y so 1 stall

$W. R_9 \leftarrow R_5+R_1$

$Y.R_{11}\leftarrow R_{10}+R_1$

$Z. R_{9} \leftarrow R_1+R_4$

(D)

$U. R_4 \leftarrow R_5+R_6$

$T. R_1 \leftarrow R_2+R_3$   Dependency between T and Y so 1 stall

$V. R_5 \leftarrow R_7+R_8$

$Y.R_{11}\leftarrow R_{10}+R_1$

$X. R_{10} \leftarrow R_4+R_1$

$W. R_9 \leftarrow R_5+R_1$

$Z. R_{9} \leftarrow R_1+R_4$

So from all of them, answer should be D because of less number of stalls

answered Jun 27 by (6,850 points)
selected Jul 2 by gbmentor
Y is not there in test time.
answered Jun 26 by (31,640 points)
Giving marks for all, for ranking, will put the right choice later

Answer is (A) because if we execute the above instructions in the orignal order and order which is given in the options we can clearly see in Option A the results of the registers after the complete execution of the sequence is equal to the result which would have been obtained if we have executed in the original order.

Registers------> R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11
Original sequence R2+R3 R2 R3 R5+R6 R7+R8 R6 R7 R8 R2+R3+R5+R6 R5+R6+R2+R3 2*(R2+R3)+R5+R6
Option A R2+R3 R2 R3 R5+R6 R7+R8 R6 R7 R8 R2+R3+R5+R6 R5+R6+R2+R3 2*(R2+R3)+R5+R6
Option B R2+R3 R2 R3 R5+R6 R7+R8 R6 R7 R8 R2+R3+R7+R8 R5+R6+R2+R3 2*(R2+R3)+R5+R6
Option C R2+R3 R2 R3 R6+R7+R8 R7+R8 R6 R7 R8 R2+R3+R6+R7+R8 R2+R3+R6+R7+R8 2*(R2+R3)+R6+R7+R8
Option D R2+R3 R2 R3 R5+R6 R7+R8 R6 R7 R8 R2+R3+R5+R6 R2+R3+R5+R6 R2+R3+R10

answered Nov 22 by (1,340 points)