Efficient Calculation of Expected Miss Ratios in the Independent Reference Model
Efficient Calculation of Expected Miss Ratios in the Independent Reference Model
复制标题
独立参考模型中预期缺失率的高效计算
DOI：
10.1137/0207025
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
T. G. Price
中科院分区：
文献类型：
--
作者：
Ronald Fagin;T. G. Price
在程序行为的独立参考模型中，预期 FIFO（“先进先出”）和预期 LRU（“最近最少使用”）未命中率的 King 公式均包含指数数量的项（非常粗略 $n^{{\text{CAP}}} $，其中 n 是页数，CAP 是主存容量）。因此，在简单的算法下，这些公式在计算上是难以处理的。我们提出了一种算法，该算法既高效（有 $O(n \cdot {\text{CAP}})$ 加法、乘法和除法），又可证明数值稳定，用于计算预期的 FIFO 未命中率。对于 LRU，我们提出了一种基于 urn 模型的有效方法，用于获得预期 LRU 未命中率的无偏估计（该方法需要 $O(n \cdot {\text{CAP}})$ 添加和比较，以及 $O({\text{CAP}})$ 除法和随机数生成）。
In the independent reference model of program behavior, King’s formulas for the expected FIFO (“first-in-first-out”) and expected LRU (“least-recently-used”) miss ratios each contain an exponential number of terms (very roughly $n^{{\text{CAP}}} $, where n is the number of pages and CAP is the capacity of main memory). Hence, under the straightforward algorithms, these formulas are computationally intractable. We present an algorithm which is both efficient (there are $O(n \cdot {\text{CAP}})$ additions, multiplications, and divisions) and provably numerically stable, for calculating the expected FIFO miss ratio. In the case of LRU, we present an efficient method, based on an urn model, for obtaining an unbiased estimate of the expected LRU miss ratio (the method requires $O(n \cdot {\text{CAP}})$ additions and comparisons, and $O({\text{CAP}})$ divisions and random number generations).