performance - 至强 CPU (E5-2603) 后向内存预取

Question

在 Xeon CPU (E5-2603) 中，向后内存预取是否与前向内存预取一样快？

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

由于每次迭代都需要上次迭代的结果，因此我无法颠倒循环的顺序。

谢谢你。

Answer 1

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

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

数组按前向顺序初始化，然后以相同方式遍历。我将此模式称为 forfor .

数组在前向顺序初始化，然后在后向(从最后一个元素到第一个元素)顺序遍历。我将此模式称为 forback .

数组按反向顺序初始化，然后以同样的方式遍历。我将此模式称为 backback .

x 轴代表元素索引，y 轴代表 TSC 周期中的延迟。我已经配置了我的系统，以便 TSC 周期大约等于一个核心周期。我已经绘制了 forfor 的两次运行的测量值叫 forfor1和 forfor2 .每个元素的平均延迟如下:

forfor1 : 9.9 个周期。

forfor2 : 15 个周期。

forback : 35.8 个周期。

backback : 40.3 个周期。

L1 访问延迟对任何测量噪声都特别敏感。 L2 访问延迟应该是 12 cycles平均而言，但由于几个周期的噪声，我们可能仍会获得 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 缓存。所以一定要使用 > 操作符。您也可以使用 (void) *((volatile int*)array + i)而不是 int tmp = array[i]如 this 中提出的和 this回答。那就更靠谱了。