Я пытаюсь ускорить работу одной программы с помощью предварительной выборки. Цель моей программы - просто проверить. Вот то, что она делает:Ускорьте случайный доступ к памяти с использованием предварительной выборки
- Он использует два Int буферов одного и того же размера
- Он читает один за другим все значения первого буфера
- Он считывает значение в индексе во втором буфере
- Он суммирует все значения, взятые из второго буфера
- Это все предыдущие шаги для большего и большего
- в конце я печатаю число и непроизвольного CP У
В первый раз, значение в первых буферах содержит значение его индекса (ср функция 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
функцию с помощью PreFetch
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
, чтобы он выделяет буфер, имеющий еще один элемент
I программе возобновления моя программа: не лучше! Как упреждение может быть медленнее, чем один «для» итерации цикла, я могу упреждение не один элемента раньше, но два элемента, прежде чем
__builtin_prefetch((char *) &indexBuffer[i + 2], 0, 0);
не лучше! две петли итераций? не лучше? Три? ** Я пробовал это до 50 (!!!), но я не могу повысить производительность своей функции computeSum
.
Могу ли я хотел бы помочь понять, почему Большое спасибо за вашу помощь
Мой ответ для вашего предложения 'sin' выше вашего ответа, а не ниже (я, конечно, допустил ошибку ...) –