OpenMP

Question

我有以下算法：

int hostMatch(long *comparisons)
{
    int i = -1;
    int lastI = textLength-patternLength;
    *comparisons=0;

    #pragma omp parallel for schedule(static, 1) num_threads(1)
    for (int k = 0; k <= lastI; k++)
    {
        int j;
        for (j = 0; j < patternLength; j++)
        {
            (*comparisons)++;
            if (textData[k+j] != patternData[j])
            {
                j = patternLength+1; //break    
            }
        }
        if (j == patternLength && k > i)
            i = k;
    }

    return i;
}

更改 num_threads 时，我得到以下比较次数结果：

01 = 9949051000
02 = 4992868032
04 = 2504446034
08 = 1268943748
16 = 776868269
32 = 449834474
64 = 258963324

为什么比较次数不固定？这很有趣，因为比较的次数随着线程数的加倍而减半。 (*comparisons)++ 是否存在某种竞争条件，如果变量正在使用，OMP 会跳过增量？

我目前的理解是 k 循环的迭代在线程之间几乎平均分配。每次迭代都有一个私有整数 j 以及一个整数 k 的私有副本，以及一个添加到比较中的非并行 for 循环，直到已终止。

Answer 1

你自己说的 (*comparisons)++; 有竞争条件。它是一个必须序列化的关键部分（我不认为 (*pointer)++ 是原子操作）。

所以基本上你通过两个线程读取相同的值（即 2）两次，然后都增加它（3）并将其写回。所以你得到 3 而不是 4。你必须确保对变量的操作不在并行化的本地范围内 function/loop，不要重叠。

Answer 2

绕过竞争条件将操作声明为 atomic update:

的天真方法

#pragma omp atomic update
(*comparisons)++;

请注意，此处的临界区是不必要的，而且成本更高。 atomic update 可以在任何具有标量类型的左值表达式的原始二元或一元运算上声明。

但这仍然不是最优的，因为 *comparisons 的值需要一直在 CPU 缓存之间移动，并且执行昂贵的锁定指令。相反，你应该使用减少。为此你需要另一个局部变量，指针在这里不起作用。

int hostMatch(long *comparisons)
{
    int i = -1;
    int lastI = textLength-patternLength;
    long comparisons_tmp = 0;

    #pragma omp parallel for reduction(comparisons_tmp:+)
    for (int k = 0; k <= lastI; k++)
    {
        int j;
        for (j = 0; j < patternLength; j++)
        {
            comparisons_tmp++;
            if (textData[k+j] != patternData[j])
            {
                j = patternLength+1; //break    
            }
        }
        if (j == patternLength && k > i)
            i = k;
    }

    *comparisons = comparisons_tmp;

    return i;
}

P.S。 schedule(static, 1) 似乎是个坏主意，因为这会导致 textData 上的内存访问模式效率低下。把它放在外面，让编译器来做这件事。如果测量表明它没有有效地工作，请给它一些更好的提示。

OpenMP - 为什么比较次数会减少？

OpenMP - Why does the number of comparisons decrease?

c

parallel-processing

for-loop