在 OpenMP 中使用 rand_r 'for' 在 2 个线程下速度较慢

Question

以下代码使用 1 个线程比使用 2 个线程

的性能更好（不过，使用 4 个线程可以加快速度）：

#include <stdlib.h>
#include <stdio.h>
#include <omp.h>
int main(int argc, char **argv) {
  int n = atoi(argv[1]);
  int num_threads = atoi(argv[2]);
  omp_set_num_threads(num_threads);
  unsigned int *seeds = malloc(num_threads * sizeof(unsigned int));
  for (int i = 0; i < num_threads; ++i) {
    seeds[i] = 42 + i;
  }
  unsigned long long sum = 0;
  double begin_time = omp_get_wtime();
  #pragma omp parallel
  {
    unsigned int *seedp = &seeds[omp_get_thread_num()];
    #pragma omp for reduction(+ : sum)
    for (int i = 0; i < n; ++i) {
      sum += rand_r(seedp);
    }
  }
  double end_time = omp_get_wtime();
  printf("%fsn", end_time - begin_time);
  free(seeds);
  return EXIT_SUCCESS;
}

在我的笔记本电脑（2 核，启用 HT）上，我得到以下结果：

$ gcc -fopenmp test.c && ./a.out 100000000 1
0.821497s
$ gcc -fopenmp test.c && ./a.out 100000000 2
1.096394s
$ gcc -fopenmp test.c && ./a.out 100000000 3
0.933494s
$ gcc -fopenmp test.c && ./a.out 100000000 4
0.748038s

问题仍然存在，没有减少，drand48_r没有带来任何区别，动态调度使事情变得更糟。但是，如果我用与随机无关的东西替换循环的主体，即 sum += *seedp + i;，一切都按预期工作。

Answer 1

这是

错误共享的教科书示例。通过使用每个线程接受一个元素的种子数组，可以强制逻辑私有变量在内存中彼此相邻。因此，它们都在同一缓存行中。这意味着，尽管没有线程尝试修改其他线程的种子，但缓存行本身在每次迭代时都会由每个线程修改。而实际的问题是，系统无法检测变量对缓存一致性的修改，只能检测缓存行的修改。因此，在每个线程的每次迭代中，缓存行已被另一个线程修改，从系统的角度来看不再有效。它必须从内存中重新加载（嗯，很可能是从这里的共享 L3 缓存中重新加载），导致代码变慢。

试试这个（未测试）：

#include <stdlib.h>
#include <stdio.h>
#include <omp.h>
int main(int argc, char **argv) {
  int n = atoi(argv[1]);
  int num_threads = atoi(argv[2]);
  omp_set_num_threads(num_threads);
  unsigned long long sum = 0;
  double begin_time = omp_get_wtime();
  #pragma omp parallel
  {
    unsigned int seed = 42 + omp_get_thread_num();
    #pragma omp for reduction(+ : sum)
    for (int i = 0; i < n; ++i) {
      sum += rand_r(&seed);
    }
  }
  double end_time = omp_get_wtime();
  printf("%fsn", end_time - begin_time);
  return EXIT_SUCCESS;
}