c - 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 循环的迭代在线程之间几乎平均分配。每次迭代都有一个私有(private)整数 j 以及一个整数 k 的私有(private)副本，以及一个添加到比较中直到终止的非并行 for 循环。

Answer 1

绕过竞争条件将操作声明为原子更新的天真方法:

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

请注意，这里的关键部分是不必要的，而且成本更高。 原子更新 可以在任何具有标量类型的左值表达式的原始二元或一元运算上声明。

但这仍然不是最优的，因为 *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;
}

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