There's a big problem that we have been carefully ignoring for quite a while now:
In our examples we have 200 ps as the clock cycle time, and both tick 1 and tick 4 access memory,
which has a latency on the order of 15 ns.
That's right, we have 200 ps to perform an operation that takes 75 times that long.
That's obviously a problem.
Our answer to this problem is cache memory, which is a small amount of really fast memory that
keeps copies of the memory locations that are actually in use at any given time.
- When the program needs to access memory, it looks first in the cache.
- If the required value is there, we call it a cache hit.
- When we have a cache hit, the program just keeps on truckin.
- When we have a cache miss, we have to stall the CPU while we go out and get the value from main memory.
- When this happens, we also install the value into the cache.
- This exploits a property of programs known as temporal locality.
- This is just a name for the observed fact that, when a particular memory address is accessed,
the probability that it will be accessed again soon goes up.
- So putting it into the cache when it's first used means that it will already be there
if it's used again soon.
- A surprisingly small cache can performs almost as well as having all the main memory be fast enough
that no cache is needed. A hit rate upwards of 95% is common.
- Having a main memory that fast would be prohibitively expensive is were possible. Issues involving
physical size and the speed of light probably make it impossible, anyway.
- Modern processors have the cache right on the same chip as the CPU, which reduces the distances
that signals have to travel between CPU and cache.
The simplest organization for a cache is called direct mapping
- In this organization, each memory location has only one place in the cache that it might be.
- The cache is much, much smaller than main memory; this means that many, many memory locations
are assigned to the same cache location.
- Only one of them can be there at a time. That's obvious.
- The secret is that, however much memory a program occupies,
it is using only a small part of it at any given time.
- By having the contents of the cache closely track the parts of memory that are actually in use,
we get performance approaching that of really, really fast main memory.
- Here's how the mapping between memory addresses and cache addresses works:
- divide the memory address by the size of the cache and use the remainder as the cache address
- the remainder will be a number in the range 0 .. (cache size - 1), which exactly corresponds
to the range of cache addresses
- since the cache size is a power of 2, doing the division requires no work from the CPU
- One detail that we need to talk about is that caches don't do bytes;
if the CPU needs to fetch a byte, it gets the whole word from the cache and discards the other bits.
- Because of this, caches never use the 2 rightmost bits in an address.
Some More Terminology
- What we have been calling the cache address up to now is the index
- When we discard the 2 rightmost bits, we get numbers that increase by 1 (not 4)
as we go from one word to the next; we will call these numbers word numbers.
- I'd like to call them word addresses, but that risks confusion, which we don't need.
- A word's address is 32 bits, always with the rightmost 2 of them 0 bits.
When we discard those 2 rightmost bits, we get a 30-but number that is one fourth of the 32-bit address.
- That is, a word's address is 4 times its word number.
- The 2 rightmost bits in a memory address (the ones that caches ignore)
are known as the byte offset.
- Let's discuss the term offset; it will come back soon.
- the byte offset makes a good example since we already know about words and bytes
- the byte offset can have one of these values: 0, 1, 2, 3
- that tells us the byte's position relative to the beginning of the word
- the address of the byte is the sum of the word's address and the byte's offset
- we can compute a byte's offset by dividing the byte's address by 4
(the number of bytes in a word)
- The Fun-with-Address-Spaces pages apply to all this.
How it works
- This is pretty simple since there's only one place in the cache that a word can go.
- Take the word's address, throw away the 2 bits on the right; now we have its word number.
- Divide that by the cache size; that gives us the cache index,
which tells us where to put the word in the cache.
- There's another question here: once it's in the cache, how do we know where it came from?
- That is, how do we distinguish it from all the other addresses that map to the same cache index?
- That's explained in the next page: The Tag Field.