时间戳

首页 > 解决方案 > openmp 中嵌套 for 循环的性能改进失败

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

问题描述

我正在做 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;
                    }
                }
            }
        }
    }
}

标签： copenmp

解决方案

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

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

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

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

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

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

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

更新：可能的替代方案

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

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

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

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

此外，您可以实施一些微优化，以（可能）从串行版本中获得一点加速。这与问题无关，因此我不会在这里详细介绍，但您应该很容易在网络上找到示例。

推荐阅读