Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #269 > unrolled thread

questions about memory_order_seq_cst fence

Started byMasakuni Oishi <yamasa@bsdhouse.org>
First post2011-06-13 09:40 -0700
Last post2011-06-15 02:06 -0700
Articles 20 on this page of 84 — 6 participants

Back to article view | Back to comp.programming.threads

Contents

  questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-13 09:40 -0700
    Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-06-13 22:39 +0200
      Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-14 08:27 -0700
        Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-06-16 00:21 +0200
          Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-15 15:48 -0700
            Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-16 05:03 -0700
          Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 08:35 +0100
            Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 12:05 +0200
              Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 11:19 +0100
                Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 13:57 +0200
                  Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 13:51 +0100
                    Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 16:53 +0200
                      Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 16:17 +0100
                        Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 17:37 +0200
                          Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 08:47 -0700
                          Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 16:54 +0100
                            Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 09:01 -0700
                              Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 17:07 +0100
                                Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 13:59 -0700
                                  Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-16 14:32 -0700
                                    Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-17 08:03 +0100
                                      Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-17 16:19 +0200
                                        Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-17 15:40 +0100
                                          Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-30 14:26 +0200
                                      Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-17 15:24 -0700
                                        Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 03:49 -0700
                                          Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-18 14:40 -0700
                                            Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 15:46 -0700
                                              Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-18 20:27 -0700
                                              Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 21:31 -0700
                                                Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 21:37 -0700
                                                  Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-20 15:45 -0700
                                                    Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-20 20:05 -0700
                                        Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-18 14:06 +0200
                            Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 18:32 +0200
                              Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 15:42 -0700
                              Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-07-10 19:47 +0200
                        Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 08:51 -0700
                          Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 17:23 +0100
                            Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 18:49 +0200
                        Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 08:51 -0700
                      Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 17:25 +0200
                        Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 16:56 +0100
                          Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-18 14:28 +0200
                            Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 09:54 +0100
                              Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-20 15:39 +0200
                              Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-22 13:24 +0200
            Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-06-16 14:39 +0200
              Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 13:55 +0100
          Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 12:03 +0200
            Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-07-10 19:10 +0200
    Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-13 16:00 -0700
      Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-13 23:31 -0700
        Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-14 08:32 -0700
    Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-14 23:05 +0100
      Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-14 16:44 -0700
        Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-15 08:34 +0100
          Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-15 02:11 -0700
          Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-15 15:58 -0700
          Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 08:26 +0100
            Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-16 05:05 -0700
              Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 13:11 +0100
                Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-18 15:42 +0200
                  Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 09:27 +0100
                    Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-20 15:30 +0200
                      Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 15:00 +0100
                        Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-21 14:54 +0200
                          Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-21 18:37 +0200
                        Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-21 15:59 +0200
                          Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-22 09:01 -0700
                  Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 15:41 +0100
                    Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-20 23:24 -0700
                      Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-22 10:46 -0700
                      Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-22 11:19 -0700
                        Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-22 11:57 -0700
                          Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-27 14:05 +0200
                            Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-29 16:14 -0700
                        Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-24 01:42 -0700
                          Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-27 13:24 +0200
                            Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-07-01 02:25 -0700
                              Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-07-01 12:48 +0200
        Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-15 01:53 -0700
          Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-15 02:57 -0700
      Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-15 02:06 -0700

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#293

FromMasakuni Oishi <yamasa@bsdhouse.org>
Date2011-06-16 05:05 -0700
Message-ID<4358686f-7bfb-480e-ae71-a8ce57566ab0@l14g2000pro.googlegroups.com>
In reply to#287
Anthony Williams <anthony....@gmail.com> wrote:
> Anthony Williams <anthony....@gmail.com> writes:
> > Joshua Maurice <joshuamaur...@gmail.com> writes:
>
> >>> 29.3p7 of N3290 says:
>
> >>> "For atomic operations A and B on an atomic object M, if there are
> >>> memory_order_seq_cst fences X and Y such that A is sequenced before X, Y
> >>> is sequenced before B, and X precedes Y in S, then B occurs later than A
> >>> in the modification order of M."
>
> >> I think it's meant to read:
> >> []
> >> For atomic **write (and atomic read-modify-write operations)** A and B
> >> on an atomic object M, if there are memory_order_seq_cst fences X and
> >> Y such that A is sequenced before X, Y is sequenced before B, and X
> >> precedes Y in S, then B occurs later than A in the modification order
> >> of M.
> >> [/]
>
> > When we drafted this words, I think we meant "operation". It is the
> > reference to "modification order" that is the typo. What is meant is
> > that if A is a write and B is a read then B must read the value written
> > by A, or something later in the modification order; if A is a write and
> > B is a write then B must be later than A in the MO; if A is a read and B
> > is a write then A must read a value prior to B in the MO, and if A is a
> > read and B is a read then B must read the same value as A or a value
> > later in the MO.
> > After rereading this section of the standard several times, I'm no
> > longer sure. I'll have to check my notes.
>
> I've checked my notes. My recollection was wrong.
>
> We *discussed* requiring seq_cst fences to order loads like this, but
> decided to explicitly limit the orderings to writes. The approved
> wording said "where A and B modify M", but this somehow got lost.
>
> In particular, it was felt that requiring this would add complexity to
> the IA-64 implementation of fences, and potentially require that relaxed
> operations on that architecture would also have to be more expensive,
> thus requiring people to pay for features they didn't need.

Interesting.
If so, for the code 1 in my first post, is the outcome
r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?

In fact, I encountered this problem when I was implementing
a variant of work-stealing deque (*).
And I'm dissatisfied with the result that the code 2 works well
but the code 1 doesn't.

(*) http://portal.acm.org/citation.cfm?doid=277651.277678

-- masakuni

[toc] | [prev] | [next] | [standalone]

#295

FromAnthony Williams <anthony.ajw@gmail.com>
Date2011-06-16 13:11 +0100
Message-ID<871uyuasc0.fsf@justsoftwaresolutions.co.uk>
In reply to#293
Masakuni Oishi <yamasa@bsdhouse.org> writes:

> If so, for the code 1 in my first post, is the outcome
> r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?

I believe so.

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

[toc] | [prev] | [next] | [standalone]

#324

FromAlexander Terekhov <terekhov@web.de>
Date2011-06-18 15:42 +0200
Message-ID<4DFCAB39.35CDACC8@web.de>
In reply to#295
Anthony Williams wrote:
> 
> Masakuni Oishi <yamasa@bsdhouse.org> writes:
> 
> > If so, for the code 1 in my first post, is the outcome
> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
> 
> I believe so.

Perhaps this is relevant:

http://download.intel.com/design/itanium/downloads/25142901.pdf

See 3.3.7.1 Total ordering of WB Releases. 

(remote write atomicity)

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#331

FromAnthony Williams <anthony.ajw@gmail.com>
Date2011-06-20 09:27 +0100
Message-ID<87oc1ssyaq.fsf@justsoftwaresolutions.co.uk>
In reply to#324
Alexander Terekhov <terekhov@web.de> writes:

> Anthony Williams wrote:
>> 
>> Masakuni Oishi <yamasa@bsdhouse.org> writes:
>> 
>> > If so, for the code 1 in my first post, is the outcome
>> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>> 
>> I believe so.
>
> Perhaps this is relevant:
>
> http://download.intel.com/design/itanium/downloads/25142901.pdf
>
> See 3.3.7.1 Total ordering of WB Releases. 
>
> (remote write atomicity)

