1

I just started to learn about OpenMP and I found this code below

#pragma omp parallel for
for (int i = 1; i < N; i++) { A[i] = B[i] – A[i – 1]; }

I wonder would it be possible to parallelize this loop?

2 Answers 2

1

Here’s equivalent code that only reads from 1 array:

auto a = A[ 0 ];
for( int i = 1; i < N; i++ )
{
    a = B[ i ] - a;
    A[ i ] = a;
}

As you see, you have data dependency between adjacent loop iterations, i.e. the result depends on the previous iteration step. Usually it’s not possible to parallelize such algorithms.

BTW, if your values are floats, integers or something equally fast to compute operator - on them, the speed of the code might be limited by RAM bandwidth, not by computations. Parallelizing wouldn’t help much.

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

1 Comment

Thanks for your reply, it really help me to understand it :3
0

I would say no (at least not in a way it would worth). Consider the way of underlying parallelization with using two threads:

// thread # 1
for(int i = 1; i < N / 2; i++) { A[i] = B[i] – A[i – 1]; }

// thread # 2
for(int i = N / 2; i < N; i++) { A[i] = B[i] – A[i – 1]; }

The threads will be working in parallel so second thread will calculate A[N / 2] based on A[N / 2 - 1] which is probably not yet calculated by the first thread. If you would find a way to pre-calculate the "adjacent" items (e.g. N / 2 - 1 in our case) then it could work. But for doing so, you should traverse all elements until N / 2. You might also do some arithmetic tricks to pre-calculate some elements but then you should have another loops which would make parallelization ineffective...

1 Comment

Thanks a lot for the reply, I think I understand now :))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.