Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #2155 > unrolled thread
| Started by | aminer <aminer@toto.net> |
|---|---|
| First post | 2014-04-13 19:54 -0700 |
| Last post | 2014-04-13 22:54 -0700 |
| Articles | 6 on this page of 46 — 9 participants |
Back to article view | Back to comp.programming.threads
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
Page 3 of 3 — ← Prev page 1 2 [3]
| From | George Neuner <gneuner2@comcast.net> |
|---|---|
| Date | 2014-04-17 21:15 -0400 |
| Subject | Re: About lockfree and waitfree... (2nd try) |
| Message-ID | <6it0l91i77eocil0e12dgsff16t78469dr@4ax.com> |
| In reply to | #2172 |
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 ... George [*] I've watched the videos but they are short on specifics and I'm basically a software guy to begin with.
[toc] | [prev] | [next] | [standalone]
| From | George Neuner <gneuner2@comcast.net> |
|---|---|
| Date | 2014-04-17 21:25 -0400 |
| Subject | Re: About lockfree and waitfree... (2nd try) |
| Message-ID | <ogv0l9ls2rq6c7ig3nv4ivgfm6o2ue2p7o@4ax.com> |
| In reply to | #2179 |
On Thu, 17 Apr 2014 21:15:15 -0400, George Neuner <gneuner2@comcast.net> wrote: >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 ... Maybe mispoke: it may not be per-thread belt that is a problem, but rather whether writes to memory are (or not) globally visible to logical threads within the core before they hit cache. My (maybe wrong) impression from the videos was that they are not. George
[toc] | [prev] | [next] | [standalone]
| From | Ivan Godard <ivan@ootbcomp.com> |
|---|---|
| Date | 2014-04-17 19:17 -0700 |
| Subject | Re: About lockfree and waitfree... (2nd try) |
| Message-ID | <liq20h$ves$1@dont-email.me> |
| In reply to | #2180 |
On 4/17/2014 6:25 PM, George Neuner wrote: > On Thu, 17 Apr 2014 21:15:15 -0400, George Neuner > <gneuner2@comcast.net> wrote: > >> 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 ... > > Maybe mispoke: it may not be per-thread belt that is a problem, but > rather whether writes to memory are (or not) globally visible to > logical threads within the core before they hit cache. > > My (maybe wrong) impression from the videos was that they are not. > George > The belt is only a problem if general registers constitute a problem on a conventional architecture that has them :-) The Mill does not do simultaneous multithreading (SMT) because we feel the hardware power and area is better spent on multicore (although that is a different discussion irrelevant here). Consequently there is only one thread in a core at any time, and it sees all its writes. When switching to another thread (which is very fast on a Mill) the new thread sees all the writes of the prior thread, with the same ordering as a single-thread executing the same operations would see. Consequently the only issues are between cores, not between threads.Top-level caches (and optionally lower levels as well) are local to cores, and the coherence protocol described in my previous posting maintains the sequential consistency among cores.
[toc] | [prev] | [next] | [standalone]
| From | George Neuner <gneuner2@comcast.net> |
|---|---|
| Date | 2014-04-18 00:46 -0400 |
| Subject | Re: About lockfree and waitfree... (2nd try) |
| Message-ID | <sdb1l95812jak64l3pi011cmc2qok2hbc9@4ax.com> |
| In reply to | #2182 |
On Thu, 17 Apr 2014 19:17:46 -0700, Ivan Godard <ivan@ootbcomp.com> wrote: >When switching to another thread (which is very fast on a Mill) the new >thread sees all the writes of the prior thread, with the same ordering >as a single-thread executing the same operations would see. Then the various lock/wait-free algorithms should have no trouble with threading on a single core. George
[toc] | [prev] | [next] | [standalone]
| From | Ivan Godard <ivan@ootbcomp.com> |
|---|---|
| Date | 2014-04-17 18:52 -0700 |
| Subject | Re: About lockfree and waitfree... (2nd try) |
| Message-ID | <liq0gj$oe2$1@dont-email.me> |
| In reply to | #2179 |
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/.
[toc] | [prev] | [next] | [standalone]
| From | aminer <aminer@toto.net> |
|---|---|
| Date | 2014-04-13 22:54 -0700 |
| Message-ID | <lifiku$i9g$1@news.albasani.net> |
| In reply to | #2157 |
Chris M. Thomasson wrote:
> Can you see where `cmptmp' is updated with the current value
> in the following line:
> ______________________________________
> cmptmp = System.Threading.Interlocked.CompareExchange(
> ref m_tail, next, cmp);
> ______________________________________
>
I have missed that, so there is no bug.
Thank you Chris, have a nice day and hope you are doing well.
Amine Moulay Ramdane.
On 4/13/2014 7:38 PM, Chris M. Thomasson wrote:
>> "aminer" wrote in message news:lif821$inj$1@news.albasani.net... Hello,
>> Look at the following concurrent FIFO queue that have wrote
>> Chriss Thomason:
>> http://pastebin.com/f72cc3cc1
>> I have not learned C# , but look at the following code:
>> ==
>> [...]
>> ==
>> Outside the do{} while you there is a "cmptmp = m_tail;"
>> but if the CAS has succeeded the m_tail will change ,
>
> Can you see where `cmptmp' is updated with the current value
> in the following line:
> ______________________________________
> cmptmp = System.Threading.Interlocked.CompareExchange(
> ref m_tail, next, cmp);
> ______________________________________
>
> ?
>
>
> FWIW, this behaves just like:
>
> http://msdn.microsoft.com/en-us/library/windows/desktop/ms683560(v=vs.85).aspx
>
>
> Examine the return value!
>
> ;^)
[toc] | [prev] | [standalone]
Page 3 of 3 — ← Prev page 1 2 [3]
Back to top | Article view | comp.programming.threads
csiph-web