使用OpenMP并行增加数组元素

Question

我有一个大小为N的数组a，其中包含随机数。使用OpenMP，我想要对大小为10的数组b中0到9的元素进行递增，以处理A中的每个数字。语言是C。

#pragma omp parallel for
for(i = 0; i < N; i++)
   b[a[i]]++;

很不幸，b 数组中的某些元素存在同时写入的情况，结果与预期不符。我已经尝试将 b 设置为 firstprivate 和 lastprivate ，但这也没有帮助。

这个任务看起来很简单，但在 OpenMP 中数组没有原子操作。我可以为线程数创建一个新数组，然后在最后将它们加起来，但这似乎并不是最优解。

如何最快地统计 a 数组中每个数字在 b 数组元素中出现的次数？

- Michael

---

独立求和，然后合并结果。 - Brian Cain

@BrianCain 我不确定你的意思。你说的“sum”是指增量吗？你说的“independently”是指我应该创建一个新的私有变量吗？你说的“merge”是指我应该在最后将所有版本的私有变量相加吗？因为这对我来说似乎是低效的。你能用简单的代码片段展示一下你的意思吗？ - Michael

算法并不像我想象的那么简单。但最终这是一个权衡，它是否有效可能取决于N与b大小的比例（它真的总是10吗？）。一个更简单的替代方案是使用一系列互斥锁。 - Brian Cain

我不理解“在OpenMP中数组没有原子性”的意思。您指的是哪个OpenMP规范？您并不是试图对数组执行原子操作。您正在尝试对数组的单个元素进行原子递增，我找不到任何证据表明这样做不起作用。 - Jeff Hammond

Answer 1

您的问题实际上是我曾经提出的一个问题的重复。 使用OpenMP在不使用临界区的情况下并行填充直方图。

在您的情况下，简单的解决方案是

#pragma omp parallel
{
    int i, b_local[10] = {0};
    #pragma omp for nowait 
    for(i = 0; i < n; i++) b_local[a[i]]++;
    #pragma omp critical
    for(i=0; i<10; i++) b[i] += b_local[i];    
}

虽然可以在没有临界区的情况下完成这个过程（请参见我的问题），但这并不一定更有效。

以下是一个可行的例子：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 100

void foo(int *b, int *a, int n) {
    #pragma omp parallel
    {
        int i, b_local[10];
        memset(b_local, 0, 10*sizeof(int));
        #pragma omp for 
        for(i = 0; i < n; i++) b_local[a[i]]++;


        #pragma omp critical
        {     
            for(i=0; i<10; i++) {
                b[i] += b_local[i]; 
            }
        }

    }
}

int main() {   
    int i;
    int b[10] = {0,1,2,3,4,5,6,7,8,9};
    int b2[10] = {0,1,2,3,4,5,6,7,8,9};
    int a[N];
    for(i=0; i<N; i++) a[i] = rand()%10;

    foo(b,a,N);
    for(i=0; i<N; i++) b2[a[i]]++;
    for(i=0; i<10; i++) printf("%d ", b[i]); puts("");
    for(i=0; i<10; i++) printf("%d ", b2[i]); puts("");
}

- Z boson

Answer 2

如果a[]中的任何值相同，则您将同时写入b的同一元素。

例如，如果a[0] = 1且a[1] = 1，则您将同时写入b[1]。

- shredder

Answer 3

你可以使用两个“for()”循环，一个用于每个数组

- Bryan Calvo Benoit

---

这应该是一个注释 - codingadventures