Cache locality and cache hierarchy are two important concepts that can help you optimize the performance of your applications that run on processors. In this article, you will learn what they are, why they matter, and how to exploit them in your code.
Cache locality refers to the tendency of a processor to access the same or nearby data repeatedly in a short period of time. When this happens, the processor can benefit from storing the data in a fast and small memory unit called cache, which reduces the need to fetch data from a slower and larger memory unit such as RAM or disk. There are two types of cache locality: temporal and spatial. Temporal locality means that the same data is accessed multiple times, while spatial locality means that data that is close together in memory is accessed together.
Cache hierarchy is the organization of multiple levels of cache in a processor, each with different size, speed, and cost characteristics. The lowest level of cache, usually called L1, is the smallest and fastest, but also the most expensive. The highest level of cache, usually called L3 or L4, is the largest and slowest, but also the cheapest. The intermediate level of cache, usually called L2, is a compromise between the two extremes. The cache hierarchy aims to balance the trade-off between performance and cost by storing the most frequently accessed data in the lower levels of cache and the less frequently accessed data in the higher levels of cache.
One way to exploit cache locality is to design your algorithms and data structures to access data in a predictable and sequential manner. For example, if you have an array of data, you can loop through it in a linear fashion, rather than jumping around randomly. This way, you can take advantage of spatial locality by loading a chunk of data into cache at once and accessing it multiple times. Another way to exploit cache locality is to reuse data as much as possible, rather than creating new copies or variables. This way, you can take advantage of temporal locality by keeping the data in cache for longer and avoiding cache misses.
One way to exploit cache hierarchy is to understand the size and associativity of each level of cache and tune your code accordingly. For example, if you know that your L1 cache has a size of 32 KB and a 4-way associativity, you can avoid cache conflicts by ensuring that your data does not map to the same cache line or set. Another way to exploit cache hierarchy is to use prefetching techniques to anticipate the data that you will need in the future and bring it closer to the processor. For example, you can use compiler directives or intrinsic functions to instruct the processor to load data from a higher level of cache or memory into a lower level of cache before you access it.
A cache miss occurs when the processor cannot find the data that it needs in the cache and has to fetch it from a higher level of memory. There are three types of cache misses: compulsory, capacity, and conflict. A compulsory miss happens when the data is accessed for the first time and is not in any level of cache. A capacity miss happens when the cache is full and has to evict some data to make room for new data. A conflict miss happens when the data maps to the same cache line or set as another data and causes a replacement. The penalty of a cache miss is the additional time and energy that the processor has to spend to fetch the data from a higher level of memory. The penalty depends on the level of cache that the miss occurs and the distance to the next level of memory.
One way to reduce cache miss types and penalties is to minimize the working set of your application, which is the amount of data that it needs to access frequently. This way, you can reduce the number of compulsory and capacity misses by fitting more data into the cache. Another way to reduce cache miss types and penalties is to optimize the cache mapping function, which determines how the data is distributed among the cache lines and sets. This way, you can reduce the number of conflict misses by avoiding collisions and improving the cache utilization. A third way to reduce cache miss types and penalties is to use parallelism and concurrency techniques to overlap the computation and memory access tasks. This way, you can hide or reduce the latency of fetching data from a higher level of memory by doing other work in the meantime.