5

I want to implement the following function that marks some elements of array by 1.

void mark(std::vector<signed char>& marker)
{
#pragma omp parallel for schedule(dynamic, M)
    for (int i = 0; i < marker.size; i++)
         marker[i] = 0;
#pragma omp parallel for schedule(dynamic, M)
    for (int i = 0; i < marker.size; i++)
         marker[getIndex(i)] = 1; // is it ok ?
}

What will happen if we try to set value of the same element to 1 in different threads at the same time? Will it be normally set to 1 or this loop may lead to unexpected behavior?

2
  • 1
    As long as no two or more values of i result in the same return value from getIndex(i), both operations are safe. Otherwise, only the first loop is guaranteed to be free of race conditions. Commented Sep 25, 2017 at 10:19
  • 1
    It's possible to do marker[getIndex(i)] = f(i) for where f(i) is not a constant as a function of i in parallel and get the same result as sequential code but it requires more clever code than what you have have now.
    – Z boson
    Commented Sep 25, 2017 at 12:59

2 Answers 2

4

This answer is wrong in one fundamental part (emphasis mine):

If you write with different threads to the very same location, you get a race condition. This is not necessarily undefined behaviour, but nevertheless it need to be avoided.

Having a look at the OpenMP standard, section 1.4.1 says (also emphasis mine):

If multiple threads write without synchronization to the same memory unit, including cases due to atomicity considerations as described above, then a data race occurs. Similarly, if at least one thread reads from a memory unit and at least one thread writes without synchronization to that same memory unit, including cases due to atomicity considerations as described above, then a data race occurs. If a data race occurs then the result of the program is unspecified.

Technically the OP snippet is in the undefined behavior realm. This implies that there is no guarantee on the behavior of the program until the UB is removed from it.

The simplest way to do it is to protect memory access with an atomic operation:

#pragma omp parallel for schedule(dynamic, M)
for (int i = 0; i < marker.size; i++)
#pragma omp atomic write seq_cst
     marker[getIndex(i)] = 1;

but that will probably hinder performance in a sensible way (as was correctly noted by @schorsch312).

7
  • That's interesting. I was not aware that this result is unspecified. I would like to hear more about this. Are there any examples where the result is unexpected (even theoretical discussions of possible OpenMP implementations on some special hardware)?
    – Z boson
    Commented Sep 26, 2017 at 8:38
  • 1
    The closest fit I know to what you ask for is the atomic<> weapons talk from Herb Sutter, that discusses at some point what is the relation between the load acquire / store release semantic and the instructions emitted on different architectures. He doesn't show examples of things blowing-up, but it goes into great details to explain why the semantic is wrong if you don't synchronize correctly. Commented Sep 26, 2017 at 13:01
  • 1
    Also, I am not sure if an atomic operation has an implicit flush. If marker is read concurrently while it's updated, it is better to ensure an additional flush as well. OpenMP spec says "Any atomic construct with a seq_cst clause forces the atomically performed operation to include an implicit flush operation without a list.", although I have only seen people to use seq_cst sub-clause when an atomic capture is used. Nonetheless, to be safe, I would probably use #pragma omp atomic write seq_cst in this case. Please correct me if I am wrong.
    – Sayan
    Commented Sep 26, 2017 at 22:34
  • 1
    @Sayan I think you're right in both comments - formally in the first one and substantially in the second one. For the first one I say formally because the expression is not listed in the allowed ones, but probably that came just by overlooking details - I think the code above is perfectly valid in previous standards and the intent of update is specified as the read and write of the location designated by x are performed mutually atomically. Commented Sep 27, 2017 at 3:55
  • 1
    There is no answer above. Commented Sep 29, 2017 at 15:18
3

If you write with different threads to the very same location, you get a race condition. This is not necessarily undefined behaviour, but nevertheless it need to be avoided.

Since, you write a "1" with all threads it might be ok, but if you write real data it is probably not.

Side note: In order to have a good numerical performance, you need to work on memory which is not too close to each other. If two threads are writing to two different elements in one cache line, this chunk of memory will be invalidated for all other threads. This will lead to a cache miss and will spoil your performance gain (parallel execution might be even slower than single threaded execution).

1
  • 1
    Good answer, one addition: In order to get a well-defined behavior, you must write using #pragma atomic write.
    – Zulan
    Commented Sep 25, 2017 at 10:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.