c - OpenMP - 计算模式匹配中的比较

Question

我有以下算法，我通过尝试使顺序模式查找算法并行来创建它。

当我在尝试对所做的比较进行计数时遇到竞争条件时，我创建了一个临时变量并尝试执行归约，但是我仍然没有获得与顺序算法相同数量的比较。

int hostMatch(long *comparisons)
{
    int i = 0, j = 0, k = 0, lastI = textLength-patternLength;
    long comparisons_tmp = 0;
    int found = textLength + 1;

    #pragma omp parallel for reduction(+:comparisons_tmp) \
                         schedule(static)                  \
                         num_threads(4)                     \
                         default(none)                       \
                         shared(found, comparisons)           \
                         private(j, k)                         \
                         firstprivate(lastI, textData, patternData, patternLength)
    for(i = 0; i<= lastI; i++)
    {
         if(i < found)
         {
            k=i; j=0;
            while(textData[k] == patternData[j] && j < patternLength)
            {
                k++; j++; comparisons_tmp++;
            }
            if(j == patternLength)
            {
                #pragma omp critical(check)
                {
                    if(found > i)
                       found = i;
                }
            }
         }
    }
    *comparisons = comparisons_tmp;
 // return (found < textLength + 1) ? found : -1;
    if(found < textLength + 1)
         return found;
    else
         return -1;
}

这段代码返回比较的数量
3994004000 用于 test0，而
3996002000 用于顺序算法比较。

原顺序代码如下:

int hostMatch(long *comparisons)
{
int i,j,k, lastI;

i=0;
j=0;
k=0;
lastI = textLength-patternLength;
    *comparisons=0;

while (i<=lastI && j<patternLength)
{
            (*comparisons)++;
    if (textData[k] == patternData[j])
    {
        k++;
        j++;
    }
    else
    {
        i++;
        k=i;
        j=0;
    }
}
if (j == patternLength)
    return i;
else
    return -1;
}

我不确定我是否在错误的地方增加了 comparisons_tmp 变量，任何帮助将不胜感激。 Test0 包含 1999 A 后跟 B 的模式文件，以及 199999 A 后跟 B 的文本文件。

Answer 1

comparisons_tmp 应该在 while 循环之外递增。您现在缺少第一个比较，例如，如果 patter 的第一个字符不匹配，则根本不会增加比较。

但是，请注意，通过固定计数器位置，并行算法很可能会进行更多的比较，因为 OpenMP 不保证循环执行的顺序。这意味着很可能有些线程会比较 i 大于 found 的最终值。