HW$4-1(43$ points$)$ Suppose we wish to write a procedure that computes the inner product of two vectors $\backslash ($ u $\backslash )$ and $\backslash ($ v $\backslash ).$ An abstract version of the function has a CPE of $14-18$ with x$86-64$ for different types of integer and floating$-$point data. Doing the same sort of transformations as in the text to get from the program combine$1$ to the more efficient combine$4,$ we get the following code:

$```$

typedef float data$\_$t;

#include "vec.h$"$

long i;

long length $=$ vec$\_$length$($u$)$;

data$\_$t $*$udata $=$ get$\_$vec$\_$start$($u$)$;

data$\_$t $*$vdata $=$ get$\_$vec$\_$start$($v$)$;

data$\_$t sum $=($data$\_$t$)0$;

for $($i $=0$; i $$ length; i$++)\{$

sum $=$ sum $+$ udata$[$i$]*$ vdata$[$i$]$;

$\}$

$*$dest $=$ sum;

$\}$

$```$

void inner$4($vec$\_$ptr u$,$ vec$\_$ptr v$,$ data$\_$t $*$dest$)\{$

Our measurements show that this function has a CPE of $1\mathrm{.}50$ for integer data and $3\mathrm{.}00$ for floatingpoint data. For data type double, the x$86-64$ assembly code for the inner loop $($produced on our virtual machine with flags $-02,-$mavx$2,$ and $-$S is as follows:

$```$

# Inner loop of inner$4.$ data$\_$t $=$ double. OP $=*.$

# udata in $\%$rbp$,$ vdata $\%$rax, sum in $\%$xmm$0,$ i in rcx$,$ limit in rbx

$.$L$15$: # loop:

vmovsd O$(\%$rbp$,\%$rcx$,8),\%$xmm$1$ # Get udata$[$i$]$

vmulsd $(\%$rax,$\%$rcx$,8),\%$xmm$1,\%$xmm$1$ # Multiply by vdata$[$i$]$

vaddsd $\%$xmm$1,\%$xmm$0,\%$xmm$0$ # Add to sum

addq $$1,\%$rcx # Increment i

cmpq $\%$rbx$,\%$rcx # Compare i:limit

jl $.$L$15$ # If goto loop

$```$

The new details of floating$-$point assembly code are pretty fully captured by just looking at Figures $3\mathrm{.}45,3\mathrm{.}46,$ and $3\mathrm{.}49$ with their captions.

Assume that the functional units have the latencies and issue times given in Figure $5\mathrm{.}12($and in the course notes$).$

A$.$ Diagram how this instruction sequence would be decoded into operations, and show how the data dependencies between them would create a critical path of operations. This process of diagramming is illustrated in Figures $5\mathrm{.}13($dpb$-$sequential.pptx $($live$.$com$)),5\mathrm{.}14($Figure: dpb$-$flow.pptx $($live$.$com$)$ and Figure: dpb$-$flow$-$abstract$.$pptx $($live$.$com$)),$ and $5\mathrm{.}15($Figure: dpb$-$flow$-$multiple.pptx $($live$.$com$))$; you can draw just a diagram in the style of $5\mathrm{.}14($a$),$ but do add identification of where the critical path is$.(25$ points.$)$

B$.$ For data type double, what lower bound on the CPE is determined by the critical path? Give a numerical value and an explanation. $(6$ points.$)$

C$.$ Assuming similar instruction sequences for the integer code as well, what lower bound on the CPE is determined by the critical path for integer data? Give a numerical value and an explanation. $(6$ points.$)$

D$.$ Explain how the floating$-$point version can have a CPE of $3\mathrm{.}00$ even though the multiplication operation requires $5$ cycles. $(6$ points.$)$

HW$4-2(27$ points$)$

A$.$ Write a version of the inner product procedure described in the previous problem that uses five$-$way loop unrolling $(\backslash (5\backslash$times $1\backslash )$; no parallelism$).(15$ points.$)$

For x$86-64,$ our measurements of the unrolled version give a CPE of $1\mathrm{.}07$ for integer data but still $3\mathrm{.}01$ for floating$-$point data.

B$.$ Explain why any version of any inner product procedure $($even with parallelism$)$ cannot achieve a CPE less than $1\mathrm{.}00.(6$ points.$)$

C$.$ Explain why the performance for floating$-$point data did not improve with loop unrolling. $(6$ points.$)$