Cache Line and Associativity

#hardware/memory

cache line is the smallest chunk of memory a cache moves and manages at once which maps to a location of main memory.

What cache line look like:

What is dirty cache line ?

The content of the cache line before the write operation has to be loaded. A cache line which has been written to and which has not been written back to main memory is said to be dirty. Once it is written they dirty flag is cleared.

Associativity

Fully Associative

![[what-every-programmer-should-know-about-memory.pdf#page=18&rect=67,603,281,768&color=note]]

How it Look up:

  1. compare tag through the whole cache lines by a special hardware.
  2. if tag match, then get value from word id.

Pros: minimal conflict misses.
Cons: expensive hardware latency.

A Real Case 1:

char a[8]; // address at 0x200
printf("a[4] is %d\n", a[4]); // a[4] is at 0x204

to get a value from 0x204. (0b1000000_100).

So it look up line#0 and compare the tag is 100 or not.
If not found, then cache miss.
if found, then value is at offset 4.

Direct Mapping

![[what-every-programmer-should-know-about-memory.pdf#page=18&rect=62,83,281,232&color=note]]

How it Look up:

  1. search line number (a.k.a set) from the given address
  2. compare tag
  3. if tag match, then get value from offset

Pros: simple and fast.
Cons: highest conflict miss rate.

A Real Case 1:

char a[8]; // address at 0x200
printf("a[4] is %d\n", a[4]); // a[4] is at 0x204

to get a value from 0x204. (0b1000_000_100).

So it look up line#0 and compare the tag is 10 or not.
If not found, then cache miss.
if found, then value is at offset 4.

A Real Case 2:

char a[5]; // address at 0x200
char b[5]; // address at 0x205
printf("a[4] is %d\n", a[4]); // a[4] address is at 0x204
printf("b[2] is %d\n", b[2]); // b[4] address is at 0x207

to get a[4] from 0x204 (0b1000_000_100) -> tag = 10, set = 0, offset = 4
to get b[2] from 0x207 (0b1000_000_111) -> tag = 10, set = 0, offset = 7
Boom ! they are all in the same set which means the cache needs to read a[] and then evict it from cache.

N-Set Associative

![[what-every-programmer-should-know-about-memory.pdf#page=18&rect=296,338,540,511&color=note]]

How it Look up:

  1. search set id from the given address
  2. compare tag
  3. if tag match, then get value from offset

Pros: fewer conflict misses than direct-mapped, cheaper than fully associative.
Cons: moderate complexity, per-set replacement needed.