Groups > comp.programming.threads > #2181

Re: About lockfree and waitfree... (2nd try)

From	Ivan Godard <ivan@ootbcomp.com>
Newsgroups	comp.programming.threads, comp.programming, comp.arch
Subject	Re: About lockfree and waitfree... (2nd try)
Date	2014-04-17 18:52 -0700
Organization	A noiseless patient Spider
Message-ID	<liq0gj$oe2$1@dont-email.me> (permalink)
References	(2 earlier) <lifi9j$ka7$1@speranza.aioe.org> <lihioq$ubs$1@speranza.aioe.org> <lihjlm$q0$1@speranza.aioe.org> <lihr02$g62$2@dont-email.me> <6it0l91i77eocil0e12dgsff16t78469dr@4ax.com>

Cross-posted to 3 groups.

Show all headers | View raw

On 4/17/2014 6:15 PM, George Neuner wrote:
> On Mon, 14 Apr 2014 16:29:08 -0700, Ivan Godard <ivan@ootbcomp.com>
> wrote:
>
>> Are the membars necessary at all if the machine is strict
>> sequential concurrency?
>
> Ivan,
>
> I _believe_ strict sequential is sufficient for threading in a
> *conventional* single core because writes are internally visible to
> following instructions [even though they may be from a different
> logical thread] even if those writes have not yet propagated to the
> memory hierarchy.
>
> However, with multiple cores/processors, writes need to be globally
> visible to any cores participating in the wait algorithm.  Because
> writes are not visible to all cores until they appear in memory [at
> least in snooped cache], strict sequential within the cores is not
> sufficient.
>
>
> From my limited[*] understanding of the Mill, I think you may fall
> into the multiprocessor case even with a single core: if every
> thread has its own virtual belt and can't see writes from other
> threads until they hit the cache ...

It's hard to judge this because the Mill mechanism simply doesn't work 
like the conventional memory model.

Some of the differences:

1) The Mill has (the possibility of) backless memory, data that lives 
only in cache and never does have DRAM to write to behind it. Unwritten 
backless data reads as zero in hardware. Consequently DRAM cannot be 
used as the synchronization point, because there might not be any.

2) The Mill has "valid bits" on each byte in cache. Consequently a write 
can be inserted directly into top-level cache and does not have to have 
the rest of the line read in from memory (if there is a line in memory - 
see "backless").

3) The machine is strictly in-order (while multi-issue) and has exposed 
pipeline. Consequently the order of requests to cache is the same as the 
order of operations in the executed binary. There is no overtaking or 
buffering, and no ordering timestamps are needed.

4) Because stores are immediate to the top-level cache, a load that is 
later in the request sequence will always see an earlier store, and a 
later store will always overwrite an earlier store, again with no 
buffering or timestamps.

5) Just as a store does not need to read the rest of the line from 
cache, it also does not need to acquire the line from a different core 
under the coherence protocol. Consequently store-coherence invalidation 
is "fire-and-forget" and stores do not have to wait. As a side-effect of 
this, "false sharing" (where a single line contains data exclusively 
used by different threads who then must ping-pong their access to the 
line) is impossible on a Mill.

6) The hardware coherence protocol guarantees that invalidation requests 
from any core will be seen by any other core in the order the requests 
were issues. There is no overtaking or other reordering in the coherence 
network.

7) A load may be satisfied from data in any other core, but if it is so 
satisfied then the data returned by the coherence request is always what 
a load originating on that core would see. If several cores have copies 
(which may differ due to propagation delays of invalidate requests), 
then one is chosen arbitrarily. This reflects the arbitrary-interleave 
of sequential consistency. (BTW, if correctness depends on which version 
is selected then the program contains a data race and is invalid under 
sequential consistency). Whether locating a foreign copy is implemented 
by broadcast, directory, or other is an implementation decision and will 
vary.

We have convinced ourselves that all this is a correct implementation of 
sequential consistency. So far all the issues we have found have arisen 
with programs that in fact expect global strict ordering, which the Mill 
does not do (nor does any other hardware I know of).

Besides the material at millcomputing.com/docs, there has been quite a 
bit of discussion on our Forum at http://millcomputing.com/forum/the-mill/.

Thread

About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 19:54 -0700
  Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:38 -0700
    Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:47 -0700
      Re: About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 22:56 -0700
      Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 14:08 -0700
        Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 14:23 -0700
          Re: About lockfree and waitfree... Ivan Godard <ivan@ootbcomp.com> - 2014-04-14 16:27 -0700
          Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-14 16:29 -0700
            Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-15 10:04 -0700
              Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-15 10:34 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-17 16:35 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 17:04 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-18 09:54 +0100
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-18 02:31 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-18 11:56 +0100
                Re: About lockfree and waitfree... (2nd try) rpw3@rpw3.org (Rob Warnock) - 2014-04-18 11:26 +0000
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-18 13:30 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:25 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:31 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-21 14:53 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 14:21 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 14:36 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-22 15:30 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-05-01 00:48 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-05-25 13:16 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:34 -0700
                Re: About lockfree and waitfree... (2nd try) Robert Wessel <robertwessel2@yahoo.com> - 2014-04-21 16:42 -0500
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-21 15:02 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-22 09:05 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-22 09:27 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-22 09:45 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-22 18:08 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-23 12:08 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-23 20:32 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-23 13:21 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-23 21:51 +0100
                Re: About lockfree and waitfree... (2nd try) Chris Gray <cg@GraySage.COM> - 2014-04-24 10:53 -0600
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-24 18:02 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-25 13:39 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 22:08 -0700
            Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-17 21:15 -0400
              Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-17 21:25 -0400
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 19:17 -0700
                Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-18 00:46 -0400
              Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 18:52 -0700
    Re: About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 22:54 -0700

csiph-web