c - openmp 中嵌套 for 循环的性能改进失败

Question

我正在使用 Eratosthenes Sieve 算法来查找 n 之前的素数。想法是标记质数的所有倍数。但是，随着线程数量的增加，它并没有实现性能提升。

使用 100 个线程花费 0.009 秒，使用 1 个线程花费 0.006 秒来查找 100000 之前的素数。

#pragma omp parallel num_threads(t)
{
    #pragma omp for
    for (int index = 2; index <= N; index++) {
        list_of_nums[index - 2] = index;
    }

    #pragma omp for
    for (int loop_index = 2; loop_index <= num_to_stop; loop_index++) {
        if (list_of_nums[loop_index - 2] != -1) {
            for (int mark_index = loop_index - 2; mark_index < N - 1; mark_index += loop_index) {
                if (mark_index != loop_index - 2) {
                    if (list_of_nums[mark_index] % loop_index == 0) {
                        list_of_nums[mark_index] = -1;
                    }
                }
            }
        }
    }
}

Answer 1

首先，尽管如此，并行化并不能保证提高程序的速度。管理多个线程会增加计算的开销，这可能会压倒通过并发执行多个计算获得的加速。

其次，加速的范围受限于可实现的并发量。特别是，对于没有阻塞操作的计算，您不能指望通过添加比拥有独立执行引擎(大致为内核)更多的线程来获得改进。

但第三，在这里我将重点关注这个答案的其余部分，Eratosthenes 筛法具有数据依赖性，使其不适合并行化。您甚至可以从并行版本中获得正确的结果，这源于您实现的特定特质。问题集中在这里:

        if (list_of_nums[loop_index - 2] != -1) {

那是检查 loop_index 是否已经被确定为复合的，从而跳过多余的筛选它的倍数。那里的关键词是“已经”。如果 loop_index 是复合的，并且分配了与当前线程不同的线程来测试其主要因素，那么您不能确信 loop_index 已经被标记为复合 Material 。

如果您在此时选择质数并将它们存储在单独的列表中，您就会遇到麻烦，这在 SofE 实现中很常见。另一方面，您的特定实现可能只是做很多不必要的工作来筛选复合 Material 的倍数。因此，您不仅会产生管理多个线程的开销，而且可能会做更多的总工作。从这个意义上说，这并不是真正的埃拉托色尼筛法。

可以编写一个正确尊重其数据依赖性的 SofE 的并行版本，但我不确定 OpenMP 是否丰富到足以描述一个。我用另一种语言完成了它，它确实表现出一些加速。但是适本地尊重依赖性极大地限制了可用的并发量(并增加了更多开销)，因此加速非常乏善可陈。

更新:可能的替代方案

通过测量，您知道您的并行方法的性能比底层串行方法差。您可以尝试调整参数，例如使用的线程的精确数量，但最好换个方向。有前途的替代方案包括:

• 只需使用您算法的串行版本。根据您的测量，这将运行时间减少了 33%，一点也不差。

• 预先计算您的筛选/素数列表，而不是即时计算。那么计算的性能就不是影响大型服务性能的因素。

• 通过并行标记多个小素数的倍数并接受所涉及的冗余来预先播种您的筛子，然后从那里运行标准的串行 SofE。您可能希望通过对不同选择进行适当的性能测量来调整已知素数和线程数以用于预播种过程。

此外，您可以实现一些微优化，以(可能)从串行版本中获得一点加速。这与问题无关，所以我不会在这里详细说明，但您应该很容易在网上找到示例。