Tutorial Work

1

Total bits = $20$.

$$\begin{array}{rl}{2}^{20}\text{ words}& \to \text{mm}\\ 2^5\text{ blocks}& \to \text{cache}\\ 2^4\text{ words}& \to 1\text{ block}\end{array}$$

1. $\frac{2^{20}}{2^4}=2^{16}$
2. We have $20$ bits:
   • tag field: $20-5-4=11$ bits
   • block field: $5$ bits
   • offset field (word field): $4$ bits
3. $0DB63_{16}=00001101101101100011_2$ $16+4+2=\text{block }22$

title: Correct answers.

2

Total bits = $16$

$$\begin{array}{rl}{2}^{16}\text{ words}& \to \text{mm}\\ 2^6\text{ blocks}& \to \text{cache}\\ 2^5\text{ words}& \to 1\text{ block}\end{array}$$

1. $\frac{2^{16}}{2^5}=2^{11}$ blocks
2. Format of address:
   • tag field: $16-5=11$ bits
   • word field: $5$ bits
3. Anywhere, as blocks can be placed in any location of the cache.

title: Correct answers.

3

Total bits = $28$

$$\begin{array}{rl}256\text{M words}=2^{28}& \to \text{mm}\\ 64\text{ blocks}=2^6& \to 1\text{ block}\\ 32\text{K words}=2^{15}& \to \text{cache}\end{array}$$

1. Memory size: $2^8\times 2^{20}=2^{28}$ words Block size: $2^6$ words Cache size: $2^5\times 2^{10}=2^{15}$ blocks Number of sets: $2^{15}/2=2^{14}$ sets

   We have $28$ bits to work with:

   • set field: $14$ bits
   • word field: $6$ bits
   • tag field: $8$ bits

4

1. Show main memory address format

   $$\begin{array}{rl}{2}^3\text{ blocks}& \to \text{ cache}\\ 2^{12}\text{ blocks}& \to \text{ mm}\\ 2^3\text{ words}& \to \text{ 1 block}\end{array}$$

   We have $12$ bits to work with:

   • word field: $3$ bits
   • block field: $3$ bits
   • tag field: $12-6=6$ bits

2. Compute hit ratio for a program that loops $4$ times from locations $0_{10}$ to $67_{10}$ in memory.

   We know we have $8$ blocks in cache, and at least $9$ blocks in main memory.

   Block $0$ and block $8$ will have a clash and both go to block $7$ (for pass 1).

   Pass 2 will equal pass 3, 4, …

   $$\begin{array}{rl}\text{Hit Ratio}& =\frac{\text{hit}}{\text{hit }+\text{ miss}}\\ & =\frac{257}{272}\\ & =0.944\\ & =94.485\%\\ & \\ \text{Miss Ratio}& =1-0.944\\ & =0.05515\\ & =5.515\%\end{array}$$

3. Compute the effective access time for this program.

   $$\begin{array}{rl}EAT& =(HR\times CA)+(MR\times MA)\\ & =0.944\ast 22+0.05515\ast 300\\ & =373\text{ ns}\end{array}$$

title: TA working

5

$$\begin{array}{rl}24-\text{bit address}& \to 24\text{ bits}\\ 2^{16}\text{ bytes}& \to \text{cache}\\ 2^5\text{ bytes (word)}& \to 1\text{ block}\end{array}$$

1. Direct-mapped cache

   • Word field: $5$ bits
   • Block field: $\frac{2^{16}}{2^5}=2^{11}\to 11$ bits
   • Tag field: $24-5-11=8$ bits

2. Associative cache

   • Word field: $5$ bits
   • Tag field: $24-5=19$ bits

3. 4-way set associative cache

   • Set field: $11-2=9$ bits
   • Word field: $5$ bits
   • Tag field: $24-14=10$ bits

title: TA working

6

In a direct-mapped cache, there is only one location we can write to so the victim block is already decided.

title: Correct answer.