推荐Tojot · 2016-08
“Feel free to take a look at a free copy at The Cost of Address Translation where we establish the VAT cost model.”
推荐自己的论文,其中建立了虚拟地址转换的成本模型
提出 VAT 模型,刻画虚拟内存地址转换对算法耗时的影响
论文指出现代计算机并非随机访问机,而是有内存层次、多核和虚拟内存。作者的出发点是:对数组随机扫描、二分查找、堆排序等简单算法,用 RAM 模型或外存(EM)模型的分析无法正确预测实际运行时间的增长率。为此提出 VAT(虚拟地址转换)模型来计入地址转换的代价,并用它分析上述算法及其他算法,预测与测量结果吻合,还分析了缓存无关算法的 VAT 代价。
HN 上的人引用它说明虚拟地址转换和 TLB 开销会让 C 数组访问呈现类似 log(N) 的行为,也被推荐为这一话题的入门材料。
“Feel free to take a look at a free copy at The Cost of Address Translation where we establish the VAT cost model.”
“Check out The Cost of Address Translation for some introduction to the topic.”
“as demonstrated in the following work by Jurkiewicz & Mehlhorn: The Cost of Address Translation”
“A paper came up on HN recently that showed that C arrays could have log(N) behavior for individual accesses if you antagonized the TLB cache hard enough.”