Xeon CPU（E5-2603）的反向内存预取

Question

Xeon CPU（E5-2603）的反向内存预取

performancecachingoptimizationx86intel

5

在 Xeon CPU（E5-2603）中，反向内存预取是否与正向内存预取一样快？

我想实现一个需要对数据进行正向循环和反向循环的算法。

由于每次迭代都需要上一次迭代的结果，我不能颠倒循环的顺序。

- R zu

桑迪桥架构：请参阅https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf的第45页。 - R zu

数据预取：p.59（p.2-29） - R zu

在Haswell/Skylake上，当我让一个循环向前执行，然后让下一个循环反向遍历相同的数据时，对于那些大小略大于缓存容量的数据，我得到了不错的结果。改变方向意味着你会回到之前循环中已经在缓存中的热数据。 - Peter Cordes

1

如果您反复触及1GB的工作集，请考虑使用缓存阻塞：在128kiB左右（L2大小的一半）上运行多个步骤/通过，以便每次通过都保持在L2中。请搜索Google缓存阻塞/循环平铺以获取更多信息。（在《每个程序员都应该了解的内存》中有一个瓷砖矩阵乘法的示例）。 - Peter Cordes

gcc支持使用-fprefetch-loop-arrays进行数据预取。此外，您还可以在代码中手动使用可移植的__builtin_prefetch进行预取。 - Hadi Brais

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hadi Brais · Accepted Answer

你可以运行实验来确定数据预取器是否能够处理前向顺序访问和后向顺序访问。我有一款Haswell CPU，所以预取器可能与你的CPU（Sandy Bridge）不同。

下图显示了在四种不同方式下遍历数组时每个元素访问的可观察延迟时间：

- 数组按顺序初始化并按相同方式遍历。我将此模式称为“forfor”。 - 数组按顺序初始化并按反向顺序（从最后一个元素到第一个元素）顺序遍历。我将此模式称为“forback”。 - 数组按反向顺序初始化并按相同方式遍历。我将此模式称为“backback”。

x轴表示元素索引，y轴表示TSC周期内的延迟时间。我已经配置我的系统，使得TSC周期大约等于核心周期。我绘制了两次名为“forfor1”和“forfor2”的“forfor”运行的测量值。平均每个元素的延迟如下：

forfor1：9.9个周期。
forfor2：15个周期。
forback：35.8个周期。
backback：40.3个周期。

L1访问延迟对任何测量噪声都非常敏感。L2访问延迟平均应该为12个周期，但由于几个周期的噪声，我们仍可能得到L1命中的12个周期延迟。在第一次运行forfor时，大多数延迟为4个周期，这清楚地表明了L1命中。在第二次运行forfor时，大多数延迟为8或12个周期。我认为这些也可能是L1命中。在这两种情况下，都有一些L3命中和少量主存访问。对于forback和backback，我们可以看到大多数延迟是L3命中。这意味着L3预取器能够处理正向和反向遍历，但无法处理L1和L2预取器。

然而，这些访问是快速连续地进行的，之间基本上没有计算。因此，如果L2预取器尝试向后预取，可能会得到数据太晚，因此仍会产生类似L3的延迟。

请注意，在两次遍历数组之间我没有清除缓存，因此第一次遍历可能会影响第二次遍历中测量的延迟。

这是我用来进行测量的代码。

/* compile with gcc at optimization level -O3 */
/* set the minimum and maximum CPU frequency for all cores using cpupower to get meaningful results */ 
/* run using "sudo nice -n -20 ./a.out" to minimize possible context switches, or at least use "taskset -c 0 ./a.out" */
/* make sure all cache prefetchers are enabled */
/* preferrably disable HT */
/* this code is Intel-specific */
/* see the note at the end of the answer */

#include <stdint.h>
#include <x86intrin.h>
#include <stdio.h>

