Is this the correct use of 'restrict' in C?

Question

Currently I'm learning about parallel programming. I have the following loop that needs to be parallelized.

for(i=0; i<n/2; i++)
   a[i] = a[i+1] + a[2*i]

If I run this sequentially there is no problem, but if I want to run this in parallel, there occurs data recurrence. To avoid this I want to store the information to 'read' in a seperate variable e.g b.

So then the code would be:

b = a;
#pragma omp parallel for private(i)
for(i=0; i<n/2; i++)
  a[i] = b[i+1] + b[2*i];

But here comes the part I where I begin to doubt. Probably the variable b will point to the same memory location as a. So the second code block will do exactly as the first code block. Including recurrence I'm trying to avoid.

I tried something with * restric {variable}. Unfortunately I can't really find the right documentation.

My question:

Do I avoid data recurrence by writing the code as follows?

int *restrict b;
int *restrict a;
b = a;

#pragma omp parallel for private(i)
for(i=0; i<n/2; i++)
   a[i] = b[i+1] + b[2*i];

If not, what is a correct way to achieve this goal?

Thanks, Ter

Answer 1

In your proposed code:

int *restrict b;
int *restrict a;
b = a;

the assignment of a to b violates the restrict requirement. That requires that a and b do not point to the same memory, yet they clearly do point to the same memory. It is not safe.

You'd have to.make a separately allocated copy of the array to be safe. You could do that with:

int *b = malloc(n * size of(*b));
…error check…;
memmove(b, a, n *sizeof(*b));
…revised loop using a and b…
free(b);

I always use memmove() because it is always correct, dealing with overlapping copies. In this case, it would be legitimate to use memcpy() because the space allocated for b will be separate from the space for a. The system would be broken if the newly allocated space for b overlaps with a at all, assuming the pointer to a is valid. If there was an overlap, the trouble would be that a was allocated and freed — so a is a dangling pointer pointing to released memory (and should not be being used at all), and b was coincidentally allocated where the old a was previously allocated. On the whole, it's not a problem worth worrying about. (Using memmove() doesn't help if a is a dangling pointer, but it is always safe if given valid pointers, even if the areas of memory overlap.)