flush: example A.2.2.c p. 225

Forum for the public review of the OpenMP 4.0 API Release Candidates. (Read Only)
Forum rules
This forum is now closed.

flush: example A.2.2.c p. 225

Postby muphof » Wed Mar 27, 2013 4:39 pm

This regards Version 4.0 - RC 2 - March 2013 Public Review Release Candidate 2.

This example is a bit puzzling. I have looked for an explanation on forums but I could not find anything. This is the example illustrating pitfalls with flush.

As far as I can tell, flag at any given time can only be equal to 0 or 1. Because of the while condition on line 29, flag must be 1 on line 34. How can it be undefined?

Similarly, if flag must be 1 on line 34, data=42 must have been written to memory by thread 0 (line 18). The flush by thread 1 (line 28 or 31) must occur after line 20 has executed. Therefore thread 1 must be able to see the updated value of data.

This reasoning is contradictory with the statement in the specification:
"The following example demonstrates why synchronization is difficult to perform correctly through variables. The value of flag is undefined in both prints on thread 1 and the value of data is only well-defined in the second print."

Could anyone explain this?

Thank you.
muphof
 
Posts: 5
Joined: Wed Mar 27, 2013 4:17 pm

Re: flush: example A.2.2.c p. 225

Postby MarkB » Thu Mar 28, 2013 7:33 am

Hi there,

muphof wrote:This example is a bit puzzling


You're not the first person to say that!

muphof wrote:As far as I can tell, flag at any given time can only be equal to 0 or 1.


This seems reasonable, but is only true if writes are assumed to be atomic, which OpenMP memory model (deliberately) does not do, because the
data types for which writes are atomic can very between platforms. In practice, on most hardware, writes of 32-bit integers are atomic, but in principle they might not be, and therefore a read of a variable while another thread is in the process of writing it could return an undefined value which is neither 0 nor 1.

The value of flag is undefined in both prints on thread 1 because it cannot be guaranteed that any the flushes of flag on thread 1 happened after the final flush of flag on thread 0.

Hope that helps,
Mark.
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: flush: example A.2.2.c p. 225

Postby muphof » Thu Mar 28, 2013 9:35 am

Hi Mark,

Thank you for your explanation. It does help answer the first part of my question. I understand that if writes and reads are not atomic, the value of flag is indeed undefined.

However let us consider the case of data=42 now. The specification claims that data is undefined at line 34. Let's see if this is possible.

For thread 1 to reach line 34, thread 0 must have started executing line 20. This is true even if we assume non-atomic read/writes. Looking at this more closely, there is a strict sequential order (if we assume non-atomic read/writes, the order is only for starting the instruction not for completing it):
thread 0: line 18
thread 0: line 20 // Line 18 must be complete. At that point data=42 in memory and thread 1 will get that value at its next flush
thread 1: line 28 or 31 and flag becomes non-zero for thread 1
The previous state cannot occur before line 18 is complete. Therefore if the flush by thread 1 on line 28 or 31 returns a flag that is not zero, it must also force thread 1 to correctly read the new value of data=42.

Thank you for looking more into this.
muphof
 
Posts: 5
Joined: Wed Mar 27, 2013 4:17 pm

Re: flush: example A.2.2.c p. 225

Postby MarkB » Thu Mar 28, 2013 10:31 am

Your reasoning is correct for how typical hardware works, but the OpenMP memory model is weaker than that of most typical hardware (deliberately so, in order for it to be widely implementable).

A possible sequence of events is:

thread 1: flush (line 28)
thread 0: data = 42 (line 14)
thread 0: flush (line 18)
thread 0: flag = 1 (line 20)
thread 1: while (flag < 1) test fails (line 29)
thread 1: read data (line 34)

which fails to satisfy the required write(0)-flush(0)-flush(1)-read(1) ordering (see top of page 18 of 4.0 RC2).
After the flush on line 35, the ordering is now guaranteed, and data is then valid.



Thank you for looking more into this.


You're very welcome!
Mark.
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: flush: example A.2.2.c p. 225

Postby muphof » Thu Mar 28, 2013 11:07 am

OK. I got it. What I was not seeing is that it is possible for flag to become >= 1 without doing the flush on line 31. In that case, you may not see the update on data. However since at that point thread 0 must have moved past line 18, the second flush by thread 1 on line 35 will force a read on data=42.

I guess my only advice would be to add a few lines on p. 224 to explain this. For example we could mention the following:

The following example demonstrates why synchronization is difficult to perform correctly through variables. The value of flag is undefined in both prints on thread 1 and the value of data is only well-defined in the second print. The value of flag is undefined because read/writes are not guaranteed to be atomic. Therefore the value read by thread 1 is undefined. The value of data is undefined in the first print because it is not possible to guarantee that either flush by thread 1 on line 28 or 31 happens after the flush by thread 0 on line 18 completes. In particular flag may be read by thread 1 without ever executing the flush on line 31. However, the second flush on line 35 necessarily gets the updated value for data.
muphof
 
Posts: 5
Joined: Wed Mar 27, 2013 4:17 pm

Re: flush: example A.2.2.c p. 225

Postby MarkB » Fri Mar 29, 2013 4:08 am

muphof wrote:I guess my only advice would be to add a few lines on p. 224 to explain this.


I agree that this example could use some better commentary!
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am


Return to OpenMP 4.0 Public Review Release Candidates

Who is online

Users browsing this forum: No registered users and 1 guest