Problem $8$

A five instruction sequence executes according to Tomasulo's algorithm. Each instruction is of the form ADD DR$,$SR$1,$SR$2$ or MUL DR$,$SR$1,$SR$2.$ ADDs are pipelined and take $9$ cycles $($F$-$D$-$E$1-$E$2-$E$3-$E$4-$E$5-$E$6-$WB$).$ MULs are also pipelined and take $11$ cycles $($two extra execute stages$).$ The microengine must wait until a result is in a register before it sources it $($reads it as a source operand$)$

The register file before and after the sequence are shown below $($tags for "After" are ignored$).$

Before

After

$\backslash$table$[[,$V$,$tag,value$],[$R$0,1,$z$,4],[$R$1,1,$z$,5],[$R$2,1,$z$,6],[$R$3,1,$z$,7],[$R$4,1,$z$,8],[$R$5,1,$z$,9],[$R$6,1,$z$,10],[$R$7,1,$z$,11]]$

$\backslash$table$[[,$V$,$tag,value$],[$R$0,1,,310],[$R$1,1,,5],[$R$2,1,,410],[$R$3,1,,31],[$R$4,1,,8],[$R$5,1,,9],[$R$6,1,,10],[$R$7,1,,21]]$

Complete the five instruction sequence in program order in the space below. Note that we have helped you by giving you the opcode and two source operand addresses for instruction $4.($The program sequence is unique.$)$

$\backslash$table$[[1],[2],[,,],[4,$MUL,, R$6,$ R$6],[5,,]]$

In cycle $1$ instruction $1$ is fetched. In cycle $2,$ instruction $1$ is decoded and instruction $2$ is fetched. In cycle $3,$ instruction $1$ starts execution, instruction $2$ is decoded, and instruction $3$ is fetched.

Assume the reservation stations are all initially empty. Put each instruction into the next available reservation station. For example, the first ADD goes into $"a".$ The first MUL goes into $"x".$ Instructions remain in the reservation stations until they are completed. Show the state of the reservation stations at the end of cycle $8.$

Note: to make it easier for the grader, when allocating source registers to reservation statinno ninace olusove houn tha hinhar numbarad manictar ha acoinnod tn CD$?$

$3.$ Show the state of the Register Alias Table $($ V $,$ tag, Value$)$ at the end of cycle $8.$

$\backslash$table$[[,$V$,$tag,value$],[$R$0,,,],[$R$1,,,],[$R$2,,,],[$R$3,,,],[$R$4,,,],[$R$5,,,],[$R$6,,,],[$R$7,,,]]$