最小驻留价值缓存替换算法

作者：刘磊; 熊小鹏

来源：计算机应用, 2013, (04): 1018-1022.

• 缓存替换
• 驻留价值
• 0-1背包问题
• 字节命中率
• 延迟时间 cache replacement
• cache value
• 0-1 knapsack problem
• Byte Hit Rate(BHR)
• Average Latency Time(ALT)

为提高搜索应用的缓存性能,提出一种新的缓存替换算法——最小驻留价值(LCV)算法。该算法通过计算对象访问频率,结合对象大小,优先选取对字节命中率贡献最小的对象集进行缓存替换。同时,将最优替换对象集的选取转化为经典0-1背包问题进行了求解,并给出一种快速近似解法及其算法数据结构。在与最近最少使用(LRU)、先进先出(FIFO)和考虑多重因子(GD-Size)算法的对比实验中,LCV算法在提高字节命中率(BHR)和降低平均延时时间(ALT)方面具有更好的性能。

• 单位
  重庆邮电大学