1

我正在尝试为一些 C 练习构建一个主要查找器。我已经把算法搞定了，我已经做了很多优化以使其更快，然后我决定尝试并行化它，因为，嘿，为什么不呢！结果比我想象的要难。我可以让所有线程运行相同的进程（具有相同的参数），或者如果我尝试为每个进程提供不同的参数，则单个线程将运行。我真的不知道我在这里做什么，但你可以看到我在这段代码中使用的一些实验值：

// gcc -std=c99 -o multithread multithread.c -fopenmp -lm

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>

int pf(unsigned int start, unsigned int limit, unsigned int q);

int main(int argc, char *argv[])
{   
printf("prime finder\n");

int j, slimits[4] = {1,10000000,20000000,30000000}, elimits[4] = {10000000,20000000,30000000,40000000};

double startTime = omp_get_wtime();

#pragma omp parallel shared(slimits, elimits primes)
{
    #pragma omp for
    for (j = 0; j < 4; j++)
    {
        primes += pf(slimits[j], elimits[j], atoi(argv[2]));
    }
}
printf("%d prime numbers found in %.2f seconds.\n\n", primes, omp_get_wtime() - startTime);
return 0;
}

我没有包含 pf 函数，因为它很大，但它可以自己工作，它返回找到的素数的数量。我确定问题出在某个地方。任何帮助将不胜感激！

4

1 回答 1

2

你至少犯了一个明显的（对我来说）严重的错误。您已声明primesshared 并允许程序中的所有线程对其进行更新。因此，您已经编写了数据竞赛。OpenMP（如果我没记错的话，也不是 C 语言）中没有任何东西可以保证+=以原子方式实现。您实际上并没有具体说明您的程序的问题是什么，或者问题是什么，但这肯定是其中之一。

我稍后会告诉你如何解决这个问题，但我认为你应该首先解决一个更严重的底层设计问题。您似乎已经决定要运行 4 个线程，并且应该将用于测试素性的整数范围划分为 4，并将一个块传递给每个线程。当然，您可以完成这项工作，但这不是使用 OpenMP 的明智方法。这也不是划分素性测试工作的明智方法。

OpenMP 程序设计的一种更聪明的方法是首先不对执行程序可用的线程数做任何假设。为任意数量的线程设计，不要设计一个行为取决于它在运行时获得的线程数量的程序。使用 OpenMP 的工具，特别是该schedule子句，在运行时分配工作负载。

转向素数测试。绘制或至少考虑点的散点图(i,t(i))，其中i是一个整数，t(i)是确定是否i为素数所需的时间。该图中的模式与整数中素数出现的图中的模式一样难以辨别。换句话说，确定整数素数的时间是非常不可预测的。它确实会随着整数的增加而上升（嗯，不包括我确信你的测试不会考虑的大偶数）。

这种不可预测性的一个含义是，如果您将整数范围划分为N子范围并为每个N线程分配一个子范围，那么您并没有给线程提供相同的工作量。实际上，在整数范围1..m（任意m）中，有一个整数比该范围内的任何其他整数都需要更长的测试时间，而这个时间是您的程序将采用的不可约最小值。范围的幼稚分布将产生严重不平衡的工作量。

这是我认为你应该做的来修复你的程序。

首先，编写一个函数来测试单个整数的素数。这将是您计算的基本任务。打电话给这个is_prime。接下来，研究schedule并行for结构的子句。OpenMP 提供了许多任务调度选项，我不会在这里解释它们，你会在网上找到很多很好的文档。最后，还要研究reduction从句；这为您编程的数据竞争提供了解决方案。

应用这一切我建议你改变

#pragma omp parallel shared(slimits, elimits primes)
{
    #pragma omp for
    for (j = 0; j < 4; j++)
    {
        primes += pf(slimits[j], elimits[j], atoi(argv[2]));
    }
}

到

#pragma omp parallel shared(slimits, elimits, max_int_to_test) 
{
    #pragma omp for reduction(+:primes) schedule (dynamic, 10)
    for (j = 3; j < max_int_to_test; j += 2)
    {
        primes += is_prime(j);
    }
}

幸运的是，我的基本 C 语言并没有把语法搞砸太多。

于 2013-11-09T09:41:31.887 回答