performance - 我如何从预取内在函数中获得可衡量的好处？

标签 performance x86-64 sse simd prefetch

在 x86_64 上使用 gcc 4.4.5(是的......我知道它很旧)。出于兼容性原因，仅限于 SSE2(或更早版本)说明。

我有我认为应该从预取中获得巨大好处的教科书案例。我有一个 32 位元素的数组(“A”)，它们不是(也不能)按顺序排列。这些 32 位元素是 __m128i 数据的更大数据数组 (“D”) 的索引。对于“A”的每个元素，我需要从“D”中的适当位置获取 __m128i 数据，对其执行操作，然后将其存储回“D”中的相同位置。实际上，D 中的每个“条目”都是“SOME_CONST” __m128i 的大。因此，如果 A 中的值为“1”，则 D 中的索引为 D[1 * SOME_CONST]。

由于“A”中的连续元素几乎永远不会指向“D”中的连续位置，我倾向于认为硬件预取器会挣扎或无法完成任何有用的事情。

但是，我可以很容易地预测我接下来将访问哪些位置，只需在“A”中向前看即可。废话太多了……这里有一些代码。我对数据执行的操作是取 __m128i 的低 64 位并将其克隆到相同的高 64 位。首先是基本循环，没有多余的装饰......

// SOME_CONST is either 3 or 4, but this "operation" only needs to happen for 3

