The cost of address translation
The cost of address translation
复制标题
地址转换的成本
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Mehlhorn
中科院分区：
文献类型：
--
作者：
Tomasz Jurkiewicz;K. Mehlhorn
现代计算机不是随机存取机（RAM）。它们具有内存层次结构、多核和虚拟内存。在本文中，我们解决了虚拟内存中的地址转换的计算成本。我们工作的出发点是观察到，在RAM模型或EM模型（外部存储器模型）中的一些简单算法（数组的随机扫描，二进制搜索，堆排序）的分析不能正确预测实际运行时间的增长率。我们提出了VAT模型（虚拟地址转换）来考虑地址转换的成本，并分析了模型中的上述算法和其他算法。预测与测量结果一致。我们还分析了增值税成本的缓存无关算法。
Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of address translation in virtual memory. Starting point for our work is the observation that the analysis of some simple algorithms (random scan of an array, binary search, heapsort) in either the RAM model or the EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms.