A hash table implemented in hardware 2019.03.30 KO | EN Principle of Locality Caches Cache Metrics Cache Organization Indexing Tag Matching Tag Overhead Associative Cache Set Associative Cache Organization Concrete Example Handling Cache Writes Software Restructuring References As technology has advanced, processor speed has risen quickly, but memory speed hasn’t kept up. No matter how fast a processor is, if memory responds slowly the whole system ends up slow. The device that addresses this is the cache. A cache is a small, fast memory that sits inside the CPU chip. (It’s also expensive.) Going to main memory for data every time is slow, so the cache holds frequently used data and lets the processor reach that data from the cache instead of main memory, which speeds things up. Principle of Locality The judgment about which data is “frequently used” follows the principle of locality, which can be split into temporal locality and spatial locality.…