计算机应用 ›› 2013, Vol. 33 ›› Issue (04): 1018-1022.DOI: 10.3724/SP.J.1087.2013.01018

• 先进计算 • 上一篇    下一篇

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

刘磊1,熊小鹏2   

  1. 1. 重庆邮电大学 计算机科学与技术学院,重庆 400065
    2. 重庆新媒农信科技有限公司,重庆 401121
  • 收稿日期:2012-09-12 修回日期:2012-10-25 出版日期:2013-04-01 发布日期:2013-04-23
  • 通讯作者: 刘磊
  • 作者简介:刘磊(1987-),男,河南洛阳人,硕士研究生,主要研究方向:缓存技术、中文信息处理;熊小鹏(1978-),男,重庆人,教授级高级工程师,博士,主要研究方向:时空数据库、智能信息处理。
  • 基金资助:

    重庆优势蔬菜产业化关键技术集成与示范推广

Least cache value replacement algorithm

LIU Lei1,XIONG Xiaopeng2   

  1. 1. College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
    2. Chongqing A-media Communication Technology Company Limited, Chongqing 401121, China
  • Received:2012-09-12 Revised:2012-10-25 Online:2013-04-01 Published:2013-04-23
  • Contact: LIU Lei

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

关键词: 缓存替换, 驻留价值, 0-1背包问题, 字节命中率, 延迟时间

Abstract: In order to improve the performance of cache for search applications, this paper proposed a new replacement algorithm — the Least Cache Value (LCV) algorithm. The algorithm took into account the object access frequency and size of the object. The set of objects in the cache which has the minimum contribution to Byte Hit Ratio (BHR) should have priority to be replaced. Moreover, the selection of optimal replacement set of objects was transformed into classical 0-1 knapsack problems and a rapid approximate solution and the data structure of algorithm were given. The experiment proves that the LCV algorithm has better performance in increasing BHR and reducing Average Latency Time (ALT) than algorithms of LRU (Least Recently Used), FIFO (First-In First-Out) and GD-Size (Greed Dual-Size).

Key words: cache replacement, cache value, 0-1 knapsack problem, Byte Hit Rate (BHR), Average Latency Time (ALT)

中图分类号: