Principles of Cache Operation
A. Locality: Temporal and spatial locality
Caches' operation is based on the principle of locality of reference, which describes that programs tend to access the same set of data or the data with nearby addresses. There are two types of locality, temporal and spatial.
Temporal locality: the tendency of accessing the same data again shortly
Spatial locality: the tendency to access data with addresses near to the current data shortly
Locality is common in loop instructions as some variables are accessed repeatedly. For example, in the following loop,
Cache performance can be measured by hit rate and miss rate:
Hit rate is the percentage of cache hits.
Hit rate = (Number of cache hits / Number of cache accesses) * 100%
On the other hand, miss rate is the percentage of cache misses.
Miss rate = (Number of cache misses / Number of cache accesses) * 100% OR 1 - hit rate
Ideal hit rate >= 95%
Ideal miss rate <= 5%
Average memory access time can be calculated using the following formula:
Average memory access time = Number of Cache hits + Miss rate * Cache Miss penalty
* More information about different types of cache misses
Click to view source code of this page.
Locality is common in loop instructions as some variables are accessed repeatedly. For example, in the following loop,
sum = 0;
for (i = 0; i < 5; i++) {
sum += a[i];
}
return sum;
the variable sum is accessed repeatedly during every iteration, illustrating temporal locality. On the other hand, the array elements a[i] are accessed in consecutive order, demonstrating spatial locality.
Taking advantage of the principle, these two types of data are stored in the cache. As a result, the CPU has a better chance of accessing the data more quickly.
B. Performance Evaluation: Cache Hits and Cache Misses
A cache hit refers to a successful data retrieval from the cache, given that the cache contains the required data. In contrast, a cache miss occurs when data cannot be found in the cache. In the case of a cache miss, the required data must be fetched from a slower memory unit like the main memory. A cache miss penalty is then incurred, which is the additional time or delay. As a result, memory access time would increase.Cache performance can be measured by hit rate and miss rate:
Hit rate is the percentage of cache hits.
Hit rate = (Number of cache hits / Number of cache accesses) * 100%
On the other hand, miss rate is the percentage of cache misses.
Miss rate = (Number of cache misses / Number of cache accesses) * 100% OR 1 - hit rate
Average memory access time can be calculated using the following formula:
Average memory access time = Number of Cache hits + Miss rate * Cache Miss penalty
* More information about different types of cache misses
By Cheng Man Ho (56612619)
Click to view source code of this page.