# CA-2019Fall: Quiz 4

## A

When working with caches, we have to be able to break down the memory addresses we work with to understand where they fit into our caches. There are three fields:
* Tag - Used to distinguish different blocks that use the same index. Number of
bits: (# of bits in memory address) - Index Bits - Offset Bits
* Index - The set that this piece of memory will be placed in. Number of bits: log~2~(# of indices)
* Offset - The location of the byte in the block. Number of bits: log~2~(size of block)

Given these definitions, the following is true:
> log~2~(memory size) = address bit-width = # tag bits + # index bits + # offset bits

Another useful equality to remember is:
> cache size = block size ∗ num blocks

Given the follow chunk of code, analyze the hit rate given that we have a byteaddressed computer with a total memory of 1 MiB. It also features a 16 KiB Direct-Mapped cache with 1 KiB blocks. Assume that your cache begins cold.

#define NUM_INTS 8192 // 2ˆ13
int A[NUM_INTS]; // A lives at 0x10000
int total = 0;
for (int i = 0; i < NUM_INTS; i += 128) {
    A[i] = i; // Line 5
}
for (int i = 0; i < NUM_INTS; i += 128) {
    total += A[i]; // Line 8
}

`(1)` How many bits make up a memory address on this computer?
`(2)` What is the offset? (size)
`(3)` What is the index? (size)
`(4)` What is the tag? (size)
`(5)` Calculate the cache hit rate for the line marked Line `8`.

---

## B

In the problem `A`, we have a Direct-Mapped cache, in which blocks map to specifically one slot in our cache. This is good for quick replacement and finding out block, but not good for efficiency of space. This is where we bring associativity into the matter. We define associativity as the number of slots a block can potentially map to in our cache. Thus, a Fully Associative cache has the most associativity, meaning every block can go anywhere in the cache.

For an N-way associative cache, the following is true:
> N ∗ # sets = # blocks

Heres some practice involving a 2-way set associative cache. This time we have an 8-bit address space, 8 B blocks, and a cache size of 32 B. Classify each of the following accesses as a cache hit `(H)`, cache miss `(M)` or cache miss with replacement `(R)`. For any misses, list out which type of miss it is.

For this solution, we assume that we have an LRU replacement policy.

| Address | Hit, Miss, Replace |
|:-----------:|:--------------------:|
| 0b0000 0100 | <1> |
| 0b0000 0101 | <2> |
| 0b0110 1000 | <3> |
| 0b1100 1000 | <4> |
| 0b0110 1000 | <5> |
| 0b1101 1101 | <6> |
| 0b0100 0101 | <7> |
| 0b0000 0100 | <8> |
| 0b1100 1000 | <9> |

`(1-9)` Fill in the result of `<1>`, `<2>`, ..., `<9>`.

`(10)` What is the hit rate of our above accesses?

---

==Solution==

Problem A (5)
Line 5
The integer accesses are 4 ∗ 128 = 512 bytes apart, which means there are 2 accesses
per block. The first accesses in each block is a compulsory cache miss, but the
second is a hit because A[i] and A[i+128] are in the same cache block. Resulting in
a hit rate of 50%.

Line 8
The size of A is 8192 ∗ 4 = 2^15 bytes. This is exactly twice the size of our cache. At
the end of Line 5, we have the second half of A inside our cache, but Line 8 starts
with the first half of A. Thus, we cannot reuse any of the cache data brought in
from Line 5 and must start from the beginning. Thus our hit rate is the same as
Line 5 since we access memory in the same exact way as Line 5. We dont have to
consider cache hits for total, as the compiler will most likely store it in a register.
Resulting in a hit rate of 50%

Problem B

0b0000 0100 Tag 0000, Index 0, Offset 100 - M, Compulsory
0b0000 0101 Tag 0000, Index 0, Offset 101 - H
0b0110 1000 Tag 0110, Index 1, Offset 000 - M, Compulsory
0b1100 1000 Tag 1100, Index 1, Offset 000 - M, Compulsory
0b0110 1000 Tag 0110, Index 1, Offset 000 - H
0b1101 1101 Tag 1101, Index 1, Offset 101 - R, Compulsory
0b0100 0101 Tag 0100, Index 0, Offset 101 - M, Compulsory
0b0000 0100 Tag 0000, Index 0, Offset 100 - H
0b1100 1000 Tag 1100, Index 1, Offset 000 - R, Capacity