Why every time getting different output in openmp code?

Question

Every time I execute cal() function with the same parameter I get different output. Function g() always calculate the same result for same input. Are threads overwriting any variable?

void cal(uint_fast64_t n) {
    Bint num = N(n);
    Bint total = 0, i, max_size(__UINT64_MAX__);
    for(i = 1; i <= num; i+= max_size){
        #pragma omp parallel shared(i,num,total)  
        { 
            int id = omp_get_thread_num();
            int numthreads = omp_get_num_threads();
            Bint sum(0), k;
            for(uint64_t j = id; (j < __UINT64_MAX__); j+=numthreads){
                k = i+j;
                if(k > num){
                    i = k;
                    break;
                }
                sum = sum + g(k);
            }
            #pragma omp critical
                total += sum;
        }
    }
    std::cout << total << std::endl;
}

for(uint64_t j = id; (j < __UINT64_MAX__); j+=numthreads){ probably does not do what you want. The loop conditions is always true unless j == __UINT64_MAX__, which is impossible for e.g. even id and numthreads. But you have UB regardless so this is only secondary. — Max Langhof
– Max Langhof, Commented Sep 3, 2019 at 15:02
Its BigInt object to hold large numbers (>2^64). I am using this library. — Ajit Jadhav
– Ajit Jadhav, Commented Sep 3, 2019 at 15:12
Actually I am trying to solve this this problem programmatically. I computed H(10) but to solve H(10^9) uint64_t is also not sufficient.That's why I am using BigInt. — Ajit Jadhav
– Ajit Jadhav, Commented Sep 3, 2019 at 15:19

Max Langhof · Accepted Answer · 2019-09-03 14:53:02Z

7

if(k > num){
    i = k;
    break;
}

Here you modify the shared variable i (possibly multiple times in parallel) while other threads may be reading from it (for k = i+j), all without synchronization. This is a race condition and your code thus has Undefined Behavior.

edited Sep 3, 2019 at 14:53

answered Sep 3, 2019 at 14:47

Max Langhof

23.8k5 gold badges45 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ajit Jadhav Over a year ago

This is my single thread function:

void cal_single_thread(uint_fast64_t n) {     Bint num = N(n);     Bint sum = 0, i = 0;     for(i = 1; i <= num; ++i){         sum += g(i);     }     std::cout << sum << std::endl; }

How can i modify it for openmp ?

Max Langhof Over a year ago

@AjitJadhav There are several different ways, but comments are not the appropriate place to show those. In any case, I very much doubt that you will ever reach i >= __UINT64_MAX__. Do you know how large 2^64 is? 2^64 nanoseconds (~= CPU cycles) take 600 years.

Ajit Jadhav Over a year ago

Haha :).. you are right, I have to think in a different way to solve that! Anyway, due to that problem, I learned many things. Thank you all. I was surprised by the quick replies.

Alexis Wilke · Accepted Answer · 2019-09-03 14:46:53Z

The value of j depends on the value of id. If different threads are used to do the math, you'll get different results.

        int id = omp_get_thread_num();      // <---
        int numthreads = omp_get_num_threads();
        Bint sum(0), k;
        for(uint64_t j = id; (j < __UINT64_MAX__); j+=numthreads){  // <---
            k = i+j;
            if(k > num){
                i = k;      // <---
                break;
            }
            sum = sum + g(k);

Further, you change i to k when k > num. This can happen much sooner or much later depending on which thread is picked up first to run the inner loop.

You may want to look at this question and answer.

Does an OpenMP ordered for always assign parts of the loop to threads in order, too?

Collectives™ on Stack Overflow

Why every time getting different output in openmp code?

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related