04. Cache

Lecture in russian

Why cache < storage?

What is «actuality»? See Locality_of_reference

(other: branches and equidistant references)

What to keep in cache:

TODO What to throw out of cache:

There always is worst case algorithm for every cache architecture.

Cache hit
access to cached element
Cache miss
access to non-cached element

We must know address (storage index) of cached element. If element is too small, caching is ineffective because of too much metadata:

| 00 | 10 04 00 00 | a0 78 4f 95 |

38 bits of metadata over 32 bits of data.

Note: address is 30 bits instead of 32 because we need no trailing two bits, which are zero if we addressing a word (4 bytes) instead of byte.

So let's go further and cache a whole memory block:

| 00 | 10 04 00 | a0 78 4f 95 … 34 45|

32 bits of metadata over 8192 bits of data.

Tag
part of memory address that corresponds to a memory block
Line
memory block that corresponds a tag

Caching a line of words at once (and probably by access to one word only) is statistically good tactics because of spatial locality

Direct cache

A line can cache one of selected list of blocks. If tags are equal, this is hit, if not equal or unused, this is miss (and cache line is filled).

dCache.png

Associative cache

Any line can cache any memory block (aligned to cache line size).

aCache.png

Multi-associative cache

How to violate spatial locality:

mCache.png

Multi-associative cache is superposition of direct and associative cache:

Write cache

Cache strategies:

H/W

HSE/ProgrammingOS/04_Cache (последним исправлял пользователь FrBrGeorge 2020-03-01 11:32:40)