Design Principles of CPU Cache Hierarchy

Basic Concepts of Cache

CPU cache is a high-speed storage hierarchy connecting the processor and main memory, aiming to reduce memory access latency and improve overall computational efficiency. Cache achieves data prediction through the locality principle (temporal and spatial locality), establishing a balance between speed and capacity between the processor and main memory.

Cache Hierarchical Structure

CPU cache typically adopts a multi-level design, forming a three-level cache hierarchy:

  • L1 Cache
    • Capacity: Usually 64KB to 256KB
    • Speed: Approaches CPU core frequency (e.g., 1.5ns to 2ns)
    • Characteristics: Directly bound to CPU cores, lowest access latency, but smallest capacity.
  • L2 Cache
    • Capacity: Several MB (e.g., 256KB to 1MB)
    • Speed: Slightly slower than L1 (e.g., 4ns to 8ns)
    • Characteristics: Shared among multiple cores, capacity and speed between L1 and main memory.
  • L3 Cache
    • Capacity: Several MB to several tens of MB (e.g., 4MB to 16MB)
    • Speed: Slower than L2 (e.g., 10ns to 15ns)
    • Characteristics: Multi-core shared, supplements L1 and L2 to reduce main memory access frequency.

Cache Hierarchical Design Principles

Practical Application of Locality Principle

  1. Temporal Locality
    • If a program accesses a data item, it is likely to access it again in the near future.
    • Cache design uses high-speed storage and rapid access to implement this characteristic, such as high hit rates in L1 cache.
  2. Spatial Locality
    • If a program accesses a memory address, it may access adjacent addresses in the future.
    • Cache line mechanism implements spatial locality by fixed-size blocks (e.g., 64B) to minimize address translation overhead.

Cache Replacement Strategies

  • LRU (Least Recently Used) algorithm
    • Prioritizes replacing the least recently used data to ensure frequently accessed data remains in cache.
    • Implementation: Records usage time of each data block and dynamically adjusts replacement order.
  • FIFO (First In First Out) algorithm
    • Replaces the earliest entered data block, simple but may sacrifice hit rate.

Trade-off Between Cache Capacity and Speed

  • Capacity: L1 cache has the smallest capacity (usually 64KB), but the fastest (less than 1ns); L3 cache has the largest capacity (several tens of MB), but the slowest (greater than 10ns).
  • Speed: L1 cache speed aligns with CPU core frequency, while L3 cache speed is limited by total bus bandwidth.

Cache Optimization Strategies

Cache Line Size Design

  • Typical values: 64B to 128B
  • Function: Balance cache hit rate and storage overhead, avoiding frequent cache line replacement.
  • Problem: Too large cache lines increase spatial waste, too small lead to frequent replacement.

Prefetching Mechanism (Prefetching)

  • Purpose: Load data into cache ahead of its access to reduce main memory access delay.
  • Types:
    • Hardware prefetching: Predicts access patterns via hardware and automatically loads data.
    • Software prefetching: Explicitly specifies data loading positions using instructions (e.g., prefetch).

Cache Consistency Maintenance

  • Multi-core systems: L3 cache ensures all cores see consistent data states.
  • Protocol: Uses the MESI (Modified, Exclusive, Shared, Invalid) protocol to maintain consistency through state markings.

Applications of Cache Hierarchical Structure

  1. Single-core CPU: L1 and L2 cache dominate performance, with L3 cache as a supplement.
  2. Multi-core CPU: L3 cache is shared among all cores, while L1 and L2 caches are bound to cores.
  3. Embedded systems: L1 cache has small capacity but critical access speed.
  4. Server CPUs: L3 cache has large capacity, reducing main memory access delay to enhance concurrent performance.

Challenges in Cache Design

  • Capacity vs. speed trade-off: Increasing cache capacity decreases speed, vice versa.
  • Hit rate vs. miss penalty: Main memory access delay may significantly increase when cache misses (e.g., 100ns to 1ms).
  • Multi-core consistency: High cost for cache consistency maintenance in multi-core systems.
    By properly designing cache hierarchies, modern CPUs achieve balance between speed, capacity, and cost, providing foundational support for high-performance computing.