At 12:17 PM 7/10/2002, Bill Pugh wrote:
I think the problem is that some of us, including myself, don't see any
possible allowable reordering that results in r1 = 1.
To repeat a bit of Bill's email.
>Applying this transformation to case 2 could yield:
>
>Initially, x = 0
>
>Thread 1:
>// move from canonical location:
>x1 = x
>// main body:
>r1 = x1
>x2 = 1
>// move back to canonical location:
>x = x2
>Thread 2:
>// move from canonical location:
>x2 = x
>// main body:
>r2 = x2
>x1 = r2
>// move back to canonical location:
>x = x1
>
>which can then be reordered by the compiler or processor to result in r1 = 1.
Assuming that x1 and x2 are local to the threads, then I think only way
that r1 can get 1 is by having the operations in Thread 1 have the ordering
t1.x2=1 --> x=t1.x2 --> t1.x1=x --> r1=t1.x1
But this ordering of the operations in thread 1 isn't allowed because of
the anti-dependence that requires t1.x1=x --> x=t1.x2
I don't have a proof, I don't think there is any way to interleave
operations in thread 2 with a different ordering of the operations in
thread 1 and still result in r1==1 at the end.
An informal argument goes like this: The only way that the operations in
thread 2 can affect thread 1 and result in r1==1 at the end is if t2.x2=x
--> x=t2.x1-->t1.x1=x, and the value fetched by t2.x2=x is 1.
But then the order would have to be.
t1.x2=1 --> x=t1.x2 --> t2.x2=x --> x=t2.x1 --> t1.x1=x --> r1=t1.x1.
>The questions is whether
>
>>* Case 2:
>>
>>Thread 1 Thread 2
>>
>>r1 = x; r2 = x;
>>x = 1; x = r2;
>
>Can result in r1=1.
>
>
>
>At 5:40 PM -0600 7/9/02, Yue Yang wrote:
>>It seems to me that reading back future write on the same variable from
>>the same thread would make programming a lot harder and more error prone.
>>
>>This behavior is very counterintuitive because most people expect to get
>>serial result, i.e., the value from the most rescent previous write, if
>>it comes from the same thread.
>
>I think you are misunderstanding or misrepresenting what is occurring.
>
>a read of a variable x by thread t does see the most recent previous write
>to x by thread t if it sees a write by thread t. In case 2, it isn't
>seeing a write by the same thread.
>
>>
>>If this relaxation is permitted by the JMM, to make sure a read won't be
>>fullfilled by a later write, a memory barrier has to be inserted in the
>>program after every read if the same variable might be rewritten in the
>>future.
>
>This is only a problem if you have other threads that are reading values
>and writing them back without using synchronization. Nobody should be
>doing that.
>I can't imagine any realistic use cases or errors where the problem you
>describe arises.
>
>>
>>
>>Questions for all experts in this group:
>>
>>Are their any existing memory models that allow such behavior, i.e.,
>>reading back future write at the same location from the same process?
>>
>>Are there any existing or future implementations that might have to take
>>advantage of this kind of relaxation?
>>
>>Thanks!
>>
>>-- Jason
>
>
>It is a bit of a stretch, but I can imagine a few:
>
>* In a compiler, perform privatization or ssa renaming to create multiple
>names/storage locations for a single variable, allowing more reordering
>and overlapping of loads and stores. Always move current value back to the
>conical location before synchronization.
>
>Applying this transformation to case 2 could yield:
>
>Initially, x = 0
>
>Thread 1:
>// move from canonical location:
>x1 = x
>// main body:
>r1 = x1
>x2 = 1
>// move back to canonical location:
>x = x2
>
>Thread 2:
>// move from canonical location:
>x2 = x
>// main body:
>r2 = x2
>x1 = r2
>// move back to canonical location:
>x = x1
>
>which can then be reordered by the compiler or processor to result in r1 = 1.
>
>* Allow prescient stores in a processor architecture. A prescient store goes
> into the write buffer, but is tagged so that it is not visible to the
> thread
> that initiated the prescient store until the store is committed.
>
>
>I'll admit that the case for allowing case 2 to enable efficient
>implementations is weak. However, I think that disallowing case 2 would
>further complicate the memory model, and I don't see any compelling
>reasons from the programmer side to disallow case 2. Incorrectly
>synchronized programs have weird behaviors, including case 2.
>
> Bill
>
>
>
>-------------------------------
>JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:40 EDT