Maybe I'm wrong; I am not an expert on IA-64 semantics.

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

[toc] | [prev] | [next] | [standalone]

#333

FromAlexander Terekhov <terekhov@web.de>
Date2011-06-20 15:30 +0200
Message-ID<4DFF4B71.20A46979@web.de>
In reply to#331
Anthony Williams wrote:
> 
> Alexander Terekhov <terekhov@web.de> writes:
> 
> > Anthony Williams wrote:
> >>
> >> Masakuni Oishi <yamasa@bsdhouse.org> writes:
> >>
> >> > If so, for the code 1 in my first post, is the outcome
> >> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
> >>
> >> I believe so.
> >
> > Perhaps this is relevant:
> >
> > http://download.intel.com/design/itanium/downloads/25142901.pdf
> >
> > See 3.3.7.1 Total ordering of WB Releases.
> >
> > (remote write atomicity)
> 
> Maybe I'm wrong; I am not an expert on IA-64 semantics.

Suppose that I can program in terms of C++MM's acquire/release. The
platform is x86.

How am I supposed to ensure remote write atomicity ala IA-64 releases
for a particular store (relevant loads) using C++MM and NOT pessimizing
everything to seq_cst?

The next question is regarding store-load fencing for particular
release-store and subsequent acquire-load.

If both can not be done easily under C++MM then it is pretty useless to
me.

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#335

FromAnthony Williams <anthony.ajw@gmail.com>
Date2011-06-20 15:00 +0100
Message-ID<871uyosiuw.fsf@justsoftwaresolutions.co.uk>
In reply to#333
Alexander Terekhov <terekhov@web.de> writes:

> Anthony Williams wrote:
>> 
>> Alexander Terekhov <terekhov@web.de> writes:
>> 
>> > Anthony Williams wrote:
>> >>
>> >> Masakuni Oishi <yamasa@bsdhouse.org> writes:
>> >>
>> >> > If so, for the code 1 in my first post, is the outcome
>> >> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>> >>
>> >> I believe so.
>> >
>> > Perhaps this is relevant:
>> >
>> > http://download.intel.com/design/itanium/downloads/25142901.pdf
>> >
>> > See 3.3.7.1 Total ordering of WB Releases.
>> >
>> > (remote write atomicity)
>> 
>> Maybe I'm wrong; I am not an expert on IA-64 semantics.
>
> Suppose that I can program in terms of C++MM's acquire/release. The
> platform is x86.
>
> How am I supposed to ensure remote write atomicity ala IA-64 releases
> for a particular store (relevant loads) using C++MM and NOT pessimizing
> everything to seq_cst?

In the general case, you can't. Acquire/release is essentially pairwise
synchronization in the C++0x MM; if you need a total order then you must
use seq_cst.

However, in particular cases then you can order particular subsets. If
you have an example of code that you would like to work then I can see
if I can think of a way to make it work without using seq_cst everywhere.

> The next question is regarding store-load fencing for particular
> release-store and subsequent acquire-load.

One issue here is that the terminology and effects of SPARC membar
constraints do not map cleanly onto C++0x ordering constraints. SPARC
membar constraints relate instruction order to global visibility
order. C++0x ordering constraints are transitive pairwise constraints
between processors, apart from seq_cst which is a global ordering on
seq_cst operations.

Consequently there is not always a simple 1-1 translation between the
two, but you should be able to achieve the same effects. If there are
cases where you can't, then I am interested to understand the issues,
and see how the C++ MM could be extended to handle the new cases.

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

[toc] | [prev] | [next] | [standalone]

#343

FromAlexander Terekhov <terekhov@web.de>
Date2011-06-21 14:54 +0200
Message-ID<4E009468.4B9FF511@web.de>
In reply to#335
Anthony Williams wrote:
[...]
> > Suppose that I can program in terms of C++MM's acquire/release. The
> > platform is x86.
> >
> > How am I supposed to ensure remote write atomicity ala IA-64 releases
> > for a particular store (relevant loads) using C++MM and NOT pessimizing
> > everything to seq_cst?
> 
> In the general case, you can't. Acquire/release is essentially pairwise
> synchronization in the C++0x MM; if you need a total order then you must
> use seq_cst.

I have no problem using seq_cst for either particular store or relevant
loads but I don't want to pessimizing everything to seq_cst.

> 
> However, in particular cases then you can order particular subsets. 

Please elaborate.

> If you have an example of code that you would like to work then I can 
> see if I can think of a way to make it work without using seq_cst 
> everywhere.
> 
> > The next question is regarding store-load fencing for particular
> > release-store and subsequent acquire-load.
> 
> One issue here is that the terminology and effects of SPARC membar
> constraints do not map cleanly onto C++0x ordering constraints. SPARC

Do you have an example for a C++MM's seq_cst fence actually not
providing a store-load barrier in compiled code on some platform?

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#347

FromAlexander Terekhov <terekhov@web.de>
Date2011-06-21 18:37 +0200
Message-ID<4E00C8BE.4A910747@web.de>
In reply to#343
Alexander Terekhov wrote:
> 
> Anthony Williams wrote:
> [...]
> > > Suppose that I can program in terms of C++MM's acquire/release. The
> > > platform is x86.
> > >
> > > How am I supposed to ensure remote write atomicity ala IA-64 releases
> > > for a particular store (relevant loads) using C++MM and NOT pessimizing
> > > everything to seq_cst?
> >
> > In the general case, you can't. Acquire/release is essentially pairwise
> > synchronization in the C++0x MM; if you need a total order then you must
> > use seq_cst.
> 
> I have no problem using seq_cst for either particular store or relevant
> loads ... 

I take that back. I'd rather get rid of seq_cst altogether.

atomic<>'s loads and stores ought to support the following 'modes':

  Whether load/store is competing (default) or not. Competing load 
  means that there might be concurrent store. Competing store means 
  that there might be concurrent load or store. Non-competing 
  load/store can be performed non-atomically.

  Whether competing load/store needs remote write atomicity (default 
  is no remote write atomicity). All competing loads/stores must 
  specify the same remote write atomicity mode.

  Whether load/store has specified reordering constraint (default 
  is no constraint specified) in terms of the following reordering 
  modes:

    Whether preceding loads (in program order) can be reordered 
    across it (can by default).

    Whether preceding stores (in program order) can be reordered 
    across it (can by default).

    Whether subsequent loads (in program order) can be reordered 
    across it (can by default). For load, the set of constrained 
    subsequent loads can be limited to only dependant loads (aka 
    'consume' mode).

    Whether subsequent stores (in program order) can be reordered 
    across it (can by default). For load, there is an implicit 
    reordering constraint regarding dependent stores (no need to 
    specify it).

    atomic<>'s fence operation can be used to specify reordering 
    constraint using the same modes.

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#344

FromAlexander Terekhov <terekhov@web.de>
Date2011-06-21 15:59 +0200
Message-ID<4E00A3D0.82D8E955@web.de>
In reply to#335
Anthony Williams wrote:

[... remote write atomicity ...]

> However, in particular cases then you can order particular subsets. If
> you have an example of code that you would like to work then I can see
> if I can think of a way to make it work without using seq_cst everywhere.

See examples in 

