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.
展开▼
机译:我们以任意的关联性(包括受害者缓存,偏斜缓存等)解决了在两级存储器上进行在线分页的问题。我们表明,某些重要的分页算法在广泛的关联性上(即使使用任意资源扩充)也不具有竞争性,尽管某些专为完全关联性设计的算法实际上在 any I>二级存储器上具有竞争性,专为完全关联性设计的分页算法的近视行为通常至少在某些“关联性拓扑”中会导致非常差的性能。同时,我们提出了一种简单而强大的技术,使我们能够克服这一缺点,将为完全关联性设计的算法推广为对任意关联的两级存储器都有效的实用算法。我们确定了一个简单的拓扑参数伪关联性 I>,该参数表征了在任何两级内存中均可实现的竞争比,从而为任何分页算法可实现的竞争性赋予了下限,并将其与因子4匹配。新颖的算法。
展开▼