缓存感知算法的一个简单示例？

Question

有人可以发布缓存感知算法的任何简单解释吗？有许多链接可用,但这些网站的阅读材料本质上是学术性的,阅读和理解是耗时的.

Answer 1

高速缓存感知算法旨在最小化存储器页面进出处理器的片上存储器高速缓存的移动.我们的想法是避免所谓的"缓存未命中",这会导致处理器在将数据从RAM加载到处理器缓存时停止运行.

在纸面上不太理想的缓存感知算法可以胜过理论上"更快"的传统算法,因为缓存感知算法更有效地使用内存.

显式编码缓存感知算法以利用处理器的缓存行为.有关处理器内存页面大小和"缓存行"的详细信息将编码到算法中.因此,高速缓存感知算法将是高度特定于处理器的.

缓存遗忘算法被编码为以比传统算法更加缓存友好的方式使用存储器,但它不依赖于关于底层硬件的私密细节.

Answer 2

我认为缓存感知算法最简单的例子之一是访问二维数组row-major与column-major.由于二维数组通常作为数组所有行的串联存储在内存中,因此逐行访问它会在适当的时间将适当的数据放入缓存中.但是,当按列主要顺序访问数组时,内存中的大量跳转和缓存未命中都会导致速度大幅下降.

举个例子,这个C++代码:

for (int i = 0; i < MAX_N; ++i) {
  for (int j = 0; j < MAX_N; ++j) {
   a[i][j] = 10;
  }
}

在我的机器上运行速度比我交换所访问单元格的索引快了3-4倍(即访问a[j][i]).