Parallel operations in array with dependency

Question

I need help to solve this problem, I have a code with operations being performed on the previous element of the array, and I need to parallelize using openmp tasks, however I know how to remove this depency. My teacher says that in this case it is not interesting to use depend (in, out). How would I remove that depended on this then?

void sum_sequential(float a[N]) {
        a[0] = 1.0;

    for (int i = 1; i < N; i++)
        a[i] = 2 * a[i-1] + 1;
}

Do you want a closed form solution?

MFisherKDX
– MFisherKDX

2019-04-09 19:20:55 +00:00
Commented Apr 9, 2019 at 19:20 — MFisherKDX
– MFisherKDX, Commented Apr 9, 2019 at 19:20

John Bollinger · Accepted Answer · 2019-04-09 19:21:18Z

1

You are quite right that there is is a data dependency. The value to be computed for each element is expressed in terms of the value previously computed for the preceding element, so this algorithm is inherently serial. There is no practical advantage in parallelizing it, as successfully dealing with the dependencies leaves no room for any concurrency.

HOWEVER, if you study the computation carefully, it is possible to re-express it in an algebraically equivalent way that does not have such dependencies -- an altogether different algorithm that produces the same results and is trivially parallelizable. At the risk of providing too big a hint, try writing out the first several terms of the results by hand, and see whether you recognize a simple pattern.

answered Apr 9, 2019 at 19:21

John Bollinger

190k11 gold badges102 silver badges206 bronze badges

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

2 Comments

SUdoW Over a year ago

In fact this sequence of operations can be expressed by a summation, and consequently can be simplified. The question was how to parallele this code, and as you said it is sequential. Tomorrow I will talk to my teacher about this exercise that I do not really see as paralleling. Thank you.

dader Over a year ago

@SUdoW can you accept john's answer please ? thank you.

Collectives™ on Stack Overflow

Parallel operations in array with dependency

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related