Page placement algorithms for large real-indexed caches

TLDR

Cache performance in systems with paged virtual memory and large real‑indexed caches depends on main‑memory page placement, yet most operating systems use arbitrary page‑frame selection from the replacement‑algorithm pool. The authors aim to demonstrate that naive page placement can cause up to 30 % unnecessary cache conflicts and to develop careful‑mapping algorithms that reduce such contention. They construct a simple model to quantify the conflict penalty and design careful‑mapping algorithms that choose page frames likely to lower cache contention. Trace‑driven simulations show that careful mapping cuts dynamic cache misses by 10–20 % versus naive mapping and achieves roughly half the miss reduction of doubling cache size or associativity.

Abstract

When a computer system supports both paged virtual memory and large real-indexed caches, cache performance depends in part on the main memory page placement. To date, most operating systems place pages by selecting an arbitrary page frame from a pool of page frames that have been made available by the page replacement algorithm. We give a simple model that shows that this naive (arbitrary) page placement leads to up to 30% unnecessary cache conflicts. We develop several page placement algorithms, called careful-mapping algorithms , that try to select a page frame (from the pool of available page frames) that is likely to reduce cache contention. Using trace-driven simulation, we find that careful mapping results in 10–20% fewer (dynamic) cache misses than naive mapping (for a direct-mapped real-indexed multimegabyte cache). Thus, our results suggest that careful mapping by the operating system can get about half the cache miss reduction that a cache size (or associativity) doubling can.