数组过滤的高效并行算法

Question

给定一个非常大的数组，我只想 select 匹配某些条件的元素。我先验地知道将要匹配的元素数量。我当前的伪代码是：

filter(list):
  out = list of predetermined size
  i = 0
  for element in list
    if element matches condition
      out[i++] = element
  return out

在尝试并行化之前的算法时，我天真的方法是使 i 的增量成为原子的（它是 OpenMP 项目的一部分，因此使用了#pragma omp atomic）。然而，与串行实现相比，这种实现降低了性能。有什么更有效的算法来实现这个？为什么我的速度变慢了？

来自评论的信息：

我将 C 与 OpenMP 结合使用；
目前正在测试一百万个条目；
串行需要大约 7 秒，两个线程并行需要大约 15 秒；
输出数组大小刚好是一半（问题等同于找到小于所述数组中位数的数组元素）；
我只用两个内核测试它。

Answer 1

However this implementation has slowed performance when compared to even the serial implementation. What more efficient algorithms are there to implement this?

瓶颈是 atomic 操作的开销，因此乍一看更有效的算法应该是避免使用此类操作的算法。尽管这是可能的，但代码将需要一个两步的方法，例如每个线程都会将它找到的元素保存在一个私有数组中。在并行区域之后，main 线程将收集每个线程找到的所有元素并将它们合并到一个数组中。

合并成单个数组的第二部分也可以并行或使用 SIMD 指令。

我创建了一个小代码来模仿您的伪代码：

#include <time.h>
#include <omp.h>

int main ()
{
  int array_size = 1000000;
  int *a = malloc(sizeof(int) * array_size); 
  int *out = malloc(sizeof(int) * array_size/2);
 
  for(int i = 0; i < array_size; i++)
      a[i] = i;   
 
  double start = omp_get_wtime();
  int i = 0;
  #pragma omp parallel for
  for (int n=0 ; n < array_size; ++n ){
      if(a[n] % 2 == 0){
         int tmp;
         #pragma omp atomic capture
         tmp = i++;
         out[tmp] = a[n]; 
      }
  }
  double end = omp_get_wtime();
  printf("%f\n",end-start);
  free(a);
  free(out);
  return 0;
}

我做了一个临时基准测试，结果如下：

-> Sequential : 0.001597 (s)
-> 2 Threads  : 0.017891 (s)
-> 4 Threads  : 0.015254 (s)

因此并行版本要慢得多，这是可以预料的，因为并行执行的工作根本不足以克服 atomic 和并行性的开销。

我还测试了删除 atomic 并保留 race-condition 只是为了检查时间：

-> Sequential : 0.001597 (s)
-> 2 Threads  : 0.001283 (s)
-> 4 Threads  : 0.000720 (s)

因此，如果没有原子，2 线程和 4 线程的加速比分别约为 1.2 和 2.2。所以自然 atomic 会造成巨大的开销。尽管如此，即使没有任何 atomic，加速也不是很大。这是您可以单独并行化代码的最大期望。

根据您的实际代码以及您的条件对计算的要求，即使使用我提到的第二种方法，您也可能无法实现很大的加速。

来自 @Paul G 的评论的有用注释：

Even if it isn't going to speed up this particular example, it might be useful to state that problems like this are generally solved in parallel computing using a (parallel) exclusive scan algorithm/prefix sum to determine which thread starts at which index of the output array. Then every thread has a private output index it is incrementing and one doesn't need atomics.

That approach might be slower than @dreamcrashs solution in this particular case but is more general as having private arrays for each thread can be very tricky (determining their size etc.) especially if your output is bigger than the input (case where each input element doesnt give 0 or 1 output element, but n output elements).

数组过滤的高效并行算法

Efficient Parallel algorithm for array filtering

c

parallel-processing

concurrency

multithreading

openmp