TR-07-1.pdf
``Coordinated multilevel buffer cache management with consistent access
locality quantification"
Song Jiang, Kei Davis, and Xiaodong Zhang
IEEE Transactions on Computers, Vol. 56, No. 1, 2007, pp. 95-108.
Abstract
This paper proposes a protocol for effective coordinated buffer cache
management in a multilevel cache hierarchy typical of a client/server system.
Currently, such cache hierarchies are managed suboptimally --- decisions
about block placement and replacement are made locally at each level of
the hierarchy without coordination between levels. Though straightforward,
this approach has several weaknesses: 1) Blocks may be redundantly cached,
reducing the effective total cache size, 2) weakened locality at lower-level
caches makes recency-based replacement algorithms such as LRU less effective,
and 3) high-level caches cannot effectively identify blocks with strong
locality and may place them in low-level caches. The fundamental reason
for these weaknesses is that the locality information embedded in the
streams of access requests from clients is not consistently analyzed and
exploited, resulting in globally nonsystematic, and therefore suboptimal,
placement and replacement of cached blocks across the hierarchy. To address
this problem, we propose a coordinated multilevel cache management protocol
based on consistent access-locality quantification. In this protocol,
locality is dynamically quantified at the client level to direct servers to
place or replace blocks appropriately at each level of the cache hierarchy.
The result is that the block layout in the entirely hierarchy dynamically
matches the locality of block accesses. Our simulation experiments on both
synthetic and real-life traces show that the protocol effectively ameliorates
these caching problems. As anecdotal evidence, our protocol achieves a
reduction of block accesses of 11 percent to 71 percent, with an average
of 35 percent, over uniLRU, a unified multilevel cache scheme.