multithreading - 在 OpenMP 'for' 中使用 rand_r 使用 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("%fs\n", 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没有任何区别，动态调度使事情变得更糟。但是，如果我用与随机无关的东西替换循环体，i。 e. sum += *seedp + i; ，一切都按预期工作。

Answer 1

这是虚假分享的教科书示例。通过使用每个线程获取一个元素的种子数组，您可以强制逻辑上的私有(private)变量在内存中物理上彼此相邻。因此，它们都在同一个高速缓存行中。这意味着尽管没有线程尝试修改某个其他线程的种子，但缓存行本身会在每次迭代时由每个线程修改。而实际的问题是系统无法检测到缓存一致性变量的修改，只能检测到缓存行的修改。因此，在每个线程的每次迭代中，缓存行已被另一个线程修改，并且从系统的角度来看不再有效。它必须从内存中重新加载(嗯，很可能是从这里的共享 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("%fs\n", end_time - begin_time);
  return EXIT_SUCCESS;
}