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

Question

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

1. Он использует два целых буфера одинакового размера
2. Он читает по одному все значения первого буфера
3. Читает значение по индексу во втором буфере
4. Суммирует все значения, взятые из второго буфера
5. Это делает все предыдущие шаги для большего и большего
6. В конце я печатаю номер добровольного и непроизвольного процессора

В самый первый раз значения в первых буферах содержат значения его индекса (см. Функцию createIndexBuffer в коде чуть ниже) .

Это будет более понятно в коде моей программы:

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

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


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 int * indexBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int));
  for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++)
  {
    indexBuffer[i] = i;
  }

  return (indexBuffer);
}


unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer)
{
  unsigned long long sum = 0;

  for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++)
  {
    unsigned int index = indexBuffer[i];
    sum += valueBuffer[index];
  }

  return (sum);
}


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

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

  unsigned long long sum = computeSum(indexBuffer, valueBuffer);

  gettimeofday(&endTime, NULL);

  printf("Sum = %llu\n", 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));
  unsigned int timeInMicroSeconds = computeTimeInMicroSeconds();
  printf("Time: %u micro-seconds = %.3f seconds\n", timeInMicroSeconds, (double) timeInMicroSeconds / (1000 * 1000));
}

Если я запускаю его, я получаю следующий вывод:

$ gcc TestPrefetch.c -O3 -o TestPrefetch && ./TestPrefetch 
sizeof buffers = 1562Mb
Sum = 439813150288855829
Time: 201172 micro-seconds = 0.201 seconds

Быстро и быстро!!! Насколько мне известно (я могу ошибаться), одна из причин наличия такой быстрой программы заключается в том, что при последовательном доступе к двум буферам данные могут быть предварительно выбраны в кэш-память ЦП.

Мы можем сделать его более сложным для того, чтобы данные (почти) выбирались в кеш процессора. Например, мы можем просто изменить createIndexBuffer функция в:

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

  return (indexBuffer);
}

Давайте попробуем программу еще раз:

$ gcc TestPrefetch.c -O3 -o TestPrefetch && ./TestPrefetch 
sizeof buffers = 1562Mb
Sum = 439835307963131237
Time: 3730387 micro-seconds = 3.730 seconds

Более чем в 18 раз медленнее!!!

Теперь мы подошли к моей проблеме. Учитывая новый createIndexBuffer функция, я хотел бы ускорить computeSum функция с использованием предварительной выборки

unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer)
{
  unsigned long long sum = 0;

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

  return (sum);
}

конечно, я также должен изменить свой createIndexBuffer для того, чтобы выделить буфер, имеющий еще один элемент

Я перезапускаю свою программу: не лучше! Поскольку предварительная выборка может быть медленнее, чем одна итерация цикла "for", я могу выполнить предварительную выборку не одного элемента раньше, а двух элементов раньше

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

не лучше! две петли итерации? не лучше? Три? ** Я пробовал до 50 (!!!), но я не могу повысить производительность своей функции computeSum,

Могу ли я помочь помочь понять, почему Большое спасибо за вашу помощь

Answer 1

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

Затем я адаптировал свою программу, чтобы попробовать ваше предложение, используя 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
...

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

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

большое спасибо