Understanding Cache Memory

Definitions

• Cache defined as small, fast, expensive, static RAM
• Cache holds copy of data that is faster to access than the original
• Cache hit occurs if cache has copy data
• Cache miss occurs if cache does not have copy
• Cache block is unit of cache storage
• Cache block includes 4-64 memory words in hardware memory
• Cache block can include powers of 2 of hardware page size in file system

Cache Usefulness

• For cache to be useful cost from cache retrieval must be less than fetching from memory
• Likelihood of cache hit must be high enough
• Sources of predictability include temporal and spatial locality

Temporal and Spatial Locality

• Temporal locality describes when programs reference the same memory locations multiple times
• An example of temporal locality is instructions in a loop incrementing counter variable, frequent accessing of a data structure
• Spatial locality describes when programs reference nearby memory locations
• An example of Spatial locality is accessing/updating elements of an array

Cache Concepts

• Write-through cache changes sent immediately to next level of storage
• Write-back cache changes stored until cache block is replaced

Memory Hierarchy

• Processors have different numbers and sizes of caches
• Caches can be inclusive or exclusive
• The x486 processor has L1 on the chip and L2 on the motherboard

Cache and Byte Scaling

• Kilo is 10^3, Kibi is 2^10
• Mega is 10^6, Mebi is 2^20
• Giga is 10^9, Gibi is 2^30
• Terra is 10^12, Tebi is 2^40
• Peta is 10^15, Pebi is 2^50
• Exabyte is 10^18, Exbi is 2^60
• Zetta is 10^21, Zebi is 2^70
• Yotta is 10^24, Yobi is 2^80
• IEC refers to International Electrotechnical Commission

Cache Sizing

• Key factors to consider when sizing cache are cost and speed
• Cache hit rate is a function of cache size
• Small cache results in small hit rate, large cache results in high hit rate
• Thrashing is a possibility
• Working set is a portion of the process needed for execution
• Good performance and cache hit rate are key for success
• Resident set is what is actually in memory
• Bursty cache miss rates can occur on process switch and during execution of a process

Cache Lookup

• Cache contains memory address and value, stores block of memory, not just one memory word
• Intel has 64byte chunks
• Three common Cache Lookup mechanisms include Fully associative, Set Associative, and Direct Mapped

Fully Associative Cache

• With fully associative cache address can be stored anywhere in the cache
• Requires checking all entries
• Upon match returns the value
• Otherwise cache miss results and have to go fetch from main memory

Direct Mapped Cache

• Each address can be stored at only one location in direct mapped cache
• Hashing of address to entry to lookup performed
• Direct mapped typically enables faster lookups
• Direct mapped not flexible, need to consider what happens if 2 addresses hash to the same location

Set Associative Cache

• Set associative combines benefits of both direct mapped and fully associative caches
• Set associative slower lookup than direct mapped, but has flexibility of fully associative cache
• k-set associative has k cache replicas
• All replicas in k-set associative lookup performed in parallel
• Hit occurs if found in any of the k replicas

Page modification checks

• Page table entries contain bookkeeping bits
• Dirty bit indicates if page has been modified
• Dirty bit set by hardware on first store instruction and in both TLB and page table entry
• Use bit shows if page has been recently used
• Use bit set by hardware in page table entry on TLB miss
• Bookkeeping bits can be reset by the OS kernel
• Includes when changes to page are flushed to disk
• It also assists to track whether page is recently used

Terminology

• Modified, changed and dirty are the same
• Recently used, used, accessed, and referenced are the same

Virtual/Physical Dirty/Use Bits

• Most machines keep dirty/use bits in the page table
• Physical page is modified if any page table entry that points to it is modified
• Physical page recently used if any page table entry that points to it is recently used
• On MIPS, simpler to keep dirty/use bits in the core map
• Core map is a map of physical page frames

Cache Replacement Policy

• With cache miss, determine which entry to replace
• Assuming the new entry is more likely to be used in the near future
• In direct mapped caches, determining which entry to replace is not an issue
• Policy goal is to reduce cache misses and improve overall performance
• Policy goal helps reduce likelihood of poor performance and promotes efficient use of cache

Simple Replacement Policies

• Random replacement replaces a random entry in cache
• Random replacement can be unpredictable
• FIFO replaces the entry that has been in the cache the longest time
• A worst case occurs for FIFO is if program strides through memory that is larger than the cache

LRU and LFU

• Least Recently Used (LRU) uses principle of temporal locality
• LRU replaces entry that has not been used for the longest time in the past
• Least Frequently Used (LFU) replaces the cache entry used the least often in the recent past

Belady’s Anomaly

• Belady's anomaly describes the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns
• This phenomenon is commonly experienced when using the first-in first-out page replacement algorithm

Clock Algorithm

• Clock algorithm can estimate LRU
• This estimates through periodically, sweeping through all pages
• If page is unused it is reclaimed
• If page is used, then mark as unused

Nth Chance Algorithm

• Nth Chance Algorithm stands for Not Recently Used
• Instead of one bit per page, keep an integer
• Integer counts number of sweeps since last use as notInUseSince
• Periodically sweep through all page frames and if page is used, notInUseSince is set to 0
• However, If page is not used it increments
• If notInUseSince reaches N then reclaim the page

Page Coloring

• Page coloring is relevant when the cache size is much larger than page size
• Page coloring can be direct mapped or set associative
• Multiple pages map to the same cache line
• OS page assignment matters
• Example: 8MB cache and 4KB pages
• In this example, 1 of every 2K pages lands in same place in cache

Zipf Distribution

• Caching behavior of many systems is not well characterized by the working set model
• An alternative is the Zipf distribution
• In Zipf, Popularity ~ 1/ka, for kth most popular item, with 1 < α < 2
• Examples of Zipf models include web pages, movies, library books, words in text, salaries, and city populations