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?
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.
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...