使用 OpenMP 从教程中计算 Pi 算法

Question

我在学习this关于 OpenMP 的教程，我在第 19 页看到了这个练习。这是一个我必须并行化的圆周率计算算法:

static long num_steps = 100000;
double step;
void main ()
{
  int i;
  double x, pi
  double sum = 0.0;
  step = 1.0 / (double)num_steps;

  for(i = 0; i < num_steps; i++)
  {
     x = (I + 0.5) * step;
     sum = sum + 4.0 / (1.0 + x*x);
  }

  pi = step * sum;
}

到目前为止，我无法使用#pragma parallel for。我只能使用:

#pragma omp parallel {}
omp_get_thread_num();
omp_set_num_threads(int);
omp_get_num_threads();

我的实现是这样的:

#define NUM_STEPS 800

int main(int argc, char **argv)
{
   int num_steps = NUM_STEPS;
   int i;
  double x;
  double pi;
  double step = 1.0 / (double)num_steps;

  double sum[num_steps];

  for(i = 0; i < num_steps; i++)
  {
      sum[i] = 0;
  }

  omp_set_num_threads(num_steps);
  #pragma omp parallel
  {
    x = (omp_get_thread_num() + 0.5) * step;
    sum[omp_get_thread_num()] += 4.0 / (1.0 + x * x);
  }

  double totalSum = 0;

  for(i = 0; i < num_steps; i++)
  {
    totalSum += sum[i];
  }

  pi = step * totalSum;

  printf("Pi: %.5f", pi);
}

使用sum数组忽略问题(稍后解释需要用#pragma omp critical或#pragma omp atomic为sum值定义一个临界区)，上述实现仅适用于有限数量的线程(在我的例子中是 800)，其中序列代码使用 100000 步。有没有一种方法可以仅使用上述 OpenMP 命令来实现这一点，或者我是否必须使用 #pragma omp parallel for，这在教程中尚未提及？

非常感谢您抽出宝贵的时间，我真的很想在使用 OpenMP 的 C 语言中掌握并行化的概念。

Answer 1

您需要找到一种方法，使您的并行算法在某种程度上独立于线程数。

最简单的方法是做类似的事情:

int tid = omp_get_thread_num();
int n_threads = omp_get_num_threads();

for (int i = tid; i < num_steps; i += n_threads) {
    // ...
}

通过这种方式，无论线程数量多少，工作都会分配给所有线程。

如果有 3 个线程和 9 个步骤:

• 线程 0 将执行步骤 0、3、6
• 线程 1 将执行步骤 1、4、7
• 线程 2 将执行步骤 2、5、8

这可行，但如果每个线程都从某个共享数组访问数据，则效果不佳。如果线程访问 locality 附近的数据部分会更好目的。

在这种情况下，您可以将步骤数除以线程数，并为每个线程分配一组连续的任务，如下所示:

int tid = omp_get_thread_num();
int n_threads = omp_get_num_threads();

int steps_per_thread = num_steps / n_threads;
int start = tid * steps_per_thread;
int end = start + steps_per_thread;

for (int i = start; i < end; i++) {
    // ...
}

现在执行 9 个步骤的 3 个线程如下所示:

• 线程 0 执行步骤 0、1、2
• 线程 1 执行步骤 3、4、5
• 线程 2 执行第 6、7、8 步

这种方法实际上是在使用#pragma omp for 时最有可能发生的情况。在大多数情况下，编译器只是根据线程数划分任务，并为每个线程分配一个部分。

因此，给定一组 2 个线程和 100 次循环迭代，编译器可能会将迭代 0-49 分配给线程 0，将迭代 50-99 分配给线程 1。

请注意，如果迭代次数未除以线程数，则余数需要明确处理。