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…
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