for ( i=0; i<arraySize; ++i )
{
  register __m128i *dPtr = D + (A[i] * SOME_CONST);
  dPtr[0] = _mm_shuffle_epi32( dPtr[0], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr[1] = _mm_shuffle_epi32( dPtr[1], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr[2] = _mm_shuffle_epi32( dPtr[2], 0 | (1<<2) | (0<<4) | (1<<6) );

  // The immediate operand selects:
  // Bits 0-31   = bits 0-31
  // Bits 32-63  = bits 32-63
  // Bits 64-95  = bits 0-31
  // Bits 96-127 = bits 32-63

  // If anyone is more clever than me and knows of a better way to do this in SSE2,
  //  bonus points.  ;-)
}

我已经尝试了许多不同的方法来在其中添加预取内在函数，但都没有带来任何加速。例如，我尝试展开循环以获得 2 个甚至 4 个元素的步幅，但它没有帮助......
// Assume the "A" array size is appropriately padded so that overruns don't
//  result in SIGSEGV accessing uninitialized memory in D.

register __m128i *dPtr0, *dPtr1, *dPtr2, *dPtr3, *dPtr4, *dPtr5, *dPtr6, *dPtr7;
dPtr4 = D + (A[0] * SOME_CONST);
dPtr5 = D + (A[1] * SOME_CONST);
dPtr6 = D + (A[2] * SOME_CONST);
dPtr7 = D + (A[3] * SOME_CONST);

for ( i=0; i<arraySize; i+=4 )
{
  dPtr0 = dPtr4;
  dPtr1 = dPtr5;
  dPtr2 = dPtr6;
  dPtr3 = dPtr7;

  dPtr4 = D + (A[i+4] * SOME_CONST);
  _mm_prefetch( dPtr4, _MM_HINT_NTA );
  _mm_prefetch( dPtr4+1, _MM_HINT_NTA ); // Is it needed?  Tried both ways

  dPtr5 = D + (A[i+5] * SOME_CONST);
  _mm_prefetch( dPtr5, _MM_HINT_NTA );
  _mm_prefetch( dPtr5+1, _MM_HINT_NTA ); // Is it needed?  Tried both ways

  dPtr6 = D + (A[i+6] * SOME_CONST);
  _mm_prefetch( dPtr6, _MM_HINT_NTA );
  _mm_prefetch( dPtr6+1, _MM_HINT_NTA ); // Is it needed?  Tried both ways

  dPtr7 = D + (A[i+7] * SOME_CONST);
  _mm_prefetch( dPtr7, _MM_HINT_NTA );
  _mm_prefetch( dPtr7+1, _MM_HINT_NTA ); // Is it needed?  Tried both ways

  dPtr0[0] = _mm_shuffle_epi32( dPtr0[0], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr0[1] = _mm_shuffle_epi32( dPtr0[1], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr0[2] = _mm_shuffle_epi32( dPtr0[2], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr1[0] = _mm_shuffle_epi32( dPtr1[0], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr1[1] = _mm_shuffle_epi32( dPtr1[1], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr1[2] = _mm_shuffle_epi32( dPtr1[2], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr2[0] = _mm_shuffle_epi32( dPtr2[0], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr2[1] = _mm_shuffle_epi32( dPtr2[1], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr2[2] = _mm_shuffle_epi32( dPtr2[2], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr3[0] = _mm_shuffle_epi32( dPtr3[0], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr3[1] = _mm_shuffle_epi32( dPtr3[1], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr3[2] = _mm_shuffle_epi32( dPtr3[2], 0 | (1<<2) | (0<<4) | (1<<6) );
}

那是 4 元素版本，但我也尝试只使用 2 元素，以防数据太多而无法四处晃动。我也尝试使用 _MM_HINT_NTA 和 _MM_HINT_T0。不知何故没有明显的区别。

我还尝试了一个更简单的变体，它只是尝试在预取和使用时间之间放置尽可能多的空间:
#define PREFETCH_DISTANCE 10
// trying 5 overnight, will see results tomorrow...

for ( i=0; i<arraySize; ++i )
{
  register __m128i *dPtrFuture, *dPtr;
  dPtrFuture = D + (A[i + PREFETCH_DISTANCE] * SOME_CONST);
  _mm_prefetch( dPtrFuture, _MM_HINT_NTA );      // tried _MM_HINT_T0 too
  _mm_prefetch( dPtrFuture + 1, _MM_HINT_NTA );  // tried _MM_HINT_T0 too

  dPtr = D + (A[i] * SOME_CONST);
  dPtr[0] = _mm_shuffle_epi32( dPtr[0], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr[1] = _mm_shuffle_epi32( dPtr[1], 0 | (1<<2) | (0<<4) | (1<<6) );
  dPtr[2] = _mm_shuffle_epi32( dPtr[2], 0 | (1<<2) | (0<<4) | (1<<6) );
}

最初我希望这段代码会停顿，但是一旦它进入循环中的“PREFETCH_DISTANCE”，我希望它会看到足够好的速度提升。大多数这些变体在数百万次迭代中导致不超过 0.2 秒的运行时差异，这台特定机器上的总 CPU 时间为 4 分 30 秒(除了我之外，其他机器处于闲置状态)。这些差异似乎与数据中的“噪音”无法区分。

我认为预取应该能够在这里帮助我的假设是否正确？如果是这样，我做错了什么？

感谢所有有用和有趣的想法。

编辑:

我创建了一个真正随机化 A 中数据的人为示例。我使用了从 64MB 到 6400MB 的缓冲区大小。我发现当我对当前 4 个元素执行操作时，展开循环并预先计算接下来 4 个元素的地址，我获得了巨大的 yield 。但是如果我尝试预取，我的运行时间会降低 10 倍以上我预先计算的任何地址。我真的很头疼这个。我的独立设计代码是:
#include <xmmintrin.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#define QUEUE_ELEMENTS    1048576
#define DATA_ELEMENT_SIZE 4 * sizeof( __m128i )
#define DATA_ELEMENTS     QUEUE_ELEMENTS

#define QUEUE_ITERATIONS  100000
#define LOOP_UNROLL_4
#define LOOP_UNROLL_2

#ifdef LOOP_UNROLL_4
  #define UNROLL_CONST 4
#else
  #ifdef LOOP_UNROLL_2
    #define UNROLL_CONST 2
  #else
    #define UNROLL_CONST 1
  #endif
#endif

int main( void )
{
  unsigned long long randTemp;
  unsigned long i, outerLoop;
  unsigned long *workQueue;
  __m128i *data, *dataOrig;
  clock_t timeStamp;

  workQueue = malloc( QUEUE_ELEMENTS * sizeof( unsigned long ) );

  dataOrig = malloc( (DATA_ELEMENTS * DATA_ELEMENT_SIZE) + 2 );
  if ( (unsigned long long) dataOrig & 0xf )
  {
    data = (__m128i *) (((unsigned long long) dataOrig & ~0xf) + 0x10);
    // force 16-byte (128-bit) alignment
  } else data = dataOrig;

  // Not initializing data, because its contents isn't important.

  for ( i=0; i<QUEUE_ELEMENTS; ++i )
  {
    randTemp = (unsigned long long)rand() *
     (unsigned long long) QUEUE_ELEMENTS / (unsigned long long) RAND_MAX;
    workQueue[i] = (unsigned long) randTemp;
  }

  printf( "Starting work...\n" );
  // Actual work happening below... start counting.
  timeStamp = clock();

  for ( outerLoop = 0; outerLoop < QUEUE_ITERATIONS; ++outerLoop )
  {
    register __m128i *dataPtr0, *dataPtr1, *dataPtr2, *dataPtr3;
    register __m128i *dataPtr4, *dataPtr5, *dataPtr6, *dataPtr7;

    #ifdef LOOP_UNROLL_2
      dataPtr4 = data + (workQueue[0] * DATA_ELEMENT_SIZE);
      dataPtr5 = data + (workQueue[1] * DATA_ELEMENT_SIZE);
    #endif
    #ifdef LOOP_UNROLL_4
      dataPtr6 = data + (workQueue[2] * DATA_ELEMENT_SIZE);
      dataPtr7 = data + (workQueue[3] * DATA_ELEMENT_SIZE);
    #endif

    for ( i=0; i<QUEUE_ELEMENTS; i+=UNROLL_CONST )
    {
      #ifdef LOOP_UNROLL_2
        dataPtr0 = dataPtr4;
        dataPtr4 = data + (workQueue[i+4] * DATA_ELEMENT_SIZE);
        // _mm_prefetch( dataPtr4, _MM_HINT_T0 );
        dataPtr1 = dataPtr5;
        dataPtr5 = data + (workQueue[i+5] * DATA_ELEMENT_SIZE);
        // _mm_prefetch( dataPtr5, _MM_HINT_T0 );
      #endif
      #ifdef LOOP_UNROLL_4
        dataPtr2 = dataPtr6;
        dataPtr6 = data + (workQueue[i+6] * DATA_ELEMENT_SIZE);
        // _mm_prefetch( dataPtr6, _MM_HINT_T0 );
        dataPtr3 = dataPtr7;
        dataPtr7 = data + (workQueue[i+7] * DATA_ELEMENT_SIZE);
        // _mm_prefetch( dataPtr7, _MM_HINT_T0 );
      #endif
      #if !defined( LOOP_UNROLL_2 ) && !defined( LOOP_UNROLL_4 )
        dataPtr0 = data + (workQueue[i] * DATA_ELEMENT_SIZE);
      #endif

      _mm_shuffle_epi32( dataPtr0[0], 0 | (1<<2) | (0<<4) | (1<<6) );
      _mm_shuffle_epi32( dataPtr0[1], 0 | (1<<2) | (0<<4) | (1<<6) );
      _mm_shuffle_epi32( dataPtr0[2], 0 | (1<<2) | (0<<4) | (1<<6) );
      // Per original code, no need to perform operation on dataPtrx[3]

      #ifdef LOOP_UNROLL_2
        _mm_shuffle_epi32( dataPtr1[0], 0 | (1<<2) | (0<<4) | (1<<6) );
        _mm_shuffle_epi32( dataPtr1[1], 0 | (1<<2) | (0<<4) | (1<<6) );
        _mm_shuffle_epi32( dataPtr1[2], 0 | (1<<2) | (0<<4) | (1<<6) );
      #endif
      #ifdef LOOP_UNROLL_4
        _mm_shuffle_epi32( dataPtr2[0], 0 | (1<<2) | (0<<4) | (1<<6) );  
        _mm_shuffle_epi32( dataPtr2[1], 0 | (1<<2) | (0<<4) | (1<<6) );  
        _mm_shuffle_epi32( dataPtr2[2], 0 | (1<<2) | (0<<4) | (1<<6) );  
        _mm_shuffle_epi32( dataPtr3[0], 0 | (1<<2) | (0<<4) | (1<<6) );  
        _mm_shuffle_epi32( dataPtr3[1], 0 | (1<<2) | (0<<4) | (1<<6) );  
        _mm_shuffle_epi32( dataPtr3[2], 0 | (1<<2) | (0<<4) | (1<<6) );  
      #endif
    }
    if ( (outerLoop % 1000) == 0 ) { putchar( '.' ); fflush( stdout ); }
  }

  timeStamp = clock() - timeStamp;
  printf( "\nRun was %lu seconds.\n", timeStamp / CLOCKS_PER_SEC );

  free( dataOrig );
  free( workQueue );

  return 0;
}
  • 我的 LOOP_UNROLL_2 运行时间是 40 秒。
  • 我的 LOOP_UNROLL_4 运行时间是 20 秒。
  • 我没有任何展开的运行时间是 80 秒。
  • 当我启用预取时，运行时间很长，我只是终止进程而不是等待它。

    • 我什至写了一个 8x 展开循环，它仍然可以完美地扩展到 10 秒的运行时间。我很惊讶它没有在那里饱和，因为那时我肯定会用完寄存器，持有 16 个唯一指针。那么我能从中学到什么？我的内部循环代码是如此紧凑，以至于它被循环结构本身的开销大大掩盖了？这段代码中是否有我没有看到的错误？所有版本均使用 gcc -O2 .

    最佳答案

    如果您的数据驻留在内存中，不要期望有很大的加速；从内存中预取几乎没有什么可以改进的。

    具有 150 ns 循环时间、64 字节缓存线和 4GB/秒的流传输速率(我的 AMD 系统；英特尔更快)，并且使用每个 64 字节缓存线读取的 48 字节(3 x 128 位)，系统是每秒获取 320 MB 的可用数据。预取使速率接近 4000 MB/s 的峰值。每 320 MB 读取可用于预取的总节省时间为 0.92 秒。在 320 MB/s 时，270 秒(4m 30s)相当于 840 GB 的内存传输时间；程序可能不会在实际读取内存上花费超过其中的一小部分(<1%，8GB)。完全消除内存 i/o 将节省...运行时间的 1%。

    过多预取的缺点是预取数据从靠近 cpu 的非常快但非常小的内存(1 级和 2 级缓存，千字节而不是兆字节)中取代了有用的东西。这可能是一些测试运行的悲观性能的原因。

    展开循环加速了程序，但预取并没有表明处理本身是主要瓶颈，而不是数据移动。

    关于performance - 我如何从预取内在函数中获得可衡量的好处？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25947069/

    上一篇：perl - 自重排作业队列的方法

    下一篇：r - 将函数应用于所有参数组合

    相关文章：

    javascript - 在 JS 中避免没有最终表达式的 FOR 循环是否有充分的理由？

    javascript - 循环中的异步和同步 JavaScript 代码

    assembly - 如何在 NASM 中编写 'Hello_world' EFI 应用程序？

    assembly - 如何在编译时检测 NASM 中的体系结构以获得 x64 和 x86 的一个源代码？

    c - 使用 GCC 内联汇编的 PC 相关调用

    c++ - 对齐 SSE 的模板 vector 结构

    r - R中嵌套循环的性能缓慢

    java - 视觉虚拟机中的采样

    C++ 加载和存储优化和堆对象

    c - 旧版本 GCC 上的 DPPS

    ©2024 IT工具网  联系我们