Analyzing Replacement Policies in List-Based Caches with Non-Uniform Access Costs
Analyzing Replacement Policies in List-Based Caches with Non-Uniform Access Costs
复制标题
DOI：
10.1109/infocom.2018.8485894
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
G. Casale
中科院分区：
文献类型：
--
作者：
G. Casale
基于列表的缓存可以提供比单列表缓存更低的未命中率，但由于状态空间爆炸，它们的分析具有挑战性。在此背景下，我们分析了具有非均匀访问代价的缓存的随机替换策略。在我们的模型中，成本可能取决于发出请求的流、目标项和包含它的列表。我们首先证明，类似于均匀代价的情形，随机替换(RR)和先进先出(FIFO)策略可以使用关于缓存均衡状态概率的乘积形式的表达式来精确分析。然后利用奇异摄动法处理状态空间爆炸问题，推导出当项数和缓存容量以固定比例增长时均衡性能指标的极限表达式。仿真结果表明，我们的渐近公式能够快速收敛到缓存均衡分布。
List-based caches can offer lower miss rates than single-list caches, but their analysis is challenging due to state-space explosion. We analyze in this setting randomized replacement policies for caches with non-uniform access costs. In our model, costs can depend on the stream a request originated from, the target item, and the list that contains it. We first show that, similarly to the uniform-cost case, the random replacement (RR) and first-in first-out (FIFO) policies can be exactly analyzed using a product-form expression for the equilibrium state probabilities of the cache. We then tackle the state space explosion by means of the singular perturbation method, deriving limiting expressions for the equilibrium performance measures as the number of items and the cache capacity grow in a fixed ratio. Simulations indicate that our asymptotic formulas rapidly converge to the cache equilibrium distribution.