RISC-V LinuxBetaOPEN SILICON. SHARED KNOWLEDGE.

Memory Fit: Architectural Support for Page Placement by Learning Models of Good Behavior

AI Analysis Abstract This paper introduces "memory fit," a novel hardware abstraction designed to enhance page placement decisions within operating systems managing heterogeneous memory environments, such as those incorporating zswap, CXL memory expanders, and phase-change…

A full 8,192-frame grayscale heatmap with thin individual-page rows, alongside a zoom of offsets 64 through 127. Both show the same 12.35-billion-cycle interval and grayscale scale. Several…
Source: arxiv.org

AI Analysis

Abstract

This paper introduces "memory fit," a novel hardware abstraction designed to enhance page placement decisions within operating systems managing heterogeneous memory environments, such as those incorporating zswap, CXL memory expanders, and phase-change memories. It proposes "soft trace matching (STM)," an efficient, learning-based algorithm that quantifies how well a page's access patterns align with the optimal performance characteristics of each available memory type. Implemented on a BOOMv3 RISC-V processor running Linux 6.6, memory fit demonstrates substantial improvements over existing methods like Linux TPP, recovering a significantly larger portion of the performance gap to ideal page placement for various benchmarks and applications, while incurring minimal hardware and software overhead.

Key Highlights

  • Memory fit provides a hardware abstraction for precise page placement information in heterogeneous memory systems.
  • Soft Trace Matching (STM) is a computationally and space-efficient algorithm that estimates memory fit by comparing page accesses with learned models of optimal behavior for each memory type.
  • The system is implemented and evaluated in a BOOMv3 RISC-V processor running Linux 6.6.
  • Memory fit placements recover 2.2–3.8 times more of the performance gap to optimal placement than Linux TPP on extended GUPS.
  • For Redis with equal DRAM and PCM capacities, memory fit recovers 80% of the performance gap, compared to 19% for TPP, in a placement replay.
  • Memory fit requires only 64 bits of state per 4 KiB page and has a 1.2% overhead for OS kernel notification processing.

Technical Details

  • Memory fit measures how well a page's observed access pattern suits each available memory, with lower scores indicating better fit.
  • STM represents accesses as sequences of reads and writes with normalized reuse distances, building on context tree weighting (CTW) principles.
  • Hardware maintains a running tally for each page and memory, using a decaying average with more weight on recent accesses.
  • A 64-bit per-page record stores up to four eight-bit memory fit scores and a compressed access history.
  • An on-chip delta cache (64-entry, four-way) accumulates updates to reduce metadata traffic to main memory.
  • A range filter prevents STM from recursively observing its own memory accesses to the PFN table and event ring.
  • Eventual consistency is maintained for PFN record updates and notifications, ensuring the OS always reads the latest committed record.
  • A 16-register HyperLogLog estimator estimates the current working-set size for reuse distance normalization.
  • Stochastic rounding is used for 8-bit score quantization to retain fractional precision and prevent artificial ordering reversals.
  • Randomized tickets act as a low-pass filter to reduce noise from small, frequent score changes, preventing the OS from tracking instability.
  • Per-memory models are learned offline using synthetic fixed-work access traces and simulated completion times.
  • The implementation uses a Small BOOMv3 RISC-V core on an AWS F2 FPGA, operating at 18MHz, with a 4 MiB LLC and two 8 GiB NUMA nodes.
  • Hardware resource usage for STM and its request monitor is 10,414 LUTs, 7,572 flip-flops, and 13 DSP blocks.

Implications

  • Memory fit enables more effective page placement in increasingly heterogeneous server main memory environments (e.g., zswap, CXL, PCM).
  • It provides a more expressive signal for page placement than traditional 'page temperature' (access frequency), which is too coarse for complex memory performance characteristics.
  • The hardware-software co-design approach offloads complex measurement to hardware, simplifying the operating system's page placement policy.
  • The memory fit interface is retargetable across different memory-system setups, demonstrated with CXL-like devices.
  • Memory fit composes effectively with other advanced page movement policies, such as Colloid and per-page MLP ranking.
  • The core STM algorithm is general and could be extended to use other record representations or different objective functions (e.g., energy efficiency, durability, fairness).

Limitations

  • The current STM implementation uses records encoding read/write and reuse distance; other representations may be needed for future memory tradeoffs or to improve results.
  • STM as implemented is trained for lower completion time; other objective functions, such as energy efficiency, durability, or fairness, could be explored.
  • Whether other algorithms can outperform STM for estimating access affinity to different memories is an open area for future investigation.
  • Relaxing some coherence and precision guarantees might reduce overhead for scaling memory fit to multi-chiplet, high core-count, or multi-socket systems.
  • The evaluation was conducted on a single-core BOOMv3 RISC-V processor; in multicore systems, software processing overhead might be distributed differently.
  • The current RTL implementation prioritizes functional validation and timing closure, suggesting potential for further area optimization to reduce LUT and flip-flop use.
  • Exploring memory fit for large (2MB) and huge (1GB) pages is identified as future work.
  • Server-scale LUT comparison relies on reference assumptions for core budgets, not measured FPGA mappings of commercial server cores.
  • The one-monitor comparison assumes a single instance can service the observed request stream, which may not hold for all server scales.

Source: https://arxiv.org/abs/2611.07506

Read next

Explore all articles →