C++如何强制预取数据缓存？(数组循环)

Question

我有这样的循环

start = __rdtsc();
unsigned long long count = 0;
for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++)
        count += tab[i][j];
stop = __rdtsc();
time = (stop - start) * 1/3;

需要检查预取数据如何影响效率.如何在计算之前强制从内存中预取一些值到缓存中？

Answer 1

仅适用于GCC:

__builtin_prefetch((const void*)(prefetch_address),0,0);

prefetch_address可能无效,不会有段错误.如果prefetch_address当前位置之间的差异太小,则可能没有效果甚至减速.尽量设置至少1k.

Answer 2

首先，我假设这tab是一个大型2D数组，例如静态数组（例如int tab[1024*1024][1024*1024]）或动态分配的数组（例如，int** tab以及mallocs）。在这里，您要从tab缓存中预取一些数据，以减少执行时间。

简而言之，我认为您无需在代码中手动插入任何预取，只需对2D数组执行简单的还原即可。如果有必要且有利可图，现代CPU将自动进行预取。

您应该了解此问题的两个事实：

（1）您已经在利用tab最内部循环内部的空间局部性。一旦tab[i][0]被读取（高速缓存未命中或页面故障后），从数据tab[i][0]到tab[i][15]会在你的CPU缓存，假设高速缓存行大小为64个字节。

（2）但是，当代码在行中遍历时，即tab[i][M-1]to tab[i+1][0]，极有可能发生冷缓存未命中，尤其tab是在动态分配的数组中，可以以碎片方式分配每一行时。但是，如果该数组是静态分配的，则每一行将连续地位于内存中。

因此，仅当您先读取（1）下一行的第一项和（2）j + CACHE_LINE_SIZE/sizeof(tab[0][0])提前时，预取才有意义。

您可以通过__builtin_prefetch在上部循环中插入预取操作（例如）来实现。但是，现代编译器可能并不总是发出这种预取指令。如果确实要这样做，则应检查生成的二进制代码。

但是，正如我所说，我不建议您这样做，因为现代CPU大多会自动进行预取，而自动预取将大大超过您的手动代码。例如，像Ivy Bridge处理器这样的Intel CPU，有多个数据预取器，例如预取到L1，L2或L3缓存。（尽管如此，我认为移动处理器并没有花哨的数据预取器）。一些预取器将加载相邻的缓存行。

如果您在大型2D阵列上进行更昂贵的计算，则有许多对缓存更友好的替代算法。一个值得注意的例子是被阻塞（标题）的矩阵乘法。朴素矩阵乘法会遭受很多高速缓存未命中的问题，但是阻塞算法通过计算适合高速缓存的小子集来显着减少高速缓存未命中。看到这样一些参考这个。