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.