LRFU及其自适应算法的研究

发布时间：2017-07-19 13:28

  本文关键词：LRFU及其自适应算法的研究

  更多相关文章： 缓存策略 数据访问模式 局部性 竞争机制 预测机制

【摘要】：缓存作为一项提高计算机性能的重要技术,能够较好的避免频繁的访问数据库和磁盘文件,是弥补处理器与存储系统之间差异的有效手段。但随着处理器快速的发展,对缓存性能提出了更高的要求。计算机普遍采取扩大缓存容量来提高缓存性能,但由于硬件加工技术受工艺及功耗的限制,此时设计良好的缓存算法以提高缓存性能已经成为了一大热点。经过对传统经典算法及数据访问模式研究,若选取的策略不合适,会导致缓存发生“颠簸”现象,即数据块刚被置换出缓存不久又会重新被访问,这时又需要将其调入缓存,同时也要将某一其它块剔除出缓存,频繁地在缓存和主存中进行置换操作,处理器会浪费大量时间在调度数据块上,严重影响系统整体性能。采用良好的策略可以避免缓存发生“颠簸”现象,可以有效提高缓存性能和系统整体性能。针对LRFU(Least Recently Frequently Used)算法及其自适应算法中的不足,提出了相关改进策略,改进策略分为以下部分:1)基于局部性定量分析模型,分析数据局部性强弱并给出相关调整λ策略,改善算法对不同访问模式的适应性。2)采用2路组相联的体系结构:将队列分为冷热两个队列,提高算法捕捉低频和高频的能力,取消冷热队列容量阈值限制,两个队列采用竞争机制,并引入ARC(Adaptive Replacement Cache)算法中预测机制,提高缓存命中率,增强算法灵活性和适应性。3)动态改变替换关键因素:针对LRFU算法及其自适应算法中应对线性访问模式的不足,结合局部性定量分析模型和ARC算法中动态调整思想,判断出当前访问模式,动态改变替换关键因素,提高缓存命中率。实验数据表明:改进策略在线性、概率和强局部访问模式下都具有较好的的适应性,提高了缓存整体命中率。
【关键词】：缓存策略 数据访问模式 局部性 竞争机制 预测机制
【学位授予单位】：安徽工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP333
【目录】：

• 摘要4-5
• Abstract5-9
• 第一章 绪论9-13
• 1.1 研究背景及意义9
• 1.2 国内外研究现状9-11
• 1.3 本文研究内容11
• 1.4 论文的组织结构11-13
• 第二章 相关研究13-20
• 2.1 缓存结构13-15
• 2.1.1 Cache存储体13-14
• 2.1.2 Cache地址转换部件14-15
• 2.1.3 Cache替换部件15
• 2.2 缓存策略的重要性15
• 2.3 提升缓存性能的方法15-18
• 2.3.1 降低缺失代价16-17
• 2.3.2 减少数据块命中时间17
• 2.3.3 提升缓存命中率17-18
• 2.4 局部性原理18-19
• 2.5 本章小结19-20
• 第三章 经典算法与LRFU自适应算法的研究20-31
• 3.1 基于Recency的替换策略20-21
• 3.1.1 LRU算法20-21
• 3.1.2 CLOCK算法21
• 3.1.3 MRU算法21
• 3.2 基于Frecency的替换策略21-22
• 3.2.1 LFU算法21-22
• 3.2.2 FBR算法22
• 3.3 基于Recency和Frecency平衡策略的算法22-29
• 3.3.1 ARC算法22-24
• 3.3.2 LRFU算法24-25
• 3.3.3 A-LRFU算法25-26
• 3.3.4 p-LRFU算法26-27
• 3.3.5 LA-LRFU算法27-29
• 3.4 改进的缓存替换策略29-30
• 3.5 本章小结30-31
• 第四章 基于改进策略的LRFU自适应算法设计31-45
• 4.1 ILA-LRFU算法31-35
• 4.1.1 ILA-LRFU算法基本原理31-33
• 4.1.2 ILA-LRFU运行方式33-34
• 4.1.3 算法复杂度34-35
• 4.2 AI-LRFU算法35-39
• 4.2.1 AI-LRFU算法基本原理35-37
• 4.2.2 AI-LRFU运行方式37-38
• 4.2.3 算法复杂度38-39
• 4.3 实验有效性分析39-44
• 4.3.1 实验环境设定39-40
• 4.3.2 实验工作负载40
• 4.3.3 在线性访问模式下的算法表现40-41
• 4.3.4 在强局部访问模式下的算法表现41-42
• 4.3.5 在概率访问模式下的算法表现42-43
• 4.3.6 在混合访问模式下的算法表现43-44
• 4.4 本章小结44-45
• 第五章 工作总结与展望45-47
• 5.1 总结45
• 5.2 展望45-47
• 参考文献47-50
• 在学研究成果50-51
• 致谢51

【相似文献】

中国期刊全文数据库 前10条

1 冯舜玺;;新书推荐:《算法分析导论》[J];计算机教育;2006年05期

