FAST '08 – Abstract
Pp. 49–65 of the Proceedings
On Multi-level Exclusive Caching: Offline Optimality and Why Promotions
Are Better Than Demotions
Binny S. Gill, IBM Almaden Research Center
Abstract
Multi-level cache hierarchies have become very common; however, most
cache management policies result in duplicating the same data redundantly on
multiple levels.
The state-of-the-art exclusive caching techniques used to mitigate this wastage in
multi-level cache hierarchies are the DEMOTE technique and its variants.
While these achieve good hit ratios, they suffer from significant I/O and
computational overheads, making them unsuitable for deployment in
real-life systems.
We propose a dramatically better performing alternative called PROMOTE,
which provides exclusive caching in multi-level cache hierarchies without
demotions or any of the overheads inherent in DEMOTE.
PROMOTE uses an adaptive probabilistic filtering technique to decide which pages
to ``promote" to caches closer to the application.
While both DEMOTE and PROMOTE provide the same aggregate hit ratios,
PROMOTE achieves more hits in the highest cache levels leading to better
response times.
When inter-cache bandwidth is limited, PROMOTE convincingly outperforms
DEMOTE by being  x more efficient in bandwidth usage.
For example, in a trace from a real-life scenario,
PROMOTE provided an average response time of  ms as compared to  ms for DEMOTE on a two-level hierarchy of LRU caches, and  ms as compared to  ms on a three-level cache hierarchy.
We also discover theoretical bounds for optimal multi-level cache performance.
We devise two offline policies, called OPT-UB and OPT-LB, that provably serve
as upper and lower bounds on the theoretically optimal performance of
multi-level cache hierarchies.
For a series of experiments on a wide gamut of traces and cache sizes OPT-UB
and OPT-LB ran within  % and  %
of each other for two-cache and three-cache hierarchies, respectively.
These close bounds will help evaluate algorithms and
guide future improvements in the field of multi-level caching.
- View the full text of this paper in HTML and PDF. Listen to the presentation in
MP3 format.
The Proceedings are published as a collective work, © 2008 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
|
