OpenMP - 为什么比较次数会减少？ [英] OpenMP - Why does the number of comparisons decrease?

问题描述

  int hostMatch（long * comparisons）
 {
 int i = -1; 
 int lastI = textLength-patternLength; 
 *比较= 0; 
 $ b $ #pragma omp parallel for schedule（static，1）num_threads（1）
 for（int k = 0; k <= lastI; k ++）
 {
 int j; （j = 0; j  {
（* comparisons）++; 
 if（textData [k + j]！= patternData [j]）
 {
 j = patternLength + 1; //断开
} 
} 
 if（j == patternLength&& k> i）
 i = k; 
} 
 
 return i; 
 
  

更改 num_threads 我得到以下的比较结果：
$ b $ ul
01 = 9949051000

02 = 4992868032
< 04> 2504446034

08 = 1268943748

16 = 776868269

32 = 449834474

64 = 258963324

为什么比较次数不是恒定的？这很有趣，因为比较的数量减少了一倍以上的线程数量。如果变量正在使用，OMP是否跳过增量，是否有一些竞争条件正在进行（* comparisons）++ ？

我目前的理解是， k 循环的迭代在线程之间被均匀分割。每个迭代都有一个私有整数 j ，以及一个整数 k 的私有副本，以及一个不平行的for循环，直到终止时才加入比较。

解决方案

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

所以基本上你读了相同的值（即2）由两个线程两次，然后增加它（3）并写回来。所以你得到3而不是4.你必须确保对变量的操作，不在你的并行化函数/循环的本地范围内，不要重叠。

I have the following algorithm:

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;
}

When changing num_threads I get the following results for number of comparisons:

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

Why is the number of comparisons not constant? It's interesting because the number of comparisons halves with the doubling of the number of threads. Is there some sort of race conditions going on for (*comparisons)++ where OMP just skips the increment if the variable is in use?

My current understanding is that the iterations of the k loop are split near-evenly amongst the threads. Each iteration has a private integer j as well as a private copy of integer k, and a non-parallel for loop which adds to the comparisons until terminated.

解决方案

You said it yourself (*comparisons)++; has a race condition. It is a critical section that has to be serialized (I don't think (*pointer)++ is an atomic operation).

So basically you read the same value( i.e. 2) twice by two threads and then both increase it (3) and write it back. So you get 3 instead of 4. You have to make sure the operations on variables, that are not in the local scope of your parallelized function/loop, don't overlap.

这篇关于OpenMP - 为什么比较次数会减少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！