2 张力,慕晓冬;计算机算法分析浅谈[J];武警工程学院学报;2002年04期

3 马安光;;飞弹问题的算法分析——2003年第10期题解[J];程序员;2003年12期

4 苏运霖;;《算法分析导论》评介[J];计算机教育;2006年07期

5 朱力强;;培养学生创新思维与能力的算法分析案例[J];计算机与信息技术;2007年11期

6 汪菊琴;;几种常见特殊方阵的算法分析与实现[J];无锡职业技术学院学报;2009年05期

7 李涵;;“算法分析与设计”课程教学改革和实践[J];中国电力教育;2010年16期

8 刘宁;管涛;;浅析案例教学法在算法分析与设计课程中的应用[J];科技风;2011年07期

9 胡峰;王国胤;;“算法分析与设计”教学模式探索[J];当代教育理论与实践;2011年12期

10 赵娟;;浅析启发式教学法在《算法分析与设计》课程中的应用[J];福建电脑;2012年06期

中国重要会议论文全文数据库 前10条

1 俞洋;田亚菲;;一种新的变步长LMS算法及其仿真[A];通信理论与信号处理新进展——2005年通信理论与信号处理年会论文集[C];2005年

2 周颢;刘振华;赵保华;;构造型的D~2FA生成算法[A];中国通信学会通信软件技术委员会2009年学术会议论文集[C];2009年

3 赖桃桃;冯少荣;张东站;;一种基于划分和密度的快速聚类算法[A];第二十五届中国数据库学术会议论文集（一）[C];2008年

4 刘远新;邓飞其;罗艳辉;舒添慧;;ERP柔性平台下物流运输配送系统算法分析[A];第二十六届中国控制会议论文集[C];2007年

5 王树西;白硕;姜吉发;;模式合一的“减首去尾”算法[A];第二届全国学生计算语言学研讨会论文集[C];2004年

6 王万青;张晓辉;;改进的A~*算法的高效实现[A];2009全国测绘科技信息交流会暨首届测绘博客征文颁奖论文集[C];2009年

7 孙焕良;邱菲;刘俊岭;朱叶丽;;IncSNN——一种基于密度的增量聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

8 韩建民;岑婷婷;于娟;;实现敏感属性l-多样性的l-MDAV算法[A];第二十七届中国控制会议论文集[C];2008年

9 张悦;尤枫;赵瑞莲;;利用蚁群算法实现基于程序结构的主变元分析[A];第五届中国测试学术会议论文集[C];2008年

10 王旭东;刘渝;邓振淼;;正弦波频率估计的修正Rife算法及其FPGA实现[A];全国第十届信号与信息处理、第四届DSP应用技术联合学术会议论文集[C];2006年

中国重要报纸全文数据库 前1条

1 科文;VIXD算法分析Web异常[N];中国计算机报;2008年

中国博士学位论文全文数据库 前10条

1 魏哲学;样本断点距离问题的算法与复杂性研究[D];山东大学;2015年

2 刘春明;基于增强学习和车辆动力学的高速公路自主驾驶研究[D];国防科学技术大学;2014年

3 张敏霞;生物地理学优化算法及其在应急交通规划中的应用研究[D];浙江工业大学;2015年

4 李红;流程挖掘算法研究[D];云南大学;2015年

5 盛歆漪;粒子群优化算法及其应用研究[D];江南大学;2015年

6 黄磊;高动态环境捷联惯导信号处理及高精度姿态速度算法研究[D];南京航空航天大学;2015年

7 刘新旺;多核学习算法研究[D];国防科学技术大学;2013年

8 于滨;城市公交系统模型与算法研究[D];大连理工大学;2006年

9 曾国强;改进的极值优化算法及其在组合优化问题中的应用研究[D];浙江大学;2011年

10 肖永豪;蜂群算法及在图像处理中的应用研究[D];华南理工大学;2011年

中国硕士学位论文全文数据库 前10条

1 黄厦;基于改进蚁群算法的柔性作业车间调度问题研究[D];昆明理工大学;2015年

2 李平;基于Hadoop的信息爬取与舆情检测算法研究[D];昆明理工大学;2015年

3 赵官宝;基于位表的关联规则挖掘算法研究[D];昆明理工大学;2015年

4 殷文华;移动容迟网络中基于社会感知的多播分发算法研究[D];内蒙古大学;2015年

5 徐翔燕;人工鱼群优化算法及其应用研究[D];西南交通大学;2015年

6 李德福;基于小世界模型的启发式寻路算法研究[D];华中师范大学;2015年

7 郑海彬;一种面向MAPREDUCE的DATASHUFFLE的优化方法[D];苏州大学;2015年

8 赵晓寒;轮换步长PSO算法及SMVSC参数优化[D];沈阳理工大学;2015年

9 安丰洋;基于无线网络的广播算法研究[D];曲阜师范大学;2015年

10 李智明;基于改进FastICA算法的混合语音盲分离[D];上海交通大学;2015年

，

本文编号：563178