OpenMP: Locking access to single array elements?

Question

I'm fairly new to OpenMP, so this may have an easy answer, but I haven't been able to find it.

Suppose I have the following C code and want to parallelize it using OpenMP. A is an array of objects which have some double value less than 1 buckets is an array of linked lists, and append adds a pointer to an object to the end fo a linked list.

#pragma omp for 
for (i = 0; i < n; ++i) {
    x = (int) (A[i].val * NUM_BUCKETS);
    append(&A[i], buckets[x]);
} 

The problem is that multiple threads may be trying to append items to a given bucket at one time. I could make that append statement critical. However, in my application, I'll probably have ~1000 buckets or so, so the large majority of the time the threads will be operating on different buckets.

Is there a way to enforce locks on the individual elements of buckets? Or some other way of handling this?

Answer 1

Well, OpenMP can't do it for you automatically, but it lets you create your own lock variables which you can use to limit access to array elements; for instance, you could have one lock per array element:

#include <stdio.h>
#include <omp.h>


int main(int argc, char **argv)
{
    const int NITEMS=20;
    int array[NITEMS];
    omp_lock_t lock[NITEMS];

    for (int i=0; i<NITEMS; i++)
        omp_init_lock(&(lock[i]));

#pragma omp parallel for shared(array, lock) default(none)
     for (int i=0; i<NITEMS; i++) {
        int tid = omp_get_thread_num();
        int item = (i * 7) % NITEMS;

        omp_set_lock(&(lock[item]));
        array[item] = tid;    // only one thread in here at a time; others block at set_lock()
        omp_unset_lock(&(lock[item]));
    }

    for (int i=0; i<NITEMS; i++)
        printf("%3d ", array[i]);
    printf("\n");

    for (int i=0; i<NITEMS; i++)
        omp_destroy_lock(&(lock[i]));


    return 0;
}

Or, if that level of granularity were more than you needed, you could block regions of the array, etc.