并行化时的不同答案

Question

#pragma omp parallel for    
for (int i = 0; i <500; i++)
   for (j=i; j < 102342; j++)
    {
      Output[j] += staticConstant[i] * data[j-i];
    }
}

一些向量答案是相同的，一些是不同的。这可能是什么原因？一开始我认为这可能是由于浮动，所以我把所有的东西都转换成了双精度。可能会有5-6个答案完全相同，或者是随机值非常接近的较大块，以及一些相当远的块。

Answer 1

您有多个线程在写入Output[j]。这会导致竞争条件。由一个线程写入的值被另一个具有不同值的线程替换。

Answer 2

问题是您的内部循环具有写争用条件，因此，例如，以下两个语句可能会并行发生：

Output[42] = Output[42] + staticConstant[9] * data[42-9];
Output[42] = Output[42] + staticConstant[19] * data[42-19];

每一行的代码归结为：

Load O[42] to R1
Load C[] to R2
Add R2 to R1
Store R1 to O[42]

但是，并行化程序可能会导致代码像这样运行：

Load O[42] to R1
Load O[42] to R3
Load C[9] to R2
Load C[19] to R4
Add R2 to R1
Add R4 to R3
Store R1 to O[42]
Store R3 to O[42]

正如您可能看到的，两个Load O[42]行在添加C[9]或C[19]之前加载值，因此实际上忽略了第一个计算。

最简单的修复方法是：

for (int i = 0; i <500; i++)
{
#pragma omp parallel for    
   for (j=i; j < 102342; j++)
    {
      Output[j] += staticConstant[i] * data[j-i];
    }
}

现在，因为只有内部循环是并行的，所以不会有竞争条件。