Cache Misses

Cache Misses

Cache miss occur when a program accesses a memory location that is not in the cache. Since the processor then has to wait for the data to be fetched from the next cache level or form main memory before it can continue to execute.
The performance of the application directly influenced by cache misses.
It is hard to tell from just the number of misses if cache misses are causing performance problems in an application. The same number of misses will cause a much greater relative slowdown in a short-running application than in a long-running one.
A more useful metric is the cache miss ratio, that is, the ratio of memory accesses that cause a cache miss. From the miss ratio you can usually tell whether cache misses may be a performance problem in an application.
The cache miss ratio of an application depends on the size of the cache. A larger cache can hold more cache lines and is therefore expected to get fewer misses.
The performance impact of a cache miss depends on the latency of fetching the data from the next cache level or main memory. For example, assume that you have a processor with two cache levels. A miss in the L1 cache then causes data to be fetched from the L2 cache which has a relatively low latency, so a quite high L1 miss ratio can be acceptable. A miss in the L2 cache on the other hand will cause a long stall while fetching data from main memory, so only a much lower L2 miss ratio is acceptable.

Write-Through

Block in cache could just update on the data write hit.
-but cache and memory would be inconsistent
Write through also update memory but makes writes take longer
-e.g. if base CPI =1, 10% of instructions are stores, write to memory takes 100 cycles
-Effective CPI = 1 + 0.1 x 100 =11
Solution: write buffer
-Holds data waiting to be written to memory
-CPU continues immediately and only stalls on write if write buffer is already full

Write Back

Alternative: On data write hit, just update the block in cache
-keep track of whether each block is dirty
When a dirty block is replaced
-write it back to memory
-can use a write buffer to allow replacing block to be read first

Accessing Cache

Accessing Cache

Total number of bits needed for a cache
-size of tag field is
                -32-(n+m+2)
-the total number of bits in direct-mapped cache
                -2ⁿx(block size+ tag size+ valid field size)
Block size = 2^m words (2^m+5 bits), 1 bit for valid field size
Total number of bits in cache is
-2ⁿ x (2^m x 32 + (32-n-m-2) +1)
=2ⁿ x (2^m x32 +31-n-m)

Example
How many total bit are required for a direct mapped cache with 16kb of data and 4-word blocks, assuming a 32-bit address?
-16kb is 4K (2¹²) words
-with block size of 4 words (2²), 1024 (2¹⁰) blocks remaining for cache size
-each block has 4 x 32= 128 bits data plus a tag, which is 32 – 10 – 2 – 2 bits
-plus a valid bit
-total cache size = 2¹⁰ x (4 x 32+ (32 – 10 – 2 – 2) + 1)
                                = 2¹⁰ x 147
                                =147 Kbits

Cache example

-8-block, 1 word/block, direct mapped
-initial state

Direct Mapped Cache

Direct Mapped Cache
Let assume, as we did for fully associate caches that we have 128 slots and 32 bytes per slot
In a direct mapped cache, we treat the 128 slots as like they were an array of slots. We can index the into the array using binary numbers. For 128 slots, you need 7 bits. So, the index of the array is from 0000000₂ up to 1111111_2.

Since we have 128 slots, we need to specify which one we need the cache line to go in and this requires lg128=7bits. We can get the bits from the address itself directly.
Bits A_4-0 is still the offset. The slot number are the next 7bits, Bits A_11-5. The remaining bits, A_31-12 is the
tag.

Finding the slot

Suppose you have address of B_31-0 and you want to find it in cache memory.
By using bits B_11-5 to find the slot.
See if bits B_31-12match the tag of the slot.
If so, get the bytes at offset B_4-0.
If not, fetch the 32 bytes from memory and place it in the slot, updating valid bit, dirty bit and tag as needed.

Advantages

If there's an advantage to the scheme, it's that it's very simple. You don't have to simultaneously match tags with all slots. You just have one slot to check. If the data isn't in the slot, it's obvious that this is the slot to get evicted.

Summary

A direct-mapped cache scheme makes picking the slot easily. It treats the slot as a large array, and the index of the array is picked from bits of the address which is why we need the number of slots to be a power of 2, otherwise we can’t select bits from the address.
The scheme can suffer from many addresses “colliding” to the same slot, thus causing the cache line to be repeatedly evicted, even though there may be empty slots than aren’t being used, or being used with less frequency.

Memory Hierarchy

CPU Speed is dominated by memory performance

-More significant than : ISA, circuit optimization, pipelining, etc

Trick 1: Make slow main memory appear faster (caching)
Trick 2: Make small main memory appear bigger(virtual memory)

Memory Hierarchy Levels

Block(aka line): unit of copying
-may be multiple words
If accessed data is present in upper level
-access satisfied by upper level

If accessed data is absent

-miss-->block copied from lower level
-then accessed data is supplied from upper level

Parking Lot Analogy

Suppose we have 1000 parking spots. However, instead of being unnumbered, each parking spot is given a 3 digit number from 000 to 999.

Your parking spot is based on the first 3 digits of your student ID number.

What problem can occur? If you received your social security number (student ID) in Maryland, the first three digits of your student ID is likely to be in the low 200's.

Thus, there's a much higher chance someone will be in your parking spot. There's also a chance that parking spots numbered in the 900's might be mostly empty since few students may have student IDs with the first 3 digits in that range.

This is basically the direct-mapped scheme. The advantages of this scheme are that it's simple to find your parking spot. It can only be in one location.

Memory Organization

Overview

When the processor needs to read from or write to a location in main memory, it first checks whether a copy of that data is in the cache. If so, the processor immediately reads from or writes to the cache, which is much faster than reading from or writing to main memory.
The data cache is usually organized as a hierarchy of more cache levels.

Cache memory

Cache is a small but high speed memory which is used by central processing unit of a computer to reduce average time to access memory. The cache stores copies of the data from frequently used main memory location. Often the main memory will provide a wider data word to the cache than the CPU requires to fill the cache more rapidly. As long as most memory accesses are cached memory locations, the average latency of memory accesses will be closer to the cache latency than to the latency of main memory.

Cache Analogy

You are writing a term paper for your history class at a table in the library
-As you work you realize you need a book
-You stop writing, fetch the reference, continue writing
-You don’t immediately return the book, maybe you’ll need it again
-Soon you have a few books at your table, and you can work smoothly without needing to fetch more books from the shelves
-The table is a cache for the rest of the library

Now you switch to doing your biology homework
-You need to fetch your biology textbook from the shelf
-If your table is full, you need to return one of the history books back to the shelf to make room for the biology book 

Exercise ( K-maps)

Exercise

Below are some exercise for you to try it out !! Enjoy !

Write a simplified expression for the Boolean function defined by each of the following K-maps: