As promised, here's the correspondence with Sandhya for reference.
Sarita
-----Original Message-----
From: Sarita Adve [mailto:sadve@cs.uiuc.edu]
Sent: Wednesday, March 17, 2004 9:49 PM
To: 'Willy Zwaenepoel'; 'alc@cs.rice.edu'; 'Sandhya@cs.rochester.edu'
Subject: Question on Treadmarks for the Java memory model
Hi all,
<chit-chat>
I am working with Bill Pugh and others to revise the Java memory model and
want to consult with you about a decision that I think would be quite
relevant to software DSMs.
The definition of LRC in ISCA'92 says that happens-before is established
from a release to an acquire if the acquire reads the value of the release.
An alternative definition of happens-before would establish the order from a
release to *any* later acquire to the same location. This is an issue for
programs that can have concurrent releases to the same location, say rel1
and rel2, and an acquire reads one of them, say rel2. The alternative
definition assumes a total ordering between conflicting releases, say rel1
before rel2. Based on this, the definition would induce a happens-before
from rel1 to the acquire, even though the acquire does not return the value
of rel1.
Do you see an advantage/disadvantage for either definition for software
DSMs?
Specifically for Treadmarks implementations, my recollection is that they
supported locks, barriers, and (maybe) single writer/multiple reader flags.
I don't recall support for more general synchronization idioms such as any
using concurrent synchronization writes to the same location. Is that
correct? If not, then which definition did Treadmarks implement?
I am writing to everyone because we need to make a decision relatively soon,
and am hoping one of you will have the time to respond.
Thanks,
Sarita
-----Original Message-----
From: Sandhya Dwarkadas [mailto:sandhya@cs.rochester.edu]
Sent: Wednesday, March 17, 2004 10:08 PM
To: Sarita Adve
Cc: 'Willy Zwaenepoel'; alc@cs.rice.edu; Sandhya Dwarkadas
Subject: Re: Question on Treadmarks for the Java memory model
>
> Specifically for Treadmarks implementations, my recollection is that
> they supported locks, barriers, and (maybe) single writer/multiple
> reader flags. I don't recall support for more general synchronization
> idioms such as any using concurrent synchronization writes to the same
> location. Is that correct? If not, then which definition did
> Treadmarks implement?
>
That is correct. Can you give me an example of what you have in mind with
using concurrent synchronization writes to the same location?
Sandhya
-----Original Message-----
From: Sarita Adve [mailto:sadve@cs.uiuc.edu]
Sent: Wednesday, March 17, 2004 10:49 PM
To: 'Sandhya Dwarkadas'
Cc: 'Willy Zwaenepoel'; alc@cs.rice.edu
Subject: RE: Question on Treadmarks for the Java memory model
Thanks for the super-quick response! Here's an example:
Initially, X = Y = S = 0.
S is a synchronization variable.
Thread 1:
X = 1
S = 0
r1 = S
r2 = Y
Thread 2:
Y = 1
S = 0
r3 = S
r4 = X
The question is whether the behavior r2 == r4 == 0 is possible?
With the first definition of hb I gave, the behavior would be possible under
LRC - each thread could read its own write of S. So there is no
happens-before across threads. So the reads of X and Y are free to return 0.
With the second definition I gave, one of the two S=0 writes will be ordered
first. Say Thread 1's is ordered first. So Thread 2's read of S is ordered
after Thread 1's write of S. So X=1 happens-before r4=X. So the read of X
must see 1. Similarly, if Thread 2's S=0 is ordered before Thread 1's S=0,
then the read of Y must return 1. So in no case can r2==r4==0.
So the question is: if you had to pick one definition from a software DSM
point of view, which would you pick?
Thanks,
Sarita
-----Original Message-----
From: Sandhya Dwarkadas [mailto:sandhya@cs.rochester.edu]
Sent: Monday, March 22, 2004 9:34 AM
To: Sarita Adve
Cc: 'Willy Zwaenepoel'; alc@cs.rice.edu; Sandhya Dwarkadas
Subject: RE: Question on Treadmarks for the Java memory model
My apologies - I went out of town pretty much after replying to your last
message and did not have e-mail contact.
I'm curious, have you encountered realistic situations where this sort of
access pattern would be useful/used? I can imagine this to be the case
perhaps if a variable was being used as a flag, but ...
First, for SDSM, the acquires/releases would have to be explicitly
labeled. Second, serializing the releases without acquires in
between would in effect force the implementation to require each release
to be a combination acquire-release pair. This would mean that all
synchronization, whether or not it could be satisfied locally, would
require communication. So yes, the second definition would have
performance implications if strictly implemented unless the
synchronization operations where such ordering was required were
explicitly identified and dealt with separately.
Sandhya
-----Original Message-----
From: Sarita Adve [mailto:sadve@cs.uiuc.edu]
Sent: Monday, March 22, 2004 10:16 AM
To: 'Sandhya Dwarkadas'
Cc: 'Willy Zwaenepoel'; alc@cs.rice.edu
Subject: RE: Question on Treadmarks for the Java memory model
Thanks.
> I'm curious, have you encountered realistic situations where
> this sort of
> access pattern would be useful/used? I can imagine this to be
> the case
> perhaps if a variable was being used as a flag, but ...
Yes, that's really my point on this issue. There aren't many people who
will/can use this type of interaction correctly.
>
> First, for SDSM, the acquires/releases would have to be explicitly
> labeled.
Yes, that's for sure.
> Second, serializing the releases without acquires in
> between would in effect force the implementation to require
> each release
> to be a combination acquire-release pair. This would mean that all
> synchronization, whether or not it could be satisfied locally, would
> require communication. So yes, the second definition would have
> performance implications if strictly implemented unless the
> synchronization operations where such ordering was required were
> explicitly identified and dealt with separately.
Thanks. Another point to note is that the Java model will require all
synchronization to be sequentially consistent, regardless of which
definition of happens-before is chosen. So conflicting synchronization
writes will need to be serialized regardless of this discussion. The import
of the two happens-before definitions we are currently discussing is - when
would data need to be transferred along with the synchronization (through
diffs, etc.). My opinion is: The transferring of data will add extra
implementation complexity. How much is unclear (over and above the fact that
synchs have to be serialized anyway). Given that not many people will use
this, I prefer the weaker definition of happens-before (but it is not a huge
deal). Any further comments now?
Also, do you mind if I forward your messages to the Java model mailing list?
Thanks,
Sarita
-----Original Message-----
From: Sandhya Dwarkadas [mailto:sandhya@cs.rochester.edu]
Sent: Tuesday, March 23, 2004 3:55 PM
To: Sarita Adve
Cc: Sandhya Dwarkadas
Subject: RE: Question on Treadmarks for the Java memory model
>
> Also, do you mind if I forward your messages to the Java model mailing
> list?
>
No problem. I'll let you know if I have any further comments.
Regards,
Sandhya
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:01:01 EDT