Ускорьте доступ к произвольной памяти с помощью предварительной выборки

Я считаю, что приведенный выше код автоматически оптимизируется ЦП без дополнительного места для ручной оптимизации.

1. Основная проблема заключается в том, что к indexBuffer осуществляется последовательный доступ. Аппаратный модуль предварительной выборки распознает это и автоматически выполняет предварительную выборку следующих значений без необходимости вызывать предварительную выборку вручную. Итак, во время итерации #i значения indexBuffer[i+1], _3 _, ... уже находятся в кеше. (Кстати, нет необходимости добавлять искусственный элемент в конец массива: ошибки доступа к памяти молча игнорируются инструкциями предварительной выборки).

Что вам действительно нужно сделать, так это предварительно загрузить valueBuffer:

__builtin_prefetch((char *) &valueBuffer[indexBuffer[i + 1]], 0, 0);

2. Но и в таком простом сценарии добавление вышеуказанной строки кода не поможет. Стоимость доступа к памяти составляет сотни циклов, а инструкция добавления - ~ 1 цикл. Ваш код уже тратит 99% времени на доступ к памяти. Добавление предварительной выборки вручную сделает этот цикл быстрее и не лучше.

Ручная предварительная выборка действительно хорошо работала бы, если бы ваша математика была намного более сложной (попробуйте), например, используя выражение с большим количеством неоптимизированных делений (20-30 циклов каждое) или вызов некоторой математической функции (log, sin).

3. Но даже это не гарантирует помощи. Зависимость между итерациями цикла очень слабая, только через переменную sum. Это позволяет ЦП выполнять инструкции умозрительно: он может начать выборку valueBuffer[i+1] одновременно, продолжая выполнять математические вычисления для valueBuffer[i].

При предварительной выборке обычно выбирается полная строка кэша. Это обычно 64 байта. Таким образом, случайный пример всегда выбирает 64 байта для 4-байтового int. В 16 раз больше данных, которые вам действительно нужны, что очень хорошо сочетается с замедлением в 18 раз. Таким образом, код просто ограничен пропускной способностью памяти, а не задержкой.

Прости. То, что я вам дал, не было правильной версией моего кода. Правильная версия - это то, что вы сказали:

__builtin_prefetch((char *) &valueBuffer[indexBuffer[i + prefetchStep]], 0, 0);

Однако даже с правильной версией, к сожалению, не лучше.

Затем я адаптировал свою программу, чтобы попробовать ваше предложение с помощью функции sin.

Моя адаптированная программа следующая:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <sys/time.h>
#include <math.h>

#define BUFFER_SIZE ((unsigned long) 4096 * 50000)


unsigned int randomUint()
{
  int value = rand() % UINT_MAX;
  return value;
}


unsigned int * createValueBuffer()
{
  unsigned int * valueBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int));
  for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++)
  {
    valueBuffer[i] = randomUint();
  }

  return (valueBuffer);
}


unsigned int * createIndexBuffer(unsigned short prefetchStep)
{
  unsigned int * indexBuffer = (unsigned int *) malloc((BUFFER_SIZE + prefetchStep) * sizeof(unsigned int));
  for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++)
  {
    indexBuffer[i] = rand() % BUFFER_SIZE;
  }

  return (indexBuffer);
}


double computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer, unsigned short prefetchStep)
{
  double sum = 0;

  for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++)
  {
    __builtin_prefetch((char *) &valueBuffer[indexBuffer[i + prefetchStep]], 0, 0);
    unsigned int index = indexBuffer[i];
    sum += sin(valueBuffer[index]);
  }

  return (sum);
}


unsigned int computeTimeInMicroSeconds(unsigned short prefetchStep)
{
  unsigned int * valueBuffer = createValueBuffer();
  unsigned int * indexBuffer = createIndexBuffer(prefetchStep);

  struct timeval startTime, endTime;
  gettimeofday(&startTime, NULL);

  double sum = computeSum(indexBuffer, valueBuffer, prefetchStep);

  gettimeofday(&endTime, NULL);

  printf("prefetchStep = %d, Sum = %f - ", prefetchStep, sum);
  free(indexBuffer);
  free(valueBuffer);

  return ((endTime.tv_sec - startTime.tv_sec) * 1000 * 1000) + (endTime.tv_usec - startTime.tv_usec);

}


int main()
{
  printf("sizeof buffers = %ldMb\n", BUFFER_SIZE * sizeof(unsigned int) / (1024 * 1024));
  for (unsigned short prefetchStep = 0 ; prefetchStep < 250 ; prefetchStep++)
  {
    unsigned int timeInMicroSeconds = computeTimeInMicroSeconds(prefetchStep);
    printf("Time: %u micro-seconds = %.3f seconds\n", timeInMicroSeconds, (double) timeInMicroSeconds / (1000 * 1000));
  }
}

Результат:

$ gcc TestPrefetch.c -O3 -o TestPrefetch -lm && taskset -c 7 ./TestPrefetch 
sizeof buffers = 781Mb
prefetchStep = 0, Sum = -1107.523504 - Time: 20895326 micro-seconds = 20.895 seconds
prefetchStep = 1, Sum = 13456.262424 - Time: 12706720 micro-seconds = 12.707 seconds
prefetchStep = 2, Sum = -20179.289469 - Time: 12136174 micro-seconds = 12.136 seconds
prefetchStep = 3, Sum = 12068.302534 - Time: 11233803 micro-seconds = 11.234 seconds
prefetchStep = 4, Sum = 21071.238160 - Time: 10855348 micro-seconds = 10.855 seconds
prefetchStep = 5, Sum = -22648.280105 - Time: 10517861 micro-seconds = 10.518 seconds
prefetchStep = 6, Sum = 22665.381676 - Time: 9205809 micro-seconds = 9.206 seconds
prefetchStep = 7, Sum = 2461.741268 - Time: 11391088 micro-seconds = 11.391 seconds
...

Так что здесь работает лучше! Честно говоря, был почти уверен, что лучше не будет, потому что стоимость математической функции выше по сравнению с доступом к памяти.

Если бы кто-нибудь мог дать мне больше информации о том, почему сейчас лучше, я был бы признателен

Большое Вам спасибо