http://groups.google.com/group/comp.programming.threads?hl=en
comp.programming.threads@googlegroups.com
Today's topics:
* Weird unlocked behaviour? - 8 messages, 4 authors
http://groups.google.com/group/comp.programming.threads/t/62e5cced42865212?hl=en
* removing store/load in Peterson's algorithm? - 2 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/6a7e7620b0cd85eb?hl=en
==============================================================================
TOPIC: Weird unlocked behaviour?
http://groups.google.com/group/comp.programming.threads/t/62e5cced42865212?hl=en
==============================================================================
== 1 of 8 ==
Date: Tues, Dec 22 2009 10:03 pm
From: frege
On Dec 22, 9:49 am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
> I'm now trying to track an error that seems to indicate that at some
> later moment in time, the *same* thread gets a *lower* value for
> generation (++ is the *only* write-operation and this is surely no
> integer overflow). That is fatal for the app :-(
>
> How can this happen?
++g is 3 steps: read add write
let's look at an example:
g == 0
thread1 reads g (== 0)
thread2 reads g (0)
thread1 adds then writes g (1)
threadn reads adds writes g (2)
thread1 reads adds writes g (3)
thread2 adds 1 to it's old value of g (1)
thread2 writes g (1)
thread1 reads adds writes g (2)
thread1 previously saw g as 3 now sees it as 2.
Or other variations. Basically a lot can happen between the read then
the write!
Tony
== 2 of 8 ==
Date: Wed, Dec 23 2009 12:35 am
From: Jan Wielemaker
On 2009-12-22, David Schwartz <davids@webmaster.com> wrote:
> On Dec 22, 7:27 am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
>
>> Ok, without atomic increment a thread can be preempted between reading
>> and writing while others keep incrementing.
>
> Exactly.
:-)
>> I guess it is also possible
>> that the thread doing ++generation reads an outdated value from its
>> cache.
>
> An outdated value in the caches would not be valid, and so the CPU
> would not use it until it could make it valid. A CPU will not modify a
> value in cacheable memory unless that value is exclusively held in
> that CPU's cache. The cache coherency hardware guarantees, logically
> enough, that the caches are coherent.
Hmmm. Do I understand this? I always thought that if CPU 1 writes to
an address, any other CPU may get the value prior to this writing action
as long as no synchronisation action has taken place. Is this not true?
And, if it is not true, is it not true for all hardware, or just not for
Intel/AMD IA32/X64?
Cheers --- Jan
== 3 of 8 ==
Date: Wed, Dec 23 2009 2:06 am
From: Dmitriy Vyukov
On Dec 23, 11:35 am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
> On 2009-12-22, David Schwartz <dav...@webmaster.com> wrote:
>
> > On Dec 22, 7:27 am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
>
> >> Ok, without atomic increment a thread can be preempted between reading
> >> and writing while others keep incrementing.
>
> > Exactly.
>
> :-)
>
> >> I guess it is also possible
> >> that the thread doing ++generation reads an outdated value from its
> >> cache.
>
> > An outdated value in the caches would not be valid, and so the CPU
> > would not use it until it could make it valid. A CPU will not modify a
> > value in cacheable memory unless that value is exclusively held in
> > that CPU's cache. The cache coherency hardware guarantees, logically
> > enough, that the caches are coherent.
>
> Hmmm. Do I understand this? I always thought that if CPU 1 writes to
> an address, any other CPU may get the value prior to this writing action
> as long as no synchronisation action has taken place. Is this not true?
> And, if it is not true, is it not true for all hardware, or just not for
> Intel/AMD IA32/X64?
It can and it can't at the same time. It actually depends on how you
define the term "prior". Note that there is no single time in
distributed systems.
It's usually considered as CPU1 always sees prior writes from CPU2.
But the statement is basically senseless, because it's by definition,
it's prior because CPU1 has seen it. There is basically no other way
to define the term "prior" other than by means of visibility. Thus,
one can't define 'visibility' by means of 'prior', otherwise there
will be cyclic dependency between terms.
Synchronization actions has nothing to do with visibility, then relate
only to mutual ordering (non-coherent systems aside for a moment).
--
Dmitriy V'jukov
== 4 of 8 ==
Date: Wed, Dec 23 2009 4:43 am
From: Jan Wielemaker
On 2009-12-23, Dmitriy Vyukov <dvyukov@gmail.com> wrote:
> On Dec 23, 11:35�am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
>> On 2009-12-22, David Schwartz <dav...@webmaster.com> wrote:
>>
>> > On Dec 22, 7:27�am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
>>
>> >> Ok, without atomic increment a thread can be preempted between reading
>> >> and writing while others keep incrementing.
>>
>> > Exactly.
>>
>> :-)
>>
>> >> I guess it is also possible
>> >> that the thread doing ++generation reads an outdated value from its
>> >> cache.
>>
>> > An outdated value in the caches would not be valid, and so the CPU
>> > would not use it until it could make it valid. A CPU will not modify a
>> > value in cacheable memory unless that value is exclusively held in
>> > that CPU's cache. The cache coherency hardware guarantees, logically
>> > enough, that the caches are coherent.
>>
>> Hmmm. �Do I understand this? �I always thought that if CPU 1 writes to
>> an address, any other CPU may get the value prior to this writing action
>> as long as no synchronisation action has taken place. �Is this not true?
>> And, if it is not true, is it not true for all hardware, or just not for
>> Intel/AMD IA32/X64?
>
> It can and it can't at the same time. It actually depends on how you
> define the term "prior". Note that there is no single time in
> distributed systems.
> It's usually considered as CPU1 always sees prior writes from CPU2.
> But the statement is basically senseless, because it's by definition,
> it's prior because CPU1 has seen it. There is basically no other way
> to define the term "prior" other than by means of visibility. Thus,
> one can't define 'visibility' by means of 'prior', otherwise there
> will be cyclic dependency between terms.
Hi Dmitriy,
I was talking about time as we all preceive it: wall-time and next I was
trying to grasp visibility. I know this is a bit naive way to think about it,
but afterall it is way of looking at the behaviour if you do not do anything
special multi-threaded/core related. I.e. you have two threads running that
poke in shared memory addresses without using explicit communication.
> Synchronization actions has nothing to do with visibility, then relate
> only to mutual ordering (non-coherent systems aside for a moment).
I guess it is time for some more reading :-)
Cheers --- Jan
== 5 of 8 ==
Date: Wed, Dec 23 2009 7:24 am
From: Dmitriy Vyukov
On Dec 23, 3:43 pm, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
> >> >> I guess it is also possible
> >> >> that the thread doing ++generation reads an outdated value from its
> >> >> cache.
>
> >> > An outdated value in the caches would not be valid, and so the CPU
> >> > would not use it until it could make it valid. A CPU will not modify a
> >> > value in cacheable memory unless that value is exclusively held in
> >> > that CPU's cache. The cache coherency hardware guarantees, logically
> >> > enough, that the caches are coherent.
>
> >> Hmmm. Do I understand this? I always thought that if CPU 1 writes to
> >> an address, any other CPU may get the value prior to this writing action
> >> as long as no synchronisation action has taken place. Is this not true?
> >> And, if it is not true, is it not true for all hardware, or just not for
> >> Intel/AMD IA32/X64?
>
> > It can and it can't at the same time. It actually depends on how you
> > define the term "prior". Note that there is no single time in
> > distributed systems.
> > It's usually considered as CPU1 always sees prior writes from CPU2.
> > But the statement is basically senseless, because it's by definition,
> > it's prior because CPU1 has seen it. There is basically no other way
> > to define the term "prior" other than by means of visibility. Thus,
> > one can't define 'visibility' by means of 'prior', otherwise there
> > will be cyclic dependency between terms.
>
> Hi Dmitriy,
>
> I was talking about time as we all preceive it: wall-time and next I was
> trying to grasp visibility. I know this is a bit naive way to think about it,
> but afterall it is way of looking at the behaviour if you do not do anything
> special multi-threaded/core related. I.e. you have two threads running that
> poke in shared memory addresses without using explicit communication.
From this point of view: (1) if you think on second-scale level then
all writes are visible instantly (for cache-coherent systems), (2) if
you think on nanosecond-scale level then writes become visible some
arbitrary time later. Rough reference number: 100-1000 cycles.
Regarding "synchronization actions", there is no way to speedup
propagation of changes. If there would be a one, it would be turned on
by default for all writes.
That's for hardware. But there is also an issue wrt compilers. If you
program in C/C++, then compiler may leave any write in register and
not push it to memory subsystem. That way write may actually not
become visible to other threads for seconds/minutes/hours.
--
Dmitriy V'jukov
== 6 of 8 ==
Date: Wed, Dec 23 2009 8:40 am
From: frege
On Dec 23, 3:35 am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
> On 2009-12-22, David Schwartz <dav...@webmaster.com> wrote:
>
> >> I guess it is also possible
> >> that the thread doing ++generation reads an outdated value from its
> >> cache.
>
> > An outdated value in the caches would not be valid, and so the CPU
> > would not use it until it could make it valid. A CPU will not modify a
> > value in cacheable memory unless that value is exclusively held in
> > that CPU's cache. The cache coherency hardware guarantees, logically
> > enough, that the caches are coherent.
>
> Hmmm. Do I understand this? I always thought that if CPU 1 writes to
> an address, any other CPU may get the value prior to this writing action
> as long as no synchronisation action has taken place. Is this not true?
> And, if it is not true, is it not true for all hardware, or just not for
> Intel/AMD IA32/X64?
>
> Cheers --- Jan
Another CPU may get the value "prior" to this writing action because
it actually *read* the value *prior* to it being written! ie the read
got reordered to happen before when you thought it happened. If you
try to *guarantee* the order of the read/write, then you can only do
so via a synchronization action. If you try to 'detect' when things
are written (via if() statements instead of sync primitives) then
speculative reads and reordering may still have the read happen before
the write.
In other words, you can't tear open the case of your computer and look
at the memory values directly. You can only 'see' them via CPUs, and
thus your are getting a CPU's view of things, not the 'wall clock'
view.
Tony
== 7 of 8 ==
Date: Wed, Dec 23 2009 11:26 am
From: David Schwartz
On Dec 23, 12:35 am, Jan Wielemaker <j...@hppc323.few.vu.nl> wrote:
> > An outdated value in the caches would not be valid, and so the CPU
> > would not use it until it could make it valid. A CPU will not modify a
> > value in cacheable memory unless that value is exclusively held in
> > that CPU's cache. The cache coherency hardware guarantees, logically
> > enough, that the caches are coherent.
> Hmmm. Do I understand this? I always thought that if CPU 1 writes to
> an address, any other CPU may get the value prior to this writing action
> as long as no synchronisation action has taken place. Is this not true?
It is true, but it's not due to the CPU reading from a cache. It's due
to two things:
1) The CPU that does the write may hold the write in a write posting
buffer. This may cause the write to not be visible on other CPUs until
much later than normal program sequence would suggest.
2) The CPU that does the read may pre-fetch the read and acquire the
data earlier than the normal program sequence would suggest.
DS
== 8 of 8 ==
Date: Wed, Dec 23 2009 11:29 am
From: David Schwartz
On Dec 23, 8:40 am, frege <gottlobfr...@gmail.com> wrote:
> Another CPU may get the value "prior" to this writing action because
> it actually *read* the value *prior* to it being written! ie the read
> got reordered to happen before when you thought it happened. If you
> try to *guarantee* the order of the read/write, then you can only do
> so via a synchronization action. If you try to 'detect' when things
> are written (via if() statements instead of sync primitives) then
> speculative reads and reordering may still have the read happen before
> the write.
Exactly! The incorrect assumption is that the CPU executes your code
in the same order you wrote it. The CPU executes your code so that the
effect is the same as if it executed your code in the same order you
write it if, and only if, you follow the rules.
If you have dependencies in your code that are not allowed by the
platform specification, then CPU superscalar optimizations may cause
your code to execute differently than it should. For example, if you
have:
a=1;
b=2;
And these two writes are to normal memory, there is no reason the CPU
can't reorder them if it's more efficient for it to execute them in
the other order. Similarly, if you have:
a=c;
b=d;
If these two reads are from normal memory and 'a' and 'b' are in
registers, there's no reason the CPU can't reorder the two reads if it
wants to.
So it's the CPU itself that causes the problem. Reads and writes are
only required to occur in the exact order the code specifies them if
there's a reason they must that's made known to the CPU. If there's a
reason they must occur in the specified order and that reason is not
made known to the CPU, the code will fail.
DS
==============================================================================
TOPIC: removing store/load in Peterson's algorithm?
http://groups.google.com/group/comp.programming.threads/t/6a7e7620b0cd85eb?hl=en
==============================================================================
== 1 of 2 ==
Date: Wed, Dec 23 2009 11:29 am
From: "James"
> "Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
> news:756561b8-810a-40ef-99e1-ff7138e13661@g7g2000yqa.googlegroups.com...
On Dec 21, 8:32 pm, "James" <n...@spam.invalid> wrote:
[...]
> > > > STORE16(&state1, 1);
> > > > LOAD32(&state1);
> > > > LOAD32(&state2);
> >
> > > > Can the load from state2 rise above the 16-bit store? It seems like
> > > > it
> > > > should be able to. Where am I going wrong?
> >
> > > > [...]
> > > Yes, it can. But there is no such code in Peterson algorithm, there is
> > > only 1 load.
> >
> > I was referring to a load that occurred within the critical section. Can
> > loads from the critical section rise above the 16-bit store? Can that
> > cause
> > any problems?
> I can only cite myself:
> I think one need only #LoadLoad | #LoadStore:
> STORE16(&state, 1);
> LOAD32(&state);
> if (...) ...
> membar #LoadLoad | #LoadStore; //no-op for SPARC TSO and x86
> // nothing from here can hoist above mutex acquisition
But the:
STORE16(&state, 1);
LOAD32(&state);
will not prevent a store from within the critical section from rising above
it. This would mess things up right?
== 2 of 2 ==
Date: Wed, Dec 23 2009 11:32 am
From: "James"
"Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
news:ad5c3755-23c5-42b8-b7b3-3ecfb3f29b53@c3g2000yqd.googlegroups.com...
On Dec 21, 10:23 pm, "James" <n...@spam.invalid> wrote:
[...]
> > For the MFENCE version I am performing a 32-bit store to location a, an
> > MFENCE then a 32-bit load from location b.
> >
> > For the collocation version I am performing a 16-bit store to location a
> > then a 32-bit load from location a.
> >
> > That should be fair?
> Yes.
> > > I think that if collocation is observably faster than MFENCE then that
> > > means that it just does not work.
> >
> > The MFENCE version of the test is much slower than the collocation
> > version.
> > So, does the collocation trick not work on an x86?
> The first question I would answer is: does Peterson algorithm with
> collocation actually provide mutual exclusion on x86 (is it guaranteed
> or just seems to work on some processors)? If the answer is No then
> performance of collocation is irrelevant for me.
I simply don't know if it works on x86. I don't know who to ask in order to
verify this. I could create a test which does not prove anything even if it
passes a hundred trillion times. Can you think of a way to verify that
collocation works on x86?
==============================================================================
You received this message because you are subscribed to the Google Groups "comp.programming.threads"
group.
To post to this group, visit http://groups.google.com/group/comp.programming.threads?hl=en
To unsubscribe from this group, send email to comp.programming.threads+unsubscribe@googlegroups.com
To change the way you get mail from this group, visit:
http://groups.google.com/group/comp.programming.threads/subscribe?hl=en
To report abuse, send email explaining the problem to abuse@googlegroups.com
==============================================================================
Google Groups: http://groups.google.com/?hl=en
No comments:
Post a Comment