专利详情

专利名称	随机替换缓存的高效模拟方法
申请号	CN201010233592.3	专利类型	发明专利
公开（公告）号	CN101916229A	公开（授权）日	2010.12.15
申请（专利权）人	中国科学院计算技术研究所	发明（设计）人	周舒畅
主分类号	G06F12/08(2006.01)I	IPC主分类号	G06F12/08(2006.01)I
专利有效期	随机替换缓存的高效模拟方法至随机替换缓存的高效模拟方法	法律状态	实质审查的生效
说明书摘要	本发明有关于一种随机替换缓存的高效模拟方法，包括：步骤一，通过对E(Xi)＝1-E((1-1/M)Zi)的近似，得到估算公式(1)或估算公式(2)：E(Xi)≈1-(1-1/M)E(Zi)(1)E(Xi)≈1-∏j(1+E(Xj)/(M-1))-1(2)步骤二，根据由估算公式(1)或估算公式(2)得到的E(Xi)计算访存序列中每点的命中概率1-E(Xi)；其中，Xi为缺失事件的指标随机变量，E(Xi)为Xi的数学期望，M为缓存的相联度，Xj属于Xi的重用窗口，即从ai的值上一次出现到i之间的所有缺失事件。如果访存序列中点ai的值此前未出现过，则Zi＝∞；如果ai的值此前出现过，则Zi＝从ai的值上一次出现到i之间的缺失事件次数。本发明通过使用概率模型的估算公式，可以通过一轮模拟得到一访存序列中每点的命中概率的估计。