8

我有这样的循环

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;

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

4

4 回答 4

9

仅适用于 GCC：

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

prefetch_address可以无效，不会有段错误。如果与当前位置之间的差异太小prefetch_address，则可能没有效果甚至减速。尝试将其设置为至少提前 1k。

于 2013-01-09T21:53:09.617 回答
7

首先，我假设这tab是一个大型二维数组，例如静态数组（例如，int tab[1024*1024][1024*1024]）或动态分配的数组（例如，int** tab和后面malloc的 s）。在这里，您希望从tab缓存中预取一些数据以减少执行时间。

简单地说，我认为您不需要手动将任何预取插入到您的代码中，其中对 2D 数组执行简单的缩减。如果必要且有利可图，现代 CPU 将进行自动预取。

对于这个问题，你应该知道两个事实：

(1) 您已经在利用tab最内层循环内部的空间局部性。一旦tab[i][0]被读取（在缓存未命中或页面错误之后），来自tab[i][0]to的数据tab[i][15]将在您的 CPU 缓存中，假设缓存行大小为 64 字节。

(2) 但是，当代码在行中遍历时，即tab[i][M-1]到tab[i+1][0]，极有可能发生冷缓存未命中，特别是当tab是动态分配的数组时，其中每一行都可以以分段的方式分配。但是，如果数组是静态分配的，则每一行将在内存中连续定位。

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

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

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

如果您在大型 2D 数组上进行更昂贵的计算，则有许多对缓存更友好的替代算法。一个值得注意的例子是blocked(titled) matrix multiply。一个简单的矩阵乘法会遭受很多缓存未命中，但阻塞算法通过计算适合缓存的小子集显着减少缓存未命中。请参阅类似的一些参考资料。

于 2013-01-10T01:07:08.133 回答
4

最简单/最便携的方法是简单地读取一些数据，每个缓存行字节分开。假设 tab 是一个合适的二维数组，你可以：

char *tptr = (char *)&tab[0][0];
tptr += 64;
char temp;
volatile char keep_temp_alive;
for(int i = 0; i < N; i++)
{
    temp += *tptr;
    tptr += 64;
    for(j = 0; j < M; j++)
        count += tab[i][j];
}
keep_temp_alive = temp;

类似的东西。但是，它确实取决于： 1. 您最终不会在分配的内存之外读取 [太多]。2. J 循环并不比 64 字节大多少。如果是，您可能希望temp += *tptr; tptr += 64;在循环的开头添加更多步骤。

after 循环对于keep_temp_alive防止编译器完全删除 temp 作为不必要的负载至关重要。

不幸的是，我编写通用代码的速度太慢，无法建议内置指令，这点归功于 Leonid。

于 2013-01-09T21:56:50.517 回答
0

该__builtin_prefetch指令非常有用，但特定于 clang/gcc。如果您要编译到多个编译器目标，我很幸运地使用了 x86 内在函数_mm_prefetch以及 clang 和 MSVC。

https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm_prefetch

于 2020-12-18T06:50:09.017 回答