使用预取加速随机内存访问

Question

我试图通过使用预取来加速单个程序。我的程序的目的只是为了测试。以下是它的作用：

1. 它使用两个大小相同的int缓冲区

第一次，第一个缓冲区中的值包含其索引的值（参见下面代码中的函数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

快，快！！！据我所知（我可能错了），有这么快的程序的原因之一是，当我依次访问我的两个缓冲区时，数据可以在CPU缓存中预取。

我们可以使它更复杂，以便数据（几乎）在CPU缓存中预缓存。例如，我们可以在以下位置更改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

很抱歉我给你的不是我代码的正确版本。正确的版本是，你所说的：

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

然而，即使是正确的版本，不幸的是它并没有更好

Answer 2

预取通常是一个完整的缓存线。这通常是64字节。因此，随机示例总是为4字节整数获取64字节。16倍于您实际需要的数据，这非常适合减速18倍。因此，代码只受内存吞吐量而不是延迟的限制。

Answer 3

我相信上面的代码是由CPU自动优化的，没有任何空间进行手动优化。

1.主要问题是indexBuffer是按顺序访问的。硬件预取器检测到它并自动预取更多值，而无需手动调用预取。因此，在迭代i期间，值indexBuffer[i1]，indexBuffer[i2]，。。。已在缓存中。（顺便说一句，不需要在数组末尾添加人工元素：预取指令会自动忽略内存访问错误）。

您真正需要做的是预取valueBuffer：

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

2.但是在这样简单的场景中，添加上面的代码行也没有帮助。访问内存的成本是数百个周期，而添加指令是〜1个周期。您的代码已经花费了99%的时间在内存访问上。添加手动预取将使这一周期更快，也不会更好。

如果你的数学要复杂得多（试试看），比如使用一个包含大量未优化的out除法（每个20-30个循环）的表达式，或者调用一些数学函数（log，sin），那么手动预取会非常有效。

3.但即使这样也不能保证有帮助。循环迭代之间的依赖性非常弱，它仅通过sum变量实现。这允许CPU推测性地执行指令：它可能会同时开始获取valueBuffer[i]，同时仍然执行valueBuffer[i]的数学运算。