使用预取加速随机内存访问-Java 学习之路

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

它使用两个相同大小的int缓冲区它逐个读取第一个缓冲区的所有值它读取第二个缓冲区中索引处的值它将从第二个缓冲区中获取的所有值相加它完成所有之前的操作更大更大的步骤最后，我打印了自愿和非自愿CPU的数量

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

We now arrive to my problem . 鉴于新的 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 ，以便它分配一个具有一个元素的缓冲区

我重新开始我的计划： not better ！由于预取可能比一个循环迭代慢，我可能先预取一个元素而不是之前的两个元素

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

not better ！两个循环迭代？ not better ？三？ **我试过它直到50（!!!）但我无法提升我的功能 computeSum 的性能 .

我想帮助理解为什么非常感谢你的帮助

4 回答

0
我相信上面的代码是由CPU自动优化的，没有任何进一步的空间用于手动优化 .

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 变量 . 这允许CPU以推测方式执行指令：它可以在仍然执行 valueBuffer[i] 的数学运算的同时开始同时获取 valueBuffer[i+1] .
回复于 2024-05-12T20:01:47+08:00
3
抱歉 . 我给你的不是我的代码的正确版本 . 正确的版本是，你说的：
```
__builtin_prefetch((char *) &valueBuffer[indexBuffer[i + prefetchStep]], 0, 0);
```
然而，即使使用正确的版本，遗憾的是它并不是更好
回复于 2024-05-12T20:01:47+08:00

然后我调整了我的程序，使用 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
...

所以在这里，它更好！老实说，我几乎肯定它不会更好，因为与内存访问相比，数学函数成本更高 .

如果有人能给我更多关于为什么它现在更好的信息，我将不胜感激

非常感谢你

回复于 2024-05-12T20:01:47+08:00

0

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

回复于 2024-05-12T20:01:47+08:00

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

4 回答

相关问题