Online paging with arbitrary associativity
Enoch Peserico · Symposium on Discrete Algorithms · 2003
We tackle the problem of online paging on two level memories with arbitrary (including victim caches, skewed caches etc.). We show that some important classes of paging algorithms are not competitive on a wide class of associativities (even with arbitrary resource augmentation) and that although some algorithms designed for full are actually competitive on any two level memory, the myopic behavior of paging algorithms designed for full will generally result in very poor performance at least for some associativity topologies. At the same time we present a simple and yet powerful technique that allows us to overcome this shortcoming, generalizing algorithms designed for full into practical algorithms which are efficient on two level memories with arbitrary associativity. We identify a simple topological parameter, pseudo associativity, which characterizes the competitive ratio achievble on any two level memory, giving a lower bound on the competitiveness achievable by any paging algorithm and matching it within a factor 4 with a novel algorithm.