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

Question

后向内存预取是否与Xeon CPU（E5-2603）中的前向内存预取一样快？

我想实现一种算法，该算法既需要数据的正向循环，也需要反向循环。

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

谢谢。

Answer 1

您可以运行实验来确定数据预取程序是否能够处理前向顺序访问和后向顺序访问。我有一个Haswell CPU，所以prefetchers可能与你在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回答中提出的那样。那将更加可靠。