Assignment $2$: Processors, Pipelines, and Instruction Representation

$15$ points $+3$ bonus

Task $1$: Pipelined Architecture

Assume you are programming in assembly on a $16-$bit architecture which employs a five$-$stage pipeline for instruction execution. The five stages are:

$(1)$ fetch next instruction

$(2)$ decode instruction and fetch operands

$(3)$ perform ALU operation

$(4)$ read or write to memory

$(5)$ store result in register

Your architecture has $8$ general purpose registers split into two banks with r$0-$r$3$ on bank $1$ and $\backslash (\backslash$mathrm$\{$r$4\}-\backslash$mathrm$\{$r$\}7\backslash )$ on baink $2.$ The following instructions are implemented:

load loads an immediate value into a register $\backslash ($ r$\_\{$b$\}\backslash )(\backslash ($ r$\_\{$e$\}\backslash )$ and the immediate value offset are provided as arguments$)$

mov moves a value from a register $\backslash ($ r$\_\{$a$\}\backslash )$ to a register $\backslash ($ r$\_\{$b$\}\backslash$left$($r$\_\{$b$\}=$r$\_\{$a$\}\backslash$right$)\backslash )$

add adds the value in register $\backslash ($ r$\_\{$a$\}\backslash )$ to the value in register $\backslash ($ r$\_\{$b$\}\backslash )$ and stores the result in register $\backslash ($ r$\_\{$b$\}\backslash$left$($r$\_\{$b$\}=$r$\_\{$a$\}\backslash$right$.\backslash )\backslash (+\backslash$mathrm$\{$r$\}\_\{\backslash$mathrm$\{$b$\}\}\backslash ))$

sub subtracts the value in register $\backslash ($ r$\_\{$b$\}\backslash )$ from the value in register $\backslash ($ r$\_\{$a$\}\backslash )$ and stores the result in register $\backslash ($ r$\_\{$b$\}\backslash ),\backslash (\backslash$left$($r$\_\{$b$\}=$r$\_\{$a$\}-$r$\_\{$b$\}\backslash$right$)\backslash )$

emp compares the value of registers $\backslash ($ r$\_\{$a$\}\backslash )$ and $\backslash ($ r$\_\{$b$\}\backslash )$ and sets the global register cmp to I if $\backslash ($ r$\_\{2\}\backslash$geq r$\_\{$b$\}\backslash )$ and to $0$ otherwise.

bae increments the program counter pe by an immediate value if the value of the global register cmp is not equal to $1(\backslash (\backslash$mathrm$\{$pc$\}=\backslash )$ petoffset$)$

jmp sets the program counter pe to a value $\backslash ($ r$\_\{3\}\backslash )$ toffset and moves on to the next instruction.

a: Assuming that each stage of the pipeline takes three clock cycles to complete, how many instructions per clock cycle does the overall architecture execute? explain under what conditions

your answer holds true. What would be the consequence of improving stages $(1).(2)$ and $(3)$ to process one instruction per cycle? $(3$ points$)$

b: At which stage of the pipeline does the parallelism offered by the register banks become uscful and why? $(1$ point$)$

c: For which instructions in the ISA does the use of register banks speed up execution? $(1$ point$)$

You have written the following assembly code:

load r$0,10$ load value $10$ into register ro

load $\backslash (\backslash$mathrm$\{$rl$\},\backslash$mathrm$\{$I$\}\backslash )\backslash$# load $1$ into register rl

load $\backslash ($ r $2,0\backslash )\backslash$# load $0$ into register $\backslash ($ r $2\backslash )$

load $\backslash ($ r $3,0\backslash$quad $\backslash )\backslash$# load $0$ into register r $3$

load $\backslash (\backslash$mathrm$\{$r$\}4,1\backslash$quad $\backslash )\backslash$# load $1$ into register r $4$

load rs$,0\backslash$# load $0$ into rs

while :

add $\backslash (\backslash$mathrm$\{$rl$\},\backslash$mathrm$\{$r$\}2\backslash$quad

otin $\backslash )$ add contents of rl and r $2,$ store into r $2$

mov r$4,$ r$5$ ie r$5-$r$4$

add $\backslash (\backslash$mathrm$\{$r$\}3,\backslash$mathrm$\{$r$\}4\backslash )$ if $\backslash (\backslash$mathrm$\{$r$4\}-\backslash$mathrm$\{$r$\}3+\backslash$mathrm$\{$r$4\}\backslash )$

mov r$5,$ r$3\backslash$# $\backslash (\backslash$mathrm$\{$r$\}3=\backslash$mathrm$\{$r$\}5\backslash )$

cmpr $2,$ r$0\backslash (\backslash$quad $\backslash )\backslash$# $\backslash (\backslash$mathrm$\{$cmp$\}=\backslash$mathrm$\{$r$\}2>-\backslash$mathrm$\{$r$\}0\backslash )$

bne while

d: Re$-$assign register numbers to use the register banks correctly and avoid register conflicts. $(2$ points$)$

e: Assume that register bank conflicts are not a problem $($we$\text{'}$ve solved this somehow$)$ and look at the original code above $($not your modifications from d:$).$ How many pipeline stalls due to data hazards will occur while executing this program? Assume that no control hazards occur and that the pipeline is always fed with the next instruction from the correct branch. $(3$ points$)$

f$.$ Design a binary encoding for the instruction set. What type of operand encoding are you using? What is the largest offset that you can encode? $(3$ points$)$

g: The instruction set does not allow for a multiplication operation. Assume we want to use this processor to emulate one which provides a multiplication instruction mul $\backslash ($ r$\_\{$a$\}$ r$\_\{$b$\}\backslash )$ which computes the expression $\backslash ($ r$\_\{3\}=$r$\_\{1\}\backslash$times r$\_\{$b$\}\backslash ).$ Write an assembly code routine to implement this instruction. You can assume that the jump and boe instructions can be called with a label, instead of an explicit offect. Note: here we are using the pseudo assembly ISA defined above and not some real assembly language. Therefore, I expect the solution to be provided in pseudocode. $(5$ points$)$