前缀和并行算法

Question

我正在研究并行求和扫描算法，但我的结果不正确。

我正在致力于在 OpenMP 中实现 Hillis Steele 扫描。

我的函数输出不正确的结果

void prefixSumShared(double *arr, int size, int numThreads)
{    
     double logsize = ceil(log2(size));
  
     for (int j = 1; j <= logsize; j++)
     {
          int power = 1 << (j - 1); // 2^(j-1) 
          int power2 = 1 << j; // 2^j
          #pragma omp parallel for num_threads(numThreads)
          for (int k = 1; k < size; k++)
          {
               if (k >= power2)
               {
                    arr[k] = arr[k] + arr[k - power];
               }
               
          }
     }

}

我的输出会随着我使用的每个头数而变化。

当数组长度为 0 到 9 之间的数字且有 2 个线程时

{0.000000,1.000000,2.000000,3.000000,4.000000,5.000000,6.000000,7.000000,8.000000,9.000000}

我的输出是

{0.000000,1.000000,3.000000,7.000000,13.000000,23.000000,37.000000,57.000000,83.000000,119.000000}

一旦我弄清楚如何使用已知值运行它，我会将输入数组更改为 0 到 2 之间的随机值。

我尝试了不同的方法，例如在这个Youtube视频

中找到的方法

我尝试使用各种线程号运行它，但不断得到不正确的结果。

Answer 1

我正在致力于在 OpenMP 中实施 Hillis Steele Scan。

OpenMP 不提供适用于您引用的 Hillis & Steele 论文中描述的算法的并行计算模型。来自他们的介绍性评论：

在本文中，我们描述了一系列适用于 具有通用通信功能的细粒度并行计算机。我们称之为 这些算法

数据并行算法，因为它们的并行性 来自大型数据集的同时操作，而不是 比来自多个控制线程。其目的并不在于 提出新的算法（大多数已经在其他的早期文章中描述过） 上下文），而是展示一种编程风格 适用于数万甚至数百万的机器 处理器。所描述的算法都使用 O(N) 处理器来解决 大小为 N 的问题，通常需要 O(log N) 时间。

我可以自信地说，你们没有一台具有他们继续描述的物理和计算特征的机器。尽管 OpenMP 可以利用主机硬件的 SIMD 功能，但它从根本上提供了一种多线程并行方法，而不是本文中描述的算法所基于的“数据并行”方法。

您可能可以通过 OpenMP 或其他基于线程的方法模拟所需的特性，但您需要添加相当细粒度的同步，我预计这会影响性能，足以使算法变得无趣，除非可能是巨大的数据集。