$1\mathrm{.}2$ Complete the timeline of the program assuming that you have an always$-$taken branch predictor. Assume that the branch prediction happens

within the ID stage, and the full branch outcome is available in the EX stage. For conciseness, use F$/$D$/$E$/$M$/$W for IF$/$ID$/$EX$/$MEM$/$WB stages in the

table. Also use $"$N$"$ for NOP. In empty rows, add proper instructions from the assembly program and complete the table. Show mispredicted

instructions as well in the table; you need to invalidate those instructions at the right time. $(60$ pts$)$Consider the code snippet given below:

addi x$14,$ x$0,3$

addi x$15,$ x$0,0$

addi x$12,$ x$0,0$

LOOP:

lw x$10,0($x$13)$

lw x$11,4($x$13)$

add x$16,$ x$10,$ x$11$

add x$12,$ x$16,$ x$12$

addi x$13,$ x$13,16$

addi x$15,$ x$15,1$

blt x$15,$ x$14,$ LOOP

$*$ Abbreviations

$-$ IF: Instruction fetch stage

$-$ ID: Instruction decode $/$ register file read stage

$-$ EX: execution

$-$ MEM: Data memory access

$-$ WB: Write back to the register file

$-$ NOP: No operation; a bubble

$*$ Key assumptions

$-$ The write$-$back data in the WB stage is available in the decode stage at the same cycle.

$-$ The processor has forwarding links for data hazard resolution $($EX $->$ ID and MEM $->$ ID$)$

$-$ Forwarded data from the execution$/$memory stage is visible to the decode stage at the same cycle $($i$.$e$.,$ if an instruction receives a forwarded data from EX$/$MEM stage, align the ID stage of the next instruction with the EX$/$MEM stage of the previous instruction$)$

$-$ The processor has a branch predictor $($each problem will specify which predictor we have$)$ and a branch target buffer $($BTB$).$

$-$ We need to compute the full branch outcome at least once to have the target address in the branch target buffer.

$-$ When "NOP" exists in a pipeline stage, the next instruction cannot complete the previous stage. For example, in the timeline given below, instruction B cannot start IF until the NOP in ID stage of instruction A is removed. Likewise, Instruction C needs to wait until the NOP in the ID stage caused by instruction B is removed $($that$\text{'}$s why IF for instruction C started at cycle $6,$ not $5).$

$1\mathrm{.}1$ Write a $C$ code that performs the same job as the given assembly program.

The assembly program implements the highlighted part in the following $C$ code

snippet. $(20$ pts$)$

$($hint: the program includes a loop$)$