至强 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 个周期，但由于周期数较少的噪声，我们可能仍会获得 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]