|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
Competitive analysis was often criticized because of its too
pessimistic guarantees which do not reflect the behavior of paging
algorithms in practice. For instance, many deterministic paging
algorithms achieve the optimal competitive ratio of k, yet LRU and its
variants clearly outperform the rest in practice. In this paper we aim
to reuse and refine insights from the competitive analysis to obtain
new algorithms that cause few cache misses in practice. We propose a
new measure of the "evilness" of the adversary, which results in a
parametrization of the input that we denote attack rate. This measure
is based on a chacterization by Koutsoupias and
Papadimitriou of the optimal offline algorithm and uses the fact that
a number of pages are for sure in its memory. We show that the attack
rate r is a tight bound on the competitive ratio of deterministic
paging algorithms and give experimental results which show that r is
usually much smaller than the cache size k and thus provides more
realistic upper bounds for the competitive ratio of existing
algorithms. Furthermore, we show that our input parametrization
compares favorably concerning the fault rate with approaches based on
locality of reference. We use a priority-based framework, which always
yields r-competitive algorithms regardless of the priority assignment.
In this framework, LRU can be obtained under a certain priority
assignment and is thus only one algorithm among many other
r-competitive ones. Using the enhanced flexibility given by this
framework, we give a priority policy which leads to an algorithm
outperforming LRU, RLRU and other practical algorithms on a wide
selection of real-world cache traces. Host: Rolf Fagerberg SDU HOME | IMADA HOME | Previous Page Daniel Merkle |