Q$16.$ Pipelining $[13$ marks$]$

Refer to the following MIPS code which is the same as the one in question $15.$ Here, we look only at instructions I$1$ to I$19.$ Pay attention to the assumptions $($underlined$)$ given below.

$```$

add $t$0,$ $$0,$ $$0$ # I$1$; i $=0$

addi $t$1,$ $a$1,0$ # I$2$; $t$1=$ &A$[0]$

addi $t$2,$ $a$2,0$ # I$3$; $t$2=$ &B$[0]$

sll $t$3,$ $a$0,2$ # I$4$

loop: slt $t$4,$ $t$0,$ $t$3$ # I$5$

beq $t$4,$ $$0,$ end # I$6$

lw $s$1,0($$t$1)$ # I$7$

lw $s$2,0($$t$2)$ # I$8$

slt $t$4,$ $s$1,$ $s$2$ # I$9$

beq $t$4,$ $$0,$ skip # I$10$

add $t$9,$ $s$1,$ $$0$ # I$11$

add $s$1,$ $s$2,$ $$0$ # I$12$

add $s$2,$ $t$9,$ $$0$ # I$13$

skip: sw $s$1,0($$t$1)$ # I$14$

sw $s$2,0($$t$2)$ # I$15$

addi $t$0,$ $t$0,4$ # I$16$

addi $t$1,$ $t$1,4$ # I$17$

addi $t$2,$ $t$2,8$ # I$18$

j loop # I$19$

end:

$```$

Assuming a $5-$stage MIPS pipeline, and all elements in array $\backslash ($ A $\backslash )$ are smaller than all elements in array $\backslash ($ B $\backslash ),$ answer the parts below. You need to count until the last stage of instruction I$19.$

$($a$)$ How many cycles does this code segment take to complete its execution in the first iteration $($I$1$ to I$19)$ in an ideal pipeline, that is$,$ one with no delays?

For parts $($b$)$ to $($d$)$ below, given the assumption for each part, how many additional cycles does this code segment $($I$1$ to I$19)$ take to complete its execution in the first iteration as compared to an ideal pipeline computed in $($a$)?$ Note that the jump instruction $($j$)$ computes the target address to jump to in its ID stage $($stage $2).$ No delayed branching is used.

Write the total number of additional delay cycles for each of the parts $($b$)$ to $($d$).$ For example, if part $($a$)$ takes $10$ cycles and part $($b$)$ takes $30$ cycles, then you should write $+20$ for part $($b$).$

$($b$)$ Assuming without forwarding and branch decision is made at MEM stage $($stage $4).$ No branch prediction is made.

$($c$)$ Assuming with forwarding and branch decision is made at MEM stage $($stage $4).$ No branch prediction is made.

$($d$)$ Assuming with forwarding and branch decision is made at ID stage $($stage $2).$

Branch is predicted not taken.

$($e$)$ Assuming the setting in part $($b$)$ above $($without forwarding and branch decision at MEM stage$),$ without affecting the correctness of the code, is it possible to move one instruction to somewhere else to reduce the number of delay cycles? If so$,$ indicate which instruction to move, where to move it to$,$ and how many delay cycles are reduced by moving it$.$ If it is not possible, explain.