Подтвердить что ты не робот

Как получить измеримую выгоду от встроенных функций предварительной выборки?

Использование gcc 4.4.5 (да... я знаю это старый) на x86_64. Ограничено инструкциями SSE2 (или ранее) по соображениям совместимости.

У меня есть то, что, по моему мнению, должно быть учебником для получения больших преимуществ от предварительной выборки. У меня есть массив ( "A" ) из 32-битных элементов, которые не являются (и не могут быть) в последовательном порядке. Эти 32-битные элементы представляют собой индексы в более крупный массив данных ( "D" ) данных __m128i. Для каждого элемента "A" мне нужно получить данные __m128i из соответствующего места в "D", выполнить операцию над ним и сохранить его обратно в одно и то же место в "D". Фактически каждая "запись" в D "SOME_CONST" __m128i большая. Поэтому, если значение в равно "1", индекс в D равен D [1 * SOME_CONST].

Поскольку последовательные элементы в "A" почти никогда не указывают на последовательные местоположения в "D", я склонен думать, что аппаратный префейдер будет бороться или не сможет выполнить что-либо полезное.

Тем не менее, я могу предсказать, в каких местах я буду получать доступ к следующим очень легко, просто посмотрев вперед в "А". Достаточно словесности... вот какой-то код. Операция, которую я выполняю на данных, заключается в том, чтобы взять младшие 64-бит __m128i и клонировать ее в верхние 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-элементная версия, но я также пробовал только с двумя, если бы было слишком много данных, которые можно было бы разворачивать. Также я попытался использовать _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 с разницы во времени выполнения в течение миллионов итераций, которые занимают общее время процессора 4 м: 30 секунд на этой конкретной машине (которая является каменным бездействием, кроме меня). Различия кажутся неотличимыми от "шума" в данных.

Правильно ли я утверждаю, что предварительная выборка должна помочь мне здесь? Если да, то что я делаю неправильно?

Приветствуются все полезные и интересные мысли.

EDIT:

Я создал надуманный пример, который действительно рандомизирует данные в A. Я играл с размерами буфера от 64 МБ до 6400 МБ. Я обнаружил, что получаю огромную выгоду от разворачивания цикла и предварительного вычисления адресов следующих 4 элементов, поскольку я выполняю свою операцию на текущем 4. Но мои баги во время выполнения в 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 секунд.
  • Когда я включаю prefetches, время выполнения так велико, что я просто убиваю процесс, а не жду его.

Я даже написал 8-кратный развернутый цикл, и он по-прежнему отлично масштабируется до 10 секунд времени исполнения. Я поражен тем, что он не насытился, потому что в этот момент у меня наверняка закончились регистры, в которых было бы 16 уникальных указателей. Так что я могу узнать из этого? Что мой внутренний код цикла настолько туго, что он сильно омрачен накладными расходами в самой конструкции цикла? Есть ли ошибки в этом коде, которые я не вижу? Все сборки были с gcc -O2.

4b9b3361

ОТВЕТЫ

Ответ 1

Если ваши данные хранятся в памяти, не ожидайте большей части ускорения; предварительная выборка из памяти имеет очень мало возможностей для улучшения.

С периодом времени 150 нс, 64-байтовыми линиями кэша и скоростью передачи данных 4 ГБ/с (моя система AMD, Intel быстрее) и используя 48 байт (3 х 128 бит) каждой строки в 64-байтной кеше, система извлекает 320 МБ полезной информации в секунду. Предварительная выборка приближает скорость к пику 4000 МБ/с. Общая экономия, доступная для предварительной выборки, составляет 0,92 секунды для каждого чтения 320 МБ. При 320 Мбайт/с, 270 секунд (4 м 30 с) - 840 ГБ времени передачи памяти; Вероятно, программ, по-видимому, не тратит больше, чем небольшая часть этого (< 1%, 8 ГБ) на фактически чтение памяти. Полностью исключая возможность ввода/вывода памяти сохранит... 1% от времени выполнения.

Недостаток слишком большой предварительной выборки заключается в том, что предварительно загруженные данные вытесняют полезные вещи из очень быстрой, но очень маленькой памяти, близкой к процессору (кэши уровня 1 и уровня 2, килобайты не мегабайты). Это может объяснить пессимум производительности некоторых тестовых прогонов.

Это разворачивание цикла ускорило программу, но предварительная выборка также не предполагала, что сама обработка является основным узким местом, а не перемещением данных.