A short proof of optimality for the MIN cache replacement al
更新时间:2023-04-18 04:29:01 阅读量: 实用文档 文档下载
- 阿根廷推荐度:
- 相关推荐
A Short Proof of Optimality for
the MIN Cache Replacement Algorithm
Benjamin Van Roy
Stanford University
November 10,2006
Abstract
The MIN algorithm is an of?ine strategy for deciding which item to replace when writing a new item to a cache.Its optimality was ?rst established by Mattson,Gecsei,Slutz,and Traiger [2]through a lengthy analysis.We provide a short and elementary proof based on a dynamic programming argument.
Keywords:analysis of algorithms,on-line algorithms,caching,paging 1The MIN Algorithm
Consider the management of a cache over T time periods given advance knowl-edge of requests ω0,ω1,...,ωT ?1from a set ?of items stored in slower memory.Let S t ??denote the set of items stored in the cache just before ωt is requested.If ωt ∈S t then S t +1=S t .Otherwise,a decision must be made to evict one item from the cache,which is replaced by ωt .The objective is to maximize the number of hits:P T
?1t =01(ωt ∈S t ).
The MIN algorithm chooses to evict an item in the cache whose next request occurs furthest in the future.If there are multiple items that will never again be requested one of them is chosen arbitrarily.Mattson,Gecsei,Slutz,and Traiger [2]establish that this algorithm is optimal.1However,their proof is somewhat long and complicated.The textbook Randomized Algorithms [3]offers an excellent ac-count of several cache replacement algorithms and their analyses.In the case of the MIN algorithm,the authors cite the optimality result of [2]without providing the proof,which they mention to be “nontrivial.”Here we offer a short and elementary proof based on a dynamic programming argument.
1In
[2],this algorithm is referred to as the OPT algorithm.In that work,the term MIN identi?es another algorithm originally proposed in [1].1
2Proof of Optimality
Let J t(S t)denote the maximum possible number of hits to occur starting with the t th request.The dynamic programming recursion takes the form
J t(S t)=1(ωt∈S t)+max
S t+1∈U t(S t)
J t+1(S t+1),for t U t(S t)={S?S t∪ωt:ωt∈S,|S|=|S t|}, is the set of possible successive states.The state S t+1∈U t(S t)is an optimal choice if and only if it attains the maximum in the above equation. Denote the time of an item’s next request byτt(ω)=min{t≤z d t(S,S )=min h∈matchings ?? ?{ω∈S|τt(ω)>τt(h(ω))} ?? ?. This is the minimum among matchings of the number of items in S requested after matched items in S . The MIN algorithm evicts the item to be requested furthest in the future. Hence,if S t+1is chosen by the MIN algorithm and Z∈U t(S t)is some other feasible choice then d t+1(S t+1,S )≤d t+1(Z,S )for any cache state S .In other words,S t+1∈argmin Z∈U t(S t)d t+1(Z,S )for all S . The following lemma shows how d t can be used to bound differences among values of cache states. Lemma1.J t(S )?J t(S)≤d t(S,S )for all t≤T and S,S ??with |S|=|S |. Proof:Since J T(S)=J T(S )=0and d T(S,S )=0,the result holds for t=T.We proceed by weak induction.Fix t Let S t=S and S t=S .Let S t+1∈U t(S t)be chosen by an optimal strategy.Let S t+1∈U t(S t)be chosen by the MIN algorithm,and note that this implies S t+1∈argmin Z∈U t(S t)d t+1(Z,S t+1).We study the relationship be- tween d t(S t,S t)and d t+1(S t+1,S t+1)in four cases: Case1:Both S t and S t are hit byωt.Neither cache state changes,so d t+1(S t+1,S t+1)= d t(S t,S t). Case2:Neither S t nor S t are hit byωt.If S t evicts an item,S t can evict the same item.It follows that d t+1(S t+1,S t+1)≤d t(S t,S t). Case3:Only S t is hit byωt.S t evicts an item and at best this improves its relative standing by1;that is,d t+1(S t+1,S t+1)≤d t(S t,S t)+1. Case4:Only S t is hit byωt.S t was previously disadvantaged relative to S t by not holdingωt but now by replacing the item to be requested furthest in the future withωt,this disadvantage vanishes.Hence,d t+1(S t+1,S t+1)≤d t(S t,S t)?1. These four relations together imply that d t+1(S t+1,S t+1)≤d t(S t,S t)+1(ωt∈S t)?1(ωt∈S t). 2 Using this relation,the dynamic programming recursion,and our inductive hy-pothesis,we obtain J t(S t)=1(ωt∈S t)+J t+1(S t+1) ≤1(ωt∈S t)+d t+1(S t+1,S t+1)+J t+1(S t+1) ≤1(ωt∈S t)+d t(S t,S t)+J t+1(S t+1) J t+1(Z)+d t(S t,S t) ≤1(ωt∈S t)+max Z∈U t(S t) =J t(S t)+d t(S t,S t). 2 Given S t,let S t+1be a successive cache state selected by the MIN algo-rithm and let S t+1be a successive cache state selected by an optimal strategy. Since S t+1minimizes d t+1(S t+1,S t+1)over the set U t(S t)which contains S t+1, d t+1(S t+1,S t+1)=0.By the optimality of S t+1and Lemma1, 0≤J t+1(S t+1)?J t+1(S t+1)≤d t+1(S t+1,S t+1). It follows that J t+1(S t+1)=J t+1(S t+1),and therefore,a decision made by the MIN algorithm is optimal. Acknowledgments Balaji Prabhakar introduced the author to the MIN algorithm,its history,and the interest in obtaining a simpler proof of optimality. References [1]L.A.Belady.A study of replacement algorithms for virtual storage computers. IBM Systems Journal,5(2):78–101,1966. [2]R.L.Mattson,J.Gecsei,D.R.Slutz,and I.L.Traiger.Evaluation techniques for storage hierarchies.IBM Systems Journal,9(2):78–117,1970. [3]R.Motwani and P.Raghavan.Randomized Algorithms.Cambridge University Press,1995. 3
正在阅读:
A short proof of optimality for the MIN cache replacement al04-18
公路工程施工招标文件05-05
《窗边的小豆豆》答案测试题阅读试题10-09
人教版数学七年级上全册导学案(有理数、整式的加减、一元一次方06-06
浅谈体育教学对中学生健康人格的培养04-22
安全生产管理题库(三类人员考试试题)04-30
任务驱动型作文:该不该给老人让座?07-08
眩晕分型03-24
2014年关心下一代工作总结05-13
安庆市蔬菜种植农场数据报告2018版03-06
- 1简述影响Cache命中率的因素
- 2A short Introduction to Algorithm Engineering CSSS2009
- 3过渡金属(Fe,Al,Cu)
- 4Testing Mass Varying Neutrino With Short Gamma Ray Burst
- 5简述影响Cache命中率的因素
- 6Testing Mass Varying Neutrino With Short Gamma Ray Burst
- 7Al的声子谱计算
- 8AL-7480简易编程 - 图文
- 9AL2O3 - 图文
- 10L1 Cache and TLB Enhancements to the RAMpage Memory Hierarchy
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- replacement
- optimality
- short
- proof
- cache
- MIN
- al
- 【新版】冀教版初中八年级语文上册《紫藤萝瀑布》学案2
- GSL1688_DataSheet_Chinese_RevA1.2
- 物流出纳一周工作总结(同名28433)
- 2022年党员干部组织生活会对照检查材料汇编四(政治功能四个意识
- 2022届临沂市高三上学期期中考试地理试题及答案 精品
- Excel_基础应用_办公技巧大全_高级技能_{史上最全教程}
- 高速线材焊接机多少钱一台 高速线材焊接机厂商 福威特焊机
- 2022年重庆省中西医执业医师针灸学2015-04-17模拟试题
- 2022年江西农业大学园林与艺术学院702化学之分析化学考研核心题
- 材料作文宁静与噪音讲评学案
- 最新人教版一年级上册数学第8单元测试卷
- 浙教版科学新版九年级上册《简单机械》第一课时优教教案 新版
- 人教课标版高中英语必修一 Unit3 Extensive reading 名师
- 4S店管理系统的使用
- 2015高中英语 Book3Module2学案2 外研版必修3
- 新员工入职报到流程
- 2022年综治工作计划格式文档
- 佛说护诸童子陀罗尼经
- 19-20学年新教材高中英语UNIT5MUSICSectionⅢDiscoveringUsefulS
- 2006年高考语文试题及答案(山东卷)