You experiment with an embedded device having a one$-$level data cache $(128$ Bytes$)$ and a main

memory $(1$K Bytes. You exclusively focus on data accesses instead of instruction access$).$ The

latencies $($in CPU cycles$)$ of the different kinds of accesses are as follows:

Cache hit: $1$ cycle; Cache miss: $110$ cycles; Main memory access with cache disabled: $80$ cycles;

Now, Considering the following matrix multiplication $C=AB,$ please answer the following

questions $($please show detailed steps$)$

$A=\left[\begin{array}{ccc}{x}_{0,0}& \text{c}\text{d}\text{o}\text{t}\text{s}& x_{0,l}\\ \text{v}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}\\ x_{m,0}& \text{c}\text{d}\text{o}\text{t}\text{s}& x_{m,l}\end{array}\right]$ and $B=\left[\begin{array}{ccc}{y}_{0,0}& \text{c}\text{d}\text{o}\text{t}\text{s}& y_{0,n}\\ \text{v}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}\\ y_{l,0}& \text{c}\text{d}\text{o}\text{t}\text{s}& y_{l,n}\end{array}\right]$

What is the dimension of the matrix $C?$

For multiplication using ALU, assume you pre$-$load both A and $B$ into the main memory from

the storage and reserve space for $C$ in the main memory to speed up the performance. The Pre$-$

loaded A and B takes $50\%$ of the main memory space and reserved space for $C$ takes $12\mathrm{.}5\%$ of

the main memory. All elements in A$,$ B$,$ and C have the same bitwidth. Assuming we know the

value of $m$ and $(m+n)$ is a constant, then what is the maximum value of $l?$

Following the result from $2),$ If $x$ is a $16-$bit integer, what are the dimensions of $A,B,$ and $C?$

Following the result from $3),$ Assume that the cache is a fully associative cache with the least

recently used cache replacement policy $($LRU$)($ask me or Wikipedia if you forgot$)$ and the result

can be directly written back to the main memory without sacrificing the memory read, what is

the total memory access time $($total cycles$)$ for the matrix multiplication if we strictly follow the

instruction order as follows?

for $($int $i=0$; $im$;$i++)$

$\{$

for $($int $j=0$;$jn$;$j++)$

$\{$

$C(i,j)=A(i$;$)**B^{TT}($;$)$

$\}$

$\}$

How to make changes to leverage the locality of the data in cache for improvement? How

much can you improve with your method?

After the computation, if we randomly access elements from A$,$ B$,$ and C continuously, what

would the average memory access time $($cycles per access$)$ be$?$

Based on the observation from the results of $6)$ and the memory access time given at the

beginning, what can you conclude?