Paging with Arbitrary Associativity

We tackle the problem of online paging on two level memories with arbitrary associativity (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 associativity are actually competitive on any two level memory, the myopic behavior of paging algorithms designed for full associativity 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 associativity 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.