// 2048 iterations.
#define LINES_SIZE 64
#define ITERATIONS 2048 * LINES_SIZE
// Forward
#define START 0
#define END ITERATIONS
// Backward
//#define START ITERATIONS - LINES_SIZE
//#define END 0
#if START < END
#define INCREMENT i = i + LINES_SIZE
#define COMP <
#else
#define INCREMENT i = i - LINES_SIZE
#define COMP >=
#endif

int main()
{
  int array[ ITERATIONS ];
  int latency[ ITERATIONS/LINES_SIZE ];
  uint64_t time1, time2, al, osl; /* initial values don't matter */

  // Perhaps necessary to prevents UB?
  for ( int i = 0; i < ITERATIONS; i = i + LINES_SIZE )
  {
     array[ i ] = i; 
  }

  printf( "address = %p \n", &array[ 0 ] ); /* guaranteed to be aligned within a single cache line */

  // Measure overhead.
  _mm_mfence();                      
  _mm_lfence();                      /* mfence and lfence must be in this order + compiler barrier for rdtsc */
  time1 = __rdtsc();                 /* set timer */
  _mm_lfence();                      /* serialize rdtsc with respect to trailing instructions + compiler barrier for rdtsc */
  /* no need for mfence because there are no stores in between */
  _mm_lfence();                      /* mfence and lfence must be in this order + compiler barrier for rdtsc */
  time2 = __rdtsc();
  _mm_lfence();                      /* serialize rdtsc with respect to trailing instructions */
  osl = time2 - time1;

  // Forward or backward traversal.
  for ( int i = START; i COMP END; INCREMENT )
  {

     _mm_mfence();                      /* this properly orders both clflush and rdtsc */
     _mm_lfence();                      /* mfence and lfence must be in this order + compiler barrier for rdtsc */
     time1 = __rdtsc();                 /* set timer */
     _mm_lfence();                      /* serialize rdtsc with respect to trailing instructions + compiler barrier for rdtsc */
     int temp = array[ i ];             /* access array[i] */
     _mm_lfence();                      /* mfence and lfence must be in this order + compiler barrier for rdtsc */
     time2 = __rdtsc();
     _mm_lfence();                      /* serialize rdtsc with respect to trailing instructions */
     al = time2 - time1;

     printf( "array[ %i ] = %i \n", i, temp );         /* prevent the compiler from optimizing the load */
     latency[i/64] = al - osl;

  }

  // Output measured latencies.
  for ( int i = 0; i < ITERATIONS/LINES_SIZE; ++i )
  {
     printf( "%i \n", latency[i] );
  }

  return 0;
}

这些实验的目的是测量个别访问延迟，以确定每个访问是从哪个缓存级别提供服务的。然而，由于存在LFENCE指令，测量可能包括在管道的其他阶段中所需的负载指令延迟。此外，编译器将一些ALU指令放置在计时区域，因此测量可能会受到这些指令的影响（可以通过用汇编语言编写代码来避免这种情况）。这可能使得难以区分命中L1和命中L2的访问之间的差异。例如，一些L1延迟测量报告为8个周期。尽管如此，forback和backback测量清楚地显示大多数访问都命中了L3。

如果我们有兴趣测量访问特定内存层次结构的平均延迟，则使用指针追踪可以提供更准确的结果。事实上，这是测量内存延迟的传统方法。

如果您以难以预测的模式访问大量数据，特别是在L2或L3上的硬件预取器，软件预取可以非常有益。但是，一般来说，正确实现软件预取很困难。此外，我得到的测量结果显示，L3预取器可以向前和向后预取。如果您在内存访问和计算方面具有良好的并行性，则OoO执行可以隐藏相当比例的L3访问延迟。

程序正确运行的重要提示：事实证明，如果我没有使用输出重定向运算符>将所有输出重定向到文件中，即所有输出都将打印在终端上，所有测量的延迟将接近L3命中延迟。原因是printf在每次迭代中被调用，污染了大量的L1和L2缓存。所以一定要使用>运算符。您也可以像this和this答案中建议的那样使用(void)*((volatile int*)array + i)而不是int tmp = array[i]，这会更加可靠。