CODEWITHSUNDEEP
copenmp
hawkeyes21
hawkeyes21

Reputation: 47

OpenMP nested loop skips some of the combinations

I am creating a string matching parallel program with the use of OpenMP. Here's the code to match a two-character string.

void compare2(char *str) //str = 2 character string pass from main(). (for e.g. "aa")
{
    char str1[2];
    int flag = 0;

    #pragma omp parallel for collapse(2)
    for(int i=0; i<strlen(alphabet); i++)
    {
        for(int j=0; j<strlen(alphabet); j++)
        {
            if(flag)
            {
                continue;
            }
            str1[0] = alphabet[i];
            str1[1] = alphabet[j];
            str1[2] = '\0';
            printf("%s\n", str1);

            if(strcmp(str1, str) == 0)
            {
                printf("Match found %d!\n", omp_get_thread_num());
                flag = 1;
            }
        }
    }
}

I have observed that some of the combinations like "aa", "bc", etc. are frequently "skipped". Also, I don't face this problem when I specify the number of threads as num_threads(1). The problem occurs when the num_threads() > 1.
Note - The flag variable has been added to skip the output once the match is found.

Upvotes: 0

Views: 203

Answers (1)

John Bollinger
John Bollinger

Reputation: 181149

In addition to str1 not being long enough for your purpose, you have the additional major issue of data races involving that variable. It will be shared by the threads executing your parallel section, which will result in them stomping all over each other's data, or worse. It is not particularly surprising that this manifests as some combinations tending to be skipped.

But this should be pretty easy to solve. Best practice for variable declarations is to place them in the narrowest scope that permits them to serve their purpose. You use that array only inside the innermost loop of your loop nest, and you do not rely on it to keep its value across iterations, so you should declare it inside that loop. Doing so will have the additional effect of preventing the problematic sharing, so that's an all-around win. Something along these lines:

void compare2(char *str) //str = 2 character string pass from main(). (for e.g. "aa")
{
    int flag = 0;

    #pragma omp parallel for collapse(2)
    for (int i = 0; i < strlen(alphabet); i++) {
        for (int j = 0; j < strlen(alphabet) && flag == 0; j++) {
            if(flag) {
                continue;
            }

            char str1[3] = { alphabet[i], alphabet[j] };

            printf("%s\n", str1);

            if (strcmp(str1, str) == 0) {
                printf("Match found %d!\n", omp_get_thread_num());
                flag = 1;
            }
        }
    }
}

Upvotes: 2

Related Questions