http://portal.acm.org/citation.cfm?id=1375591
("4.2 Unintended Consequences of Relaxing Write-Atomicity")

"4.2.1 Write-to-Read Causality (WRC) Must be Upheld"

"4.2.2 Read-to-Write Causality (RWC)"

"4.2.3 Subtle Interplay Between Coherence and Causality"

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#351

FromAnthony Williams <anthony.ajw@gmail.com>
Date2011-06-22 09:01 -0700
Message-ID<fc7e1703-3c9f-4b25-a56a-bf7a45ce37f7@u26g2000vby.googlegroups.com>
In reply to#344
Alexander Terekhov <terekhov@web.de> writes:

> Anthony Williams wrote:
>
> [... remote write atomicity ...]
>
>> However, in particular cases then you can order particular subsets. If
>> you have an example of code that you would like to work then I can see
>> if I can think of a way to make it work without using seq_cst everywhere.
>
> See examples in
>
> http://portal.acm.org/citation.cfm?id=1375591
> ("4.2 Unintended Consequences of Relaxing Write-Atomicity")
>
> "4.2.1 Write-to-Read Causality (WRC) Must be Upheld"

Figure 5:

std::atomic<int> X(0),Y(0);

T1
X.store(1,memory_order_relaxed);

T2
r1=X.load(memory_order_relaxed);
atomic_thread_fence(memory_order_release);
Y.store(memory_order_relaxed);

T3
r2=Y.load(memory_order_relaxed)
atomic_thread_fence(memory_order_acquire);
r3=X.load(memory_order_relaxed);

The required ordering comes from 29.8p2 and 1.10p16, since T2 stores
to
Y and T3 loads from Y: if r1==1 and r2==1 then r3==1.

> "4.2.2 Read-to-Write Causality (RWC)"

Figure 6:

std::atomic<int> X(0),Y(0);

T1
X.store(1,T1MO);

T2
r1=X.load(T2MO1);
atomic_thread_fence(T2MO2);
r2=Y.load(T2MO3);

T3
Y.store(1,T3MO1);
atomic_thread_fence(T3MO2);
r3=X.load(T3MO3);

In this case, there are no orderings such that acquire and release can
have any impact. Therefore the choice of ordering for each operation
is
either memory_order_seq_cst or memory_order_relaxed.

I presume we are trying to find a set of ordering constraints such
that
r1==1, r2==0, r3==0 is not possible.

The T1MO is memory_order_relaxed then both T2MO1 and T3MO3 must be
memory_order_seq_cst, and either of T2MO2 and T2MO3 must be
memory_order_seq_cst, and either of T3MO1 and T3MO2 must be
memory_order_seq_cst.

With any of these combinations, if r2==0 then the read of r1 must
occur
before the read of r3 in S, and r1==1, r3==0 is thus impossible by
29.3p3 (otherwise it is not consistent with the modification order of
X).

If T1MO is memory_order_seq_cst, then it is enough to make T2MO1,
T2MO2
and T3MO2 memory_order_seq_cst; the rest can be memory_order_relaxed.

If r1==1 then the load of r1 is after the store to X in S. If r2==0
then
the fence in T2 must be before the fence from T3 in S (by 29.3p5, if
the
fence in T3 is prior to the fence in T2 then r2==1). If T2 precedes T3
in S, and the store to X precedes the load of r1 in S then the store
to
X precedes T3 in S. By 29.3p5 we must have r3==1.

> "4.2.3 Subtle Interplay Between Coherence and Causality"

std::atomic<int> X(0),Y(0);

T1
X.store(1,T1MO);

T2
r1=X.load(T2MO1);
atomic_thread_fence(T2MO2);
r2=Y.load(T2MO3);

T3
Y.store(1,T3MO1);
atomic_thread_fence(T3MO2);
X.store(2,T3MO3);

T4
r3=X.load(T4MO1);
atomic_thread_fence(T4MO2);
r4=X.load(T4MO3);

In this example, the "violating result" is given as r1==1, r2==0,
r3==2,
r4==1.

r3==2, r4==1 requires that the store X=2 is prior to the store X=1 in
the modification order of X. There are no stores on thread 4, and no
ordering constraints can change this requirement, so T4MO1, T4MO2 and
T4MO3 can all be memory_order_relaxed.

The requirement that r1==1 requires that the load of r1 is seeing the
result of the store X=1, which is after the store X=2 from T3 in the
MO
of X. If T3MO3 and T2MO1, T3MO1 and T2MO3 are memory_order_seq_cst
then
everything works, even if everything else is memory_order_relaxed,
since
the load of r1 must be later in SC than the store X=2, in order to see
the later stored value, which means the store of Y=1 occurs before the
load of r2, and r2 must be 1.

Likewise, if T3MO3 and T2MO1, T3MO2 and T2MO2 are
memory_order_seq_cst,
then the same rules apply to mean the fence in T3 is before the fence
in
T2 in S, and by 29.3p5 r2==1.

It is possible that there are some alternatives with fewer
memory_order_seq_cst operations, but I don't see them right now.

Anthony
--
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No.
5478976

[toc] | [prev] | [next] | [standalone]

#336

FromAnthony Williams <anthony.ajw@gmail.com>
Date2011-06-20 15:41 +0100
Message-ID<87sjr4r2ej.fsf@justsoftwaresolutions.co.uk>
In reply to#324
Alexander Terekhov <terekhov@web.de> writes:

> Anthony Williams wrote:
>> 
>> Masakuni Oishi <yamasa@bsdhouse.org> writes:
>> 
>> > If so, for the code 1 in my first post, is the outcome
>> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>> 
>> I believe so.
>
> Perhaps this is relevant:
>
> http://download.intel.com/design/itanium/downloads/25142901.pdf
>
> See 3.3.7.1 Total ordering of WB Releases. 

The example is this:

> /*** code 1 ***/
> // Initially
> atomic<int> x(0), y(0);
> 
> // Thread 1:
> y.store(1, memory_order_release);
> atomic_thread_fence(memory_order_seq_cst);
> r1 = x.load(memory_order_acquire);
> 
> // Thread 2:
> x.store(1, memory_order_release);
> 
> // Thread 3:
> r2 = x.load(memory_order_acquire);
> atomic_thread_fence(memory_order_seq_cst);
> r3 = y.load(memory_order_acquire);
> /***************/
> 
> In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible? 

Under the C++0x memory model, the acquire and release operations here
serve no purpose --- there are no stores prior to the releases, so there
is no imposed ordering, and they might as well all be
memory_order_relaxed.

The above code is thus equivalent to the code below, as far as the C++0x
memory model goes, and the compiler would be conforming if it compiled
it as such:

/***************/
// Initially
atomic<int> x(0), y(0);

