Xeon 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 访问延迟。

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

Xeon CPU (E5-2603) 向后内存预取

Xeon CPU (E5-2603) backward memory prefetch

optimization

performance

x86

caching

intel