// Thread 1:
y.store(1, memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
r1 = x.load(memory_order_relaxed);

// Thread 2:
x.store(1, memory_order_relaxed);

// Thread 3:
r2 = x.load(memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
r3 = y.load(memory_order_relaxed);
/***************/

I am not an expert on IA-64, but I would expect a relaxed write on IA-64
to be plain ST --- an unordered write --- and a relaxed load to be a
plain LD --- an unordered read.

Given that, the total ordering of WB releases is not relevant here, and
I suspect that r1 == 0 && r2 == 1 && r3 == 0 is possible.

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

[toc] | [prev] | [next] | [standalone]

#340

FromMasakuni Oishi <yamasa@bsdhouse.org>
Date2011-06-20 23:24 -0700
Message-ID<cb94d252-d88e-424f-a078-92125c487f53@d1g2000prg.googlegroups.com>
In reply to#336
Anthony Williams <anthony....@gmail.com> wrote:
> Alexander Terekhov <terek...@web.de> writes:
> > Anthony Williams wrote:
>
> >> Masakuni Oishi <yam...@bsdhouse.org> writes:
>
> >> > If so, for the code 1 in my first post, is the outcome
> >> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>
> >> I believe so.
>
> > Perhaps this is relevant:
>
> >http://download.intel.com/design/itanium/downloads/25142901.pdf
>
> > See 3.3.7.1 Total ordering of WB Releases.
>
> The example is this:
>
> > /*** code 1 ***/
> > // Initially
> > atomic<int> x(0), y(0);
>
> > // Thread 1:
> > y.store(1, memory_order_release);
> > atomic_thread_fence(memory_order_seq_cst);
> > r1 = x.load(memory_order_acquire);
>
> > // Thread 2:
> > x.store(1, memory_order_release);
>
> > // Thread 3:
> > r2 = x.load(memory_order_acquire);
> > atomic_thread_fence(memory_order_seq_cst);
> > r3 = y.load(memory_order_acquire);
> > /***************/
>
> > In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible?
>
> Under the C++0x memory model, the acquire and release operations here
> serve no purpose --- there are no stores prior to the releases, so there
> is no imposed ordering, and they might as well all be
> memory_order_relaxed.
>
> The above code is thus equivalent to the code below, as far as the C++0x
> memory model goes, and the compiler would be conforming if it compiled
> it as such:
>
> /***************/
> // Initially
> atomic<int> x(0), y(0);
>
> // Thread 1:
> y.store(1, memory_order_relaxed);
> atomic_thread_fence(memory_order_seq_cst);
> r1 = x.load(memory_order_relaxed);
>
> // Thread 2:
> x.store(1, memory_order_relaxed);
>
> // Thread 3:
> r2 = x.load(memory_order_relaxed);
> atomic_thread_fence(memory_order_seq_cst);
> r3 = y.load(memory_order_relaxed);
> /***************/
>
> I am not an expert on IA-64, but I would expect a relaxed write on IA-64
> to be plain ST --- an unordered write --- and a relaxed load to be a
> plain LD --- an unordered read.
>
> Given that, the total ordering of WB releases is not relevant here, and
> I suspect that r1 == 0 && r2 == 1 && r3 == 0 is possible.

Hmm... Interesting.

I'm not an expert on IA-64, too, but I think
the code would be compiled as such:

// Thread 1
US1:   st   [y] = 1
MF1:   mf
UL1:   ld   r1 = [x]

// Thread 2
US2:   st   [x] = 1

// Thread 3
UL2:   ld   r2 = [x]
MF2:  mf
UL3:   ld   r3 = [y]

If the memory model of IA-64 allows ordering such as:
  RV_3(US2) -> F(MF2) -> F(MF1) -> RV_1(US2)
then the outcome r1 == 0 && r2 == 1 && r3 == 0 is possible,
I think.

The Intel's specification seems not prohibiting such ordering,
but I'm not sure that it may occur actually.

-- masakuni

[toc] | [prev] | [next] | [standalone]

#352

FromMasakuni Oishi <yamasa@bsdhouse.org>
Date2011-06-22 10:46 -0700
Message-ID<94b2404b-ea10-4ce2-9ecf-3c150751b4fa@34g2000pru.googlegroups.com>
In reply to#340
Masakuni Oishi <yam...@bsdhouse.org> wrote:
> Anthony Williams <anthony....@gmail.com> wrote:
> > Alexander Terekhov <terek...@web.de> writes:
> > > Anthony Williams wrote:
>
> > >> Masakuni Oishi <yam...@bsdhouse.org> writes:
>
> > >> > If so, for the code 1 in my first post, is the outcome
> > >> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>
> > >> I believe so.
>
> > > Perhaps this is relevant:
>
> > >http://download.intel.com/design/itanium/downloads/25142901.pdf
>
> > > See 3.3.7.1 Total ordering of WB Releases.
>
> > The example is this:
>
> > > /*** code 1 ***/
> > > // Initially
> > > atomic<int> x(0), y(0);
>
> > > // Thread 1:
> > > y.store(1, memory_order_release);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r1 = x.load(memory_order_acquire);
>
> > > // Thread 2:
> > > x.store(1, memory_order_release);
>
> > > // Thread 3:
> > > r2 = x.load(memory_order_acquire);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r3 = y.load(memory_order_acquire);
> > > /***************/
>
> > > In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible?
>
> > Under the C++0x memory model, the acquire and release operations here
> > serve no purpose --- there are no stores prior to the releases, so there
> > is no imposed ordering, and they might as well all be
> > memory_order_relaxed.
>
> > The above code is thus equivalent to the code below, as far as the C++0x
> > memory model goes, and the compiler would be conforming if it compiled
> > it as such:
>
> > /***************/
> > // Initially
> > atomic<int> x(0), y(0);
>
> > // Thread 1:
> > y.store(1, memory_order_relaxed);
> > atomic_thread_fence(memory_order_seq_cst);
> > r1 = x.load(memory_order_relaxed);
>
> > // Thread 2:
> > x.store(1, memory_order_relaxed);
>
> > // Thread 3:
> > r2 = x.load(memory_order_relaxed);
> > atomic_thread_fence(memory_order_seq_cst);
> > r3 = y.load(memory_order_relaxed);
> > /***************/
>
> > I am not an expert on IA-64, but I would expect a relaxed write on IA-64
> > to be plain ST --- an unordered write --- and a relaxed load to be a
> > plain LD --- an unordered read.
>
> > Given that, the total ordering of WB releases is not relevant here, and
> > I suspect that r1 == 0 && r2 == 1 && r3 == 0 is possible.
>
> Hmm... Interesting.
>
> I'm not an expert on IA-64, too, but I think
> the code would be compiled as such:
>
> // Thread 1
> US1:   st   [y] = 1
> MF1:   mf
> UL1:   ld   r1 = [x]
>
> // Thread 2
> US2:   st   [x] = 1
>
> // Thread 3
> UL2:   ld   r2 = [x]
> MF2:  mf
> UL3:   ld   r3 = [y]
>
> If the memory model of IA-64 allows ordering such as:
>   RV_3(US2) -> F(MF2) -> F(MF1) -> RV_1(US2)
> then the outcome r1 == 0 && r2 == 1 && r3 == 0 is possible,
> I think.
>
> The Intel's specification seems not prohibiting such ordering,
> but I'm not sure that it may occur actually.

Here is another example.

/***************/
// Initially
atomic<int> x(0), y(0);

// Thread 1:
r3 = y.load(memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
r1 = x.load(memory_order_relaxed);

// Thread 2:
x.store(1, memory_order_relaxed);

// Thread 3:
r2 = x.load(memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
y.store(1, memory_order_relaxed);
/***************/

In this code, the outcome r1 == 0 && r2 == 1 && r3 == 1
is NOT allowed under the C++0x memory model.
(29.8p2 and 1.10p16)

But, if we compile the code on IA-64,

// Thread 1
UL3:   ld   r3 = [y]
MF1:   mf
UL1:   ld   r1 = [x]

// Thread 2
US2:   st   [x] = 1

// Thread 3
UL2:   ld   r2 = [x]
MF2:   mf
US1:   st   [y] = 1

it seems that the outcome r1 == 0 && r2 == 1 && r3 == 1
is possible.
Isn't it?

-- masakuni

[toc] | [prev] | [next] | [standalone]

#353

FromMasakuni Oishi <yamasa@bsdhouse.org>
Date2011-06-22 11:19 -0700
Message-ID<4f622dc3-ad80-4bde-ba01-28e63ffa27d7@d19g2000prh.googlegroups.com>
In reply to#340
Masakuni Oishi <yam...@bsdhouse.org> wrote:
> Anthony Williams <anthony....@gmail.com> wrote:
> > Alexander Terekhov <terek...@web.de> writes:
> > > Anthony Williams wrote:
>
> > >> Masakuni Oishi <yam...@bsdhouse.org> writes:
>
> > >> > If so, for the code 1 in my first post, is the outcome
> > >> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>
> > >> I believe so.
>
> > > Perhaps this is relevant:
>
> > >http://download.intel.com/design/itanium/downloads/25142901.pdf
>
> > > See 3.3.7.1 Total ordering of WB Releases.
>
> > The example is this:
>
> > > /*** code 1 ***/
> > > // Initially
> > > atomic<int> x(0), y(0);
>
> > > // Thread 1:
> > > y.store(1, memory_order_release);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r1 = x.load(memory_order_acquire);
>
> > > // Thread 2:
> > > x.store(1, memory_order_release);
>
> > > // Thread 3:
> > > r2 = x.load(memory_order_acquire);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r3 = y.load(memory_order_acquire);
> > > /***************/
>
> > > In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible?
>
> > Under the C++0x memory model, the acquire and release operations here
> > serve no purpose --- there are no stores prior to the releases, so there
> > is no imposed ordering, and they might as well all be
> > memory_order_relaxed.
>
> > The above code is thus equivalent to the code below, as far as the C++0x
> > memory model goes, and the compiler would be conforming if it compiled
> > it as such:
>
> > /***************/
> > // Initially
> > atomic<int> x(0), y(0);
>
> > // Thread 1:
> > y.store(1, memory_order_relaxed);
> > atomic_thread_fence(memory_order_seq_cst);
> > r1 = x.load(memory_order_relaxed);
>
> > // Thread 2:
> > x.store(1, memory_order_relaxed);
>
> > // Thread 3:
> > r2 = x.load(memory_order_relaxed);
> > atomic_thread_fence(memory_order_seq_cst);
> > r3 = y.load(memory_order_relaxed);
> > /***************/
>
> > I am not an expert on IA-64, but I would expect a relaxed write on IA-64
> > to be plain ST --- an unordered write --- and a relaxed load to be a
> > plain LD --- an unordered read.
>
> > Given that, the total ordering of WB releases is not relevant here, and
> > I suspect that r1 == 0 && r2 == 1 && r3 == 0 is possible.
>
> Hmm... Interesting.
>
> I'm not an expert on IA-64, too, but I think
> the code would be compiled as such:
>
> // Thread 1
> US1:   st   [y] = 1
> MF1:   mf
> UL1:   ld   r1 = [x]
>
> // Thread 2
> US2:   st   [x] = 1
>
> // Thread 3
> UL2:   ld   r2 = [x]
> MF2:   mf
> UL3:   ld   r3 = [y]
>
> If the memory model of IA-64 allows ordering such as:
>   RV_3(US2) -> F(MF2) -> F(MF1) -> RV_1(US2)
> then the outcome r1 == 0 && r2 == 1 && r3 == 0 is possible,
> I think.
>
> The Intel's specification seems not prohibiting such ordering,
> but I'm not sure that it may occur actually.

Here is another example.

/***************/
// Initially
atomic<int> x(0), y(0);

// Thread 1:
r3 = y.load(memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
r1 = x.load(memory_order_relaxed);

// Thread 2:
x.store(1, memory_order_relaxed);

// Thread 3:
r2 = x.load(memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
y.store(1, memory_order_relaxed);
/***************/

In this code, the outcome r1 == 0 && r2 == 1 && r3 == 1
is NOT allowed under the C++0x memory model.
(29.8p2 and 1.10p16)

But, if we compile the code on IA-64,

// Thread 1
UL3:   ld   r3 = [y]
MF1:   mf
UL1:   ld   r1 = [x]

// Thread 2
US2:   st   [x] = 1

// Thread 3
UL2:   ld   r2 = [x]
MF2:   mf
US1:   st   [y] = 1

it seems that the outcome r1 == 0 && r2 == 1 && r3 == 1
is possible.
Isn't it?

-- masakuni

[toc] | [prev] | [next] | [standalone]

#354

FromMasakuni Oishi <yamasa@bsdhouse.org>
Date2011-06-22 11:57 -0700
Message-ID<b6ee3ba2-0ae5-40da-af4c-8ed7b44fdced@z15g2000prn.googlegroups.com>
In reply to#353
Masakuni Oishi <yam...@bsdhouse.org> wrote:
> Masakuni Oishi <yam...@bsdhouse.org> wrote:
> > Anthony Williams <anthony....@gmail.com> wrote:
> > > Alexander Terekhov <terek...@web.de> writes:
> > > > Anthony Williams wrote:
>
> > > >> Masakuni Oishi <yam...@bsdhouse.org> writes:
>
> > > >> > If so, for the code 1 in my first post, is the outcome
> > > >> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>
> > > >> I believe so.
>
> > > > Perhaps this is relevant:
>
> > > >http://download.intel.com/design/itanium/downloads/25142901.pdf
>
> > > > See 3.3.7.1 Total ordering of WB Releases.
>
> > > The example is this:
>
> > > > /*** code 1 ***/
> > > > // Initially
> > > > atomic<int> x(0), y(0);
>
> > > > // Thread 1:
> > > > y.store(1, memory_order_release);
> > > > atomic_thread_fence(memory_order_seq_cst);
> > > > r1 = x.load(memory_order_acquire);
>
> > > > // Thread 2:
> > > > x.store(1, memory_order_release);
>
> > > > // Thread 3:
> > > > r2 = x.load(memory_order_acquire);
> > > > atomic_thread_fence(memory_order_seq_cst);
> > > > r3 = y.load(memory_order_acquire);
> > > > /***************/
>
> > > > In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible?
>
> > > Under the C++0x memory model, the acquire and release operations here
> > > serve no purpose --- there are no stores prior to the releases, so there
> > > is no imposed ordering, and they might as well all be
> > > memory_order_relaxed.
>
> > > The above code is thus equivalent to the code below, as far as the C++0x
> > > memory model goes, and the compiler would be conforming if it compiled
> > > it as such:
>
> > > /***************/
> > > // Initially
> > > atomic<int> x(0), y(0);
>
> > > // Thread 1:
> > > y.store(1, memory_order_relaxed);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r1 = x.load(memory_order_relaxed);
>
> > > // Thread 2:
> > > x.store(1, memory_order_relaxed);
>
> > > // Thread 3:
> > > r2 = x.load(memory_order_relaxed);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r3 = y.load(memory_order_relaxed);
> > > /***************/
>
> > > I am not an expert on IA-64, but I would expect a relaxed write on IA-64
> > > to be plain ST --- an unordered write --- and a relaxed load to be a
> > > plain LD --- an unordered read.
>
> > > Given that, the total ordering of WB releases is not relevant here, and
> > > I suspect that r1 == 0 && r2 == 1 && r3 == 0 is possible.
>
> > Hmm... Interesting.
>
> > I'm not an expert on IA-64, too, but I think
> > the code would be compiled as such:
>
> > // Thread 1
> > US1:   st   [y] = 1
> > MF1:   mf
> > UL1:   ld   r1 = [x]
>
> > // Thread 2
> > US2:   st   [x] = 1
>
> > // Thread 3
> > UL2:   ld   r2 = [x]
> > MF2:   mf
> > UL3:   ld   r3 = [y]
>
> > If the memory model of IA-64 allows ordering such as:
> >   RV_3(US2) -> F(MF2) -> F(MF1) -> RV_1(US2)
> > then the outcome r1 == 0 && r2 == 1 && r3 == 0 is possible,
> > I think.
>
> > The Intel's specification seems not prohibiting such ordering,
> > but I'm not sure that it may occur actually.
>
> Here is another example.
>
> /***************/
> // Initially
> atomic<int> x(0), y(0);
>
> // Thread 1:
> r3 = y.load(memory_order_relaxed);
> atomic_thread_fence(memory_order_seq_cst);
> r1 = x.load(memory_order_relaxed);
>
> // Thread 2:
> x.store(1, memory_order_relaxed);
>
> // Thread 3:
> r2 = x.load(memory_order_relaxed);
> atomic_thread_fence(memory_order_seq_cst);
> y.store(1, memory_order_relaxed);
> /***************/
>
> In this code, the outcome r1 == 0 && r2 == 1 && r3 == 1
> is NOT allowed under the C++0x memory model.
> (29.8p2 and 1.10p16)
>
> But, if we compile the code on IA-64,
>
> // Thread 1
> UL3:   ld   r3 = [y]
> MF1:   mf
> UL1:   ld   r1 = [x]
>
> // Thread 2
> US2:   st   [x] = 1
>
> // Thread 3
> UL2:   ld   r2 = [x]
> MF2:   mf
> US1:   st   [y] = 1
>
> it seems that the outcome r1 == 0 && r2 == 1 && r3 == 1
> is possible.
> Isn't it?

Furthermore,

/***************/
// Initially
atomic<int> x(0), y(0);

// Thread 1:
x.store(1, memory_order_relaxed);

// Thread 2:
r1 = x.load(memory_order_relaxed);
y.store(1, memory_order_release);

// Thread 3:
r2 = y.load(memory_order_acquire);
r3 = x.load(memory_order_relaxed);
/***************/

this code does not allow the outcome
r1 == 1 && r2 == 1 && r3 == 0
under the C++0x memory model.

But, the compiled code on IA-64:

// Thread 1
US:    st   [x] = 1

// Thread 2
UL1:   ld   r1 = [x]
SR:    st.rel  [y] = 1

// Thread 3
LA:    ld.acq  r2 = [y]
UL2:   ld   r3 = [x]

seems that the outcome
r1 == 1 && r2 == 1 && r3 == 0 is possible.


Therefore, we may not compile a relaxed store
to a plain ST.

-- masakuni

[toc] | [prev] | [next] | [standalone]

#366

FromAlexander Terekhov <terekhov@web.de>
Date2011-06-27 14:05 +0200
Message-ID<4E0871F3.10EC425A@web.de>
In reply to#354
Masakuni Oishi wrote:
[...]
> /***************/
> // Initially
> atomic<int> x(0), y(0);
> 
> // Thread 1:
> x.store(1, memory_order_relaxed);
> 
> // Thread 2:
> r1 = x.load(memory_order_relaxed);
> y.store(1, memory_order_release);
> 
> // Thread 3:
> r2 = y.load(memory_order_acquire);
> r3 = x.load(memory_order_relaxed);
> /***************/
> 
> this code does not allow the outcome
> r1 == 1 && r2 == 1 && r3 == 0
> under the C++0x memory model.

Well,

http://www.rdrop.com/users/paulmck/scalability/paper/N2745r.2011.03.04a.html

"Example 1: Load/Load ...

Thread 0: 	

  r1 = x.load(memory_order_relaxed);
  y.store(1, memory_order_release);

Thread 1: 	
	 
  r2 = y.load(memory_order_acquire);
  r3 = x.load(memory_order_relaxed);
	 
Thread 2 (required for assertion): 	

  x.store(1, memory_order_relaxed);"
	
says that "the C++ memory model does not actually require the loads to
be ordered in this case, since thread 0's relaxed store is not
guaranteed to be seen in any particular order by thread 0's and 1's
relaxed loads. " ("thread 0's relaxed store" is meant to say "thread 2's
relaxed store" of course)

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#370

FromJoshua Maurice <joshuamaurice@gmail.com>
Date2011-06-29 16:14 -0700
Message-ID<16d29658-0b1f-441b-8686-9ee13aba51d7@r21g2000pri.googlegroups.com>
In reply to#366
On Jun 27, 5:05 am, Alexander Terekhov <terek...@web.de> wrote:
> Masakuni Oishi wrote:
>
> [...]
>
>
>
>
>
>
>
>
>
> > /***************/
> > // Initially
> > atomic<int> x(0), y(0);
>
> > // Thread 1:
> > x.store(1, memory_order_relaxed);
>
> > // Thread 2:
> > r1 = x.load(memory_order_relaxed);
> > y.store(1, memory_order_release);
>
> > // Thread 3:
> > r2 = y.load(memory_order_acquire);
> > r3 = x.load(memory_order_relaxed);
> > /***************/
>
> > this code does not allow the outcome
> > r1 == 1 && r2 == 1 && r3 == 0
> > under the C++0x memory model.
>
> Well,
>
> http://www.rdrop.com/users/paulmck/scalability/paper/N2745r.2011.03.0...
>
> "Example 1: Load/Load ...
>
> Thread 0:      
>
>   r1 = x.load(memory_order_relaxed);
>   y.store(1, memory_order_release);
>
> Thread 1:      
>
>   r2 = y.load(memory_order_acquire);
>   r3 = x.load(memory_order_relaxed);
>
> Thread 2 (required for assertion):      
>
>   x.store(1, memory_order_relaxed);"
>
> says that "the C++ memory model does not actually require the loads to
> be ordered in this case, since thread 0's relaxed store is not
> guaranteed to be seen in any particular order by thread 0's and 1's
> relaxed loads. " ("thread 0's relaxed store" is meant to say "thread 2's
> relaxed store" of course)

Google groups is acting up, so sorry if someone's already gotten to
this.

I think you're saying that "r1 == 1 && r2 == 1 && r3 == 0" is the
result of an allowed execution according to the C++0x rules. I believe
this is incorrect. I claim that there is no such allowed execution. My
program says as much (uploaded else-thread), but I don't trust it at
the moment, so I did the reasoning myself. My reasoning is as
follows:


/***************/
// Initially
atomic<int> x(0);
atomic<int> y(0);
start thread 1;
start thread 2;
start thread 3;

// Thread 1:
x.store(1, memory_order_relaxed);

// Thread 2:
r1 = x.load(memory_order_relaxed);
y.store(1, memory_order_release);

// Thread 3:
r2 = y.load(memory_order_acquire);
r3 = x.load(memory_order_relaxed);
/***************/

//end conditions: r1 == 1 && r2 == 1 && r3 == 0

Let's see if there's an allowed execution that fits these constraints.
We'll do so by assuming the constraints. If we derive a contradiction,
then there is no allowed execution under these constraints. If we
apply all of the possible rules and do not get a contradiction, then
we've found an allowed execution.

* The constraints we're assuming are:
    "r1 = x.load(memory_order_relaxed);"  sees  value 1
    "r2 = y.load(memory_order_acquire);"  sees  value 1
    "r3 = x.load(memory_order_relaxed);"  sees  value 0
* The only way to satisfy these constraints is:
    "r1 = x.load(memory_order_relaxed);"
            sees  "x.store(1, memory_order_relaxed);"
    "r2 = y.load(memory_order_acquire);"
            sees  "y.store(1, memory_order_release);"
    "r3 = x.load(memory_order_relaxed);"
            sees  "atomic<int> x(0);"

* Remember:
    "r2 = y.load(memory_order_acquire);"
            sees  "y.store(1, memory_order_release);"
* 29.3 p2 gives:
    "y.store(1, memory_order_release);"
            syncs-with  "r2 = y.load(memory_order_acquire);"
* Repeated applications of 1.10 p11 give:
    "r1 = x.load(memory_order_relaxed);"
            inter-thread-hb  "r3 = x.load(memory_order_relaxed);"
* 1.10 p12 gives:
    "r1 = x.load(memory_order_relaxed);"
            happens-before  "r3 = x.load(memory_order_relaxed);"
* 1.10 p16 gives:
    For T, U so that
        "r1 = x.load(memory_order_relaxed);" sees T, and
        "r3 = x.load(memory_order_relaxed);" sees U,
        then T is U, or T precedes U in the modification order of X
        aka: T <=mod-order-X U
* Thus
    "x.store(1, memory_order_relaxed);"
            <=mod-order-X  "atomic<int> x(0);"

* 30.3.1.2 p5 gives:
    "start thread 1;"
            syncs-with  "x.store(1, memory_order_relaxed);"
* Repeated applications of 1.10 p11 give:
    "atomic<int> x(0);"
            inter-thread-hb  "x.store(1, memory_order_relaxed);"
* 1.10 p12 gives:
    "atomic<int> x(0);"
            happens-before  "x.store(1, memory_order_relaxed);"
* 1.10 p15 gives:
    "atomic<int> x(0);"
            precedes "x.store(1, memory_order_relaxed);"
            in the modification order of X
    aka: "atomic<int> x(0);"
            <mod-order-X  "x.store(1, memory_order_relaxed);"

* So, we've derived the following:
    "x.store(1, memory_order_relaxed);"
            <=mod-order-X  "atomic<int> x(0);"
    "atomic<int> x(0);"
            <mod-order-X  "x.store(1, memory_order_relaxed);"
* Thus contradiction.
* Thus there is no allowed execution which satisfies the assumed
constraints.
* Aka: There is no allowed execution (in C++0x) which can produce:
    r1 == 1 && r2 == 1 && r3 == 0.

[toc] | [prev] | [next] | [standalone]

#361

FromAnthony Williams <anthony.ajw@gmail.com>
Date2011-06-24 01:42 -0700
Message-ID<38d79317-4242-4f45-8840-ca6bd2cbba85@d22g2000yqn.googlegroups.com>
In reply to#353
On Jun 22, 7:19 pm, Masakuni Oishi <yam...@bsdhouse.org> wrote:
> Masakuni Oishi <yam...@bsdhouse.org> wrote:
> > Anthony Williams <anthony....@gmail.com> wrote:
> > > Alexander Terekhov <terek...@web.de> writes:
> > > > Anthony Williams wrote:
>
> > > >> Masakuni Oishi <yam...@bsdhouse.org> writes:
>
> > > >> > If so, for the code 1 in my first post, is the outcome
> > > >> > r1 == 0 && r2 == 1 && r3 == 0 possible on IA-64?
>
> > > >> I believe so.
>
> > > > Perhaps this is relevant:
>
> > > >http://download.intel.com/design/itanium/downloads/25142901.pdf
>
> > > > See 3.3.7.1 Total ordering of WB Releases.
>
> > > The example is this:
>
> > > > /*** code 1 ***/
> > > > // Initially
> > > > atomic<int> x(0), y(0);
>
> > > > // Thread 1:
> > > > y.store(1, memory_order_release);
> > > > atomic_thread_fence(memory_order_seq_cst);
> > > > r1 = x.load(memory_order_acquire);
>
> > > > // Thread 2:
> > > > x.store(1, memory_order_release);
>
> > > > // Thread 3:
> > > > r2 = x.load(memory_order_acquire);
> > > > atomic_thread_fence(memory_order_seq_cst);
> > > > r3 = y.load(memory_order_acquire);
> > > > /***************/
>
> > > > In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible?
>
> > > Under the C++0x memory model, the acquire and release operations here
> > > serve no purpose --- there are no stores prior to the releases, so there
> > > is no imposed ordering, and they might as well all be
> > > memory_order_relaxed.
>
> > > The above code is thus equivalent to the code below, as far as the C++0x
> > > memory model goes, and the compiler would be conforming if it compiled
> > > it as such:
>
> > > /***************/
> > > // Initially
> > > atomic<int> x(0), y(0);
>
> > > // Thread 1:
> > > y.store(1, memory_order_relaxed);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r1 = x.load(memory_order_relaxed);
>
> > > // Thread 2:
> > > x.store(1, memory_order_relaxed);
>
> > > // Thread 3:
> > > r2 = x.load(memory_order_relaxed);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r3 = y.load(memory_order_relaxed);
> > > /***************/
>
> > > I am not an expert on IA-64, but I would expect a relaxed write on IA-64
> > > to be plain ST --- an unordered write --- and a relaxed load to be a
> > > plain LD --- an unordered read.
>
> > > Given that, the total ordering of WB releases is not relevant here, and
> > > I suspect that r1 == 0 && r2 == 1 && r3 == 0 is possible.
>
> > Hmm... Interesting.
>
> > I'm not an expert on IA-64, too, but I think
> > the code would be compiled as such:
>
> > // Thread 1
> > US1:   st   [y] = 1
> > MF1:   mf
> > UL1:   ld   r1 = [x]
>
> > // Thread 2
> > US2:   st   [x] = 1
>
> > // Thread 3
> > UL2:   ld   r2 = [x]
> > MF2:   mf
> > UL3:   ld   r3 = [y]
>
> > If the memory model of IA-64 allows ordering such as:
> >   RV_3(US2) -> F(MF2) -> F(MF1) -> RV_1(US2)
> > then the outcome r1 == 0 && r2 == 1 && r3 == 0 is possible,
> > I think.
>
> > The Intel's specification seems not prohibiting such ordering,
> > but I'm not sure that it may occur actually.
>
> Here is another example.
>
> /***************/
> // Initially
> atomic<int> x(0), y(0);
>
> // Thread 1:
> r3 = y.load(memory_order_relaxed);
> atomic_thread_fence(memory_order_seq_cst);
> r1 = x.load(memory_order_relaxed);
>
> // Thread 2:
> x.store(1, memory_order_relaxed);
>
> // Thread 3:
> r2 = x.load(memory_order_relaxed);
> atomic_thread_fence(memory_order_seq_cst);
> y.store(1, memory_order_relaxed);
> /***************/
>
> In this code, the outcome r1 == 0 && r2 == 1 && r3 == 1
> is NOT allowed under the C++0x memory model.
> (29.8p2 and 1.10p16)

OK

> But, if we compile the code on IA-64,
>
> // Thread 1
> UL3:   ld   r3 = [y]
> MF1:   mf
> UL1:   ld   r1 = [x]
>
> // Thread 2
> US2:   st   [x] = 1
>
> // Thread 3
> UL2:   ld   r2 = [x]
> MF2:   mf
> US1:   st   [y] = 1
>
> it seems that the outcome r1 == 0 && r2 == 1 && r3 == 1
> is possible.
> Isn't it?

I'm not sure. As far as I can make out from the Itanium memory
ordering docs, if r2==1 and r3==1 then:

RV3(US2)->R(UL2)->F(MF2)->RV1(US1)->R(UL3)->F(MF1)->R(UL1)

That on its own doesn't tell use what r1 is, since RV1(US2) is not in
that chain.

Unless there is something that I've missed, there is no constraint
that requires RV1(US2)->R(UL1), so you are right: r1==0 is permitted.
Is there anyone who is an expert on IA-64 who can confirm this, or
point out what is missing?

Anthony
--
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No.
5478976

[toc] | [prev] | [next] | [standalone]

#365

FromAlexander Terekhov <terekhov@web.de>
Date2011-06-27 13:24 +0200
Message-ID<4E086880.8F382B3D@web.de>
In reply to#361
Anthony Williams wrote:
[...]
> > /***************/
> > // Initially
> > atomic<int> x(0), y(0);
> >
> > // Thread 1:
> > r3 = y.load(memory_order_relaxed);
> > atomic_thread_fence(memory_order_seq_cst);
> > r1 = x.load(memory_order_relaxed);
> >
> > // Thread 2:
> > x.store(1, memory_order_relaxed);
> >
> > // Thread 3:
> > r2 = x.load(memory_order_relaxed);
> > atomic_thread_fence(memory_order_seq_cst);
> > y.store(1, memory_order_relaxed);
> > /***************/
> >
> > In this code, the outcome r1 == 0 && r2 == 1 && r3 == 1
> > is NOT allowed under the C++0x memory model.
> > (29.8p2 and 1.10p16)
> 
> OK
> 
> > But, if we compile the code on IA-64,
> >
> > // Thread 1
> > UL3:   ld   r3 = [y]
> > MF1:   mf
> > UL1:   ld   r1 = [x]
> >
> > // Thread 2
> > US2:   st   [x] = 1
> >
> > // Thread 3
> > UL2:   ld   r2 = [x]
> > MF2:   mf
> > US1:   st   [y] = 1
> >
> > it seems that the outcome r1 == 0 && r2 == 1 && r3 == 1
> > is possible.
> > Isn't it?
> 
> I'm not sure. As far as I can make out from the Itanium memory
> ordering docs, if r2==1 and r3==1 then:
> 
> RV3(US2)->R(UL2)->F(MF2)->RV1(US1)->R(UL3)->F(MF1)->R(UL1)
> 
> That on its own doesn't tell use what r1 is, since RV1(US2) is not in
> that chain.
> 
> Unless there is something that I've missed, there is no constraint
> that requires RV1(US2)->R(UL1), so you are right: r1==0 is permitted.

That's because visibility of 2nd thread's store with respect to 1st
thread can be delayed until after 3rd thread's store is made visible
with respect 1st thread and 1st thread can load 'stale' value of x into
r1 (due to lack of remote write atomicity). Itanium's st.rel aside, on
PowerPC, the most heavy fence (hwsync) would prevent that outcome
(hwsync in 1st thread precludes it from observing 'stale' value of x)
but Itanium's mf is not that strong.

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#373

FromAnthony Williams <anthony.ajw@gmail.com>
Date2011-07-01 02:25 -0700
Message-ID<026f1d31-6b71-4aa0-b458-a4b21a10420e@g12g2000yqd.googlegroups.com>
In reply to#365
On Jun 27, 12:24 pm, Alexander Terekhov <terek...@web.de> wrote:
> Anthony Williams wrote:
> > > /***************/
> > > // Initially
> > > atomic<int> x(0), y(0);
>
> > > // Thread 1:
> > > r3 = y.load(memory_order_relaxed);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > r1 = x.load(memory_order_relaxed);
>
> > > // Thread 2:
> > > x.store(1, memory_order_relaxed);
>
> > > // Thread 3:
> > > r2 = x.load(memory_order_relaxed);
> > > atomic_thread_fence(memory_order_seq_cst);
> > > y.store(1, memory_order_relaxed);
> > > /***************/
>
> > > In this code, the outcome r1 == 0 && r2 == 1 && r3 == 1
> > > is NOT allowed under the C++0x memory model.
> > > (29.8p2 and 1.10p16)
>
> > OK
>
> > > But, if we compile the code on IA-64,
>
> > > // Thread 1
> > > UL3:   ld   r3 = [y]
> > > MF1:   mf
> > > UL1:   ld   r1 = [x]
>
> > > // Thread 2
> > > US2:   st   [x] = 1
>
> > > // Thread 3
> > > UL2:   ld   r2 = [x]
> > > MF2:   mf
> > > US1:   st   [y] = 1
>
> > > it seems that the outcome r1 == 0 && r2 == 1 && r3 == 1
> > > is possible.
> > > Isn't it?
>
> > I'm not sure. As far as I can make out from the Itanium memory
> > ordering docs, if r2==1 and r3==1 then:
>
> > RV3(US2)->R(UL2)->F(MF2)->RV1(US1)->R(UL3)->F(MF1)->R(UL1)
>
> > That on its own doesn't tell use what r1 is, since RV1(US2) is not in
> > that chain.
>
> > Unless there is something that I've missed, there is no constraint
> > that requires RV1(US2)->R(UL1), so you are right: r1==0 is permitted.
>
> That's because visibility of 2nd thread's store with respect to 1st
> thread can be delayed until after 3rd thread's store is made visible
> with respect 1st thread and 1st thread can load 'stale' value of x into
> r1 (due to lack of remote write atomicity). Itanium's st.rel aside, on
> PowerPC, the most heavy fence (hwsync) would prevent that outcome
> (hwsync in 1st thread precludes it from observing 'stale' value of x)
> but Itanium's mf is not that strong.

Right, so it appears that on Itanium we cannot use plain LD and ST for
memory_order_relaxed operations --- at least one of them must be
stronger. For now, I'm not sure whether we can get away with making
only one stronger, or whether we need to go for making both loads and
stores stronger.

Anthony

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.programming.threads

csiph-web