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

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

About lockfree and waitfree...

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

Contents

  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 1 of 3  [1] 2 3  Next page →

#2155 — About lockfree and waitfree...

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:

==
  public bool pop(out T state) {
       node cmp, cmptmp = m_tail;
       do {
         cmp = cmptmp;
         node next = cmp.m_next;
         if (next == null) {
           state = default(T);
           return false;
         }
         state = next.m_state;
         cmptmp = System.Threading.Interlocked.CompareExchange(ref 
m_tail, next, cmp);
       } while (cmp != cmptmp);
       return true;
     }
   };

==


Outside the do{} while you there is a "cmptmp = m_tail;"

but if the CAS has succeeded the m_tail will change ,
so i think there is a bug cause it is like transactional memory ,
inside the "do{} while" you are keeping the old m_tail inside
the cmptmp variable, so i think this is a bug cause i think "cmptmp = 
m_tail;"
must be located inside the "do{} while" cause if m_tail has changed
and the CAS has failed you have to take the new m_tail, hence
i think  "cmptmp = m_tail" must be located inside the "do{} while".



Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#2157

> "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] | [next] | [standalone]

#2160

> "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] | [next] | [standalone]

#2162

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:47 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] | [next] | [standalone]

#2169

"Chris M. Thomasson"  wrote in message 
news:lifi9j$ka7$1@speranza.aioe.org...

[...]

There is a race-condition in the C#. I placed a damn membar in the wrong 
place. This has been
discussed before:

https://groups.google.com/forum/#!msg/lock-free/Wg9F-EwYfF8/EjPsbS_xS_oJ

___________________________________________________
the C# link has a race-condition in the following function:

public void signal() {
      long cmp = System.Threading.Thread.VolatileRead(ref m_count);
      System.Threading.Thread.MemoryBarrier();
      prv_signal(cmp, false);
    }

The memory barrier needs to be _before_ the load of m_count!!!!
___________________________________________________

:^o




correction:

public void signal()
{
      // MEMBAR BEFORE the DAMN LOAD!!!
      System.Threading.Thread.MemoryBarrier();

      // DO THE LOAD.
      long cmp = System.Threading.Thread.VolatileRead(ref m_count);

      // WAKE A WAITER!
      prv_signal(cmp, false);
}

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

#2170

> "Chris M. Thomasson"  wrote in message 
> news:lihioq$ubs$1@speranza.aioe.org... [...]
> correction:

> public void signal()
> {
>       // MEMBAR BEFORE the DAMN LOAD!!!
>       System.Threading.Thread.MemoryBarrier();
>
>       // DO THE LOAD.
>       long cmp = System.Threading.Thread.VolatileRead(ref m_count);
>
>       // WAKE A WAITER!
>       prv_signal(cmp, false);
> }


FWIW, this fix applies to the broadcast function as well.

The membar needs to be before the load of
the eventcount because the mutations to
the user state that we are signaling about
needs to be visible to the consumers.

I hate devious membar bugs!

Grrr..... 

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

#2171

On 4/14/2014 2:23 PM, Chris M. Thomasson wrote:
>> "Chris M. Thomasson"  wrote in message
>> news:lihioq$ubs$1@speranza.aioe.org... [...]
>> correction:
>
>> public void signal()
>> {
>>       // MEMBAR BEFORE the DAMN LOAD!!!
>>       System.Threading.Thread.MemoryBarrier();
>>
>>       // DO THE LOAD.
>>       long cmp = System.Threading.Thread.VolatileRead(ref m_count);
>>
>>       // WAKE A WAITER!
>>       prv_signal(cmp, false);
>> }
>
>
> FWIW, this fix applies to the broadcast function as well.
>
> The membar needs to be before the load of
> the eventcount because the mutations to
> the user state that we are signaling about
> needs to be visible to the consumers.
>
> I hate devious membar bugs!
>
> Grrr.....

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

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

On 4/14/2014 2:23 PM, Chris M. Thomasson wrote:
>> "Chris M. Thomasson"  wrote in message
>> news:lihioq$ubs$1@speranza.aioe.org... [...] correction:
>
>> public void signal() { // MEMBAR BEFORE the DAMN LOAD!!!
>> System.Threading.Thread.MemoryBarrier();
>>
>> // DO THE LOAD. long cmp = System.Threading.Thread.VolatileRead(ref
>> m_count);
>>
>> // WAKE A WAITER! prv_signal(cmp, false); }
>
>
> FWIW, this fix applies to the broadcast function as well.
>
> The membar needs to be before the load of the eventcount because the
> mutations to the user state that we are signaling about needs to be
> visible to the consumers.
>
> I hate devious membar bugs!
>
> Grrr.....

Are the membars necessary at all if the machine is strict sequential 
concurrency?

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

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

> "Ivan Godard"  wrote in message news:lihr02$g62$2@dont-email.me... 
> On 4/14/2014 2:23 PM, Chris M. Thomasson wrote:
> >> "Chris M. Thomasson"  wrote in message
> >> news:lihioq$ubs$1@speranza.aioe.org... [...] correction:
[...]
> > The membar needs to be before the load of the eventcount because the
> > mutations to the user state that we are signaling about needs to be
> > visible to the consumers.
> >
> > I hate devious membar bugs!
> >
> > Grrr.....

> Are the membars necessary at all if the machine is strict sequential 
> concurrency?

If all of the atomics already have implied "memory_order_seq_cst"
semantics, then you would _not_ need an explicit memory barrier
because the #StoreLoad ordering is already built in.

FWIW, I need #StoreLoad ordering here. This part of the algorithm
requires that a store to location A has to be visible _before_ a load
from location B. Acquire/release semantics is simply not strong
enough here. This is one place where you need an explicit barrier
on an x86. This could be MFENCE, or a dummy call to an atomic
RMW...

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

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

On 4/15/2014 10:04 AM, Chris M. Thomasson wrote:
>> "Ivan Godard"  wrote in message news:lihr02$g62$2@dont-email.me... On
>> 4/14/2014 2:23 PM, Chris M. Thomasson wrote:
>> >> "Chris M. Thomasson"  wrote in message
>> >> news:lihioq$ubs$1@speranza.aioe.org... [...] correction:
> [...]
>> > The membar needs to be before the load of the eventcount because the
>> > mutations to the user state that we are signaling about needs to be
>> > visible to the consumers.
>> >
>> > I hate devious membar bugs!
>> >
>> > Grrr.....
>
>> Are the membars necessary at all if the machine is strict sequential
>> concurrency?
>
> If all of the atomics already have implied "memory_order_seq_cst"
> semantics, then you would _not_ need an explicit memory barrier
> because the #StoreLoad ordering is already built in.
>
> FWIW, I need #StoreLoad ordering here. This part of the algorithm
> requires that a store to location A has to be visible _before_ a load
> from location B. Acquire/release semantics is simply not strong
> enough here. This is one place where you need an explicit barrier
> on an x86. This could be MFENCE, or a dummy call to an atomic
> RMW...


I ask because the Mill is strict sequential concurrency, but we have 
heard of cases in which that is insufficient for certain lock-free 
algorithms, which are only correct with a global strict ordering (i.e. 
global timestamps), but potentially fail with an arbitrary interleaving 
of local strict ordering (i.e. sequential consistency).

Frankly, this stuff makes my head hurt.

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

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

> "Ivan Godard"  wrote in message news:lijqjp$ri0$1@dont-email.me... 
> 
> On 4/15/2014 10:04 AM, Chris M. Thomasson wrote:
> >> "Ivan Godard"  wrote in message news:lihr02$g62$2@dont-email.me... On
> >> 4/14/2014 2:23 PM, Chris M. Thomasson wrote:
> >> >> "Chris M. Thomasson"  wrote in message
> >> >> news:lihioq$ubs$1@speranza.aioe.org... [...] correction:
> > [...]
> >> > The membar needs to be before the load of the eventcount because the
> >> > mutations to the user state that we are signaling about needs to be
> >> > visible to the consumers.
> >> >
> >> > I hate devious membar bugs!
> >> >
> >> > Grrr.....
> >
> >> Are the membars necessary at all if the machine is strict sequential
> >> concurrency?
> >
> > If all of the atomics already have implied "memory_order_seq_cst"
> > semantics, then you would _not_ need an explicit memory barrier
> > because the #StoreLoad ordering is already built in.
> >
> > FWIW, I need #StoreLoad ordering here. This part of the algorithm
> > requires that a store to location A has to be visible _before_ a load
> > from location B. Acquire/release semantics is simply not strong
> > enough here. This is one place where you need an explicit barrier
> > on an x86. This could be MFENCE, or a dummy call to an atomic
> > RMW...


> I ask because the Mill is strict sequential concurrency, but we have 
> heard of cases in which that is insufficient for certain lock-free 
> algorithms, which are only correct with a global strict ordering (i.e. 
> global timestamps), but potentially fail with an arbitrary interleaving 
> of local strict ordering (i.e. sequential consistency).

If you have a hard core setup where you execute the
equivalent of an:

MEMBAR #StoreLoad | #StoreStore| #LoadStore | #LoadLoad;

SPARC instruction before and after each atomic operation,
and the algorithm still fails, then I would look into errors
in the actual algorithm logic itself. IMVHO, it is probably
not keeping sync with the global timestamp. Or, there may
be a problem in the monotonic timestamp generator, wrt
overflow or something...

This does not sound Kosher!


> Frankly, this stuff makes my head hurt.

I am can second that!

:^)

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

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

On 4/17/2014 4:35 PM, Chris M. Thomasson wrote:
>> "Ivan Godard"  wrote in message news:lijqjp$ri0$1@dont-email.me...


>> I ask because the Mill is strict sequential concurrency, but we
>> have heard of cases in which that is insufficient for certain
>> lock-free algorithms, which are only correct with a global strict
>> ordering (i.e. global timestamps), but potentially fail with an
>> arbitrary interleaving of local strict ordering (i.e. sequential
>> consistency).
>
> If you have a hard core setup where you execute the equivalent of
> an:
>
> MEMBAR #StoreLoad | #StoreStore| #LoadStore | #LoadLoad;
>
> SPARC instruction before and after each atomic operation, and the
> algorithm still fails, then I would look into errors in the actual
> algorithm logic itself. IMVHO, it is probably not keeping sync with
> the global timestamp. Or, there may be a problem in the monotonic
> timestamp generator, wrt overflow or something...
>
> This does not sound Kosher!

There is no global timestamp, although the participating programs can 
create one using suitable locking protocols. There are also no atomic 
(pessimistic concurrency) operations.

The Mill defines a total order among load/store operations in any 
particular core; there is no overtaking of requests of any form. That 
is, if within any single core a load issued after a store (for suitable 
definition of "after" given that the Mill is a wide-issue machine which 
can have several load and/or store operations in each instruction) will 
always see the result of that store, while one issued before a store 
(ibid.) will never see the result of the store, and of two stores (one 
after the other) the latter store will be the one seen by a subsequent 
load.

Amongst cores there is no total ordering. However, all cores will see an 
ordering that is an arbitrary interleaving of the orderings of the 
individual cores. That is, within the multicore ordering each core will 
see its own actions in its local total order. This behavior is the 
definition of sequential consistency 
(https://en.wikipedia.org/wiki/Sequential_consistency), which is weaker 
than global total ordering (such as use of a global hardware timestamp).

The Mill does not use pessimistic atomic operations such as T&S, CAS, 
etc. Instead, it supports optimistic concurrency primitives using the 
caching hardware (similar to those primitives also offered by IBM and 
Intel), with hardware backoff support when contention happens. The 
optimistic primitive can be used to implement the pessimistic primitives 
if those are the desired interface, and a library for such use is provided.

We elected to use sequential concurrency because it is the intuitive 
model; many programs are written under the assumption od sequential 
consistency; and it is very difficult to get programs correct under 
weaker models. We elected to use optimistic concurrency because it 
removes the hardware single-point-of-contention that are present in 
pessimistic primitives such as bus locking. We expect that 
low-contention multicore will scale better on a Mill as a result of this 
choice, although high-contention scaling is still bounded by the 
contention, as on any other CPU.

More info on the Mill at http://millcomputing.com/docs.

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

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

In article <lipq6r$l97$1@dont-email.me>,
Ivan Godard  <ivan@ootbcomp.com> wrote:
>
>There is no global timestamp, although the participating programs can 
>create one using suitable locking protocols. There are also no atomic 
>(pessimistic concurrency) operations.

See below.

>We elected to use sequential concurrency because it is the intuitive 
>model; many programs are written under the assumption od sequential 
>consistency; and it is very difficult to get programs correct under 
>weaker models. We elected to use optimistic concurrency because it 
>removes the hardware single-point-of-contention that are present in 
>pessimistic primitives such as bus locking. We expect that 
>low-contention multicore will scale better on a Mill as a result of this 
>choice, although high-contention scaling is still bounded by the 
>contention, as on any other CPU.

Do you mean the same thing by sequential consistency and sequential
concurrency?

Anyway, all of my investigations and analyses agree with what you
say.  I believe that some weak models ARE usable, but only in
combination with enforced programming constraints that prevent the
'impossibilities' from being obtrusive.  And that would mean a
completely new set of programming languages.

However, I find it odd that there is no global clock, because it
is easy to provide if you already have sequential consistency.
The 'implementation' is just that one thread updates the clock
and others read it.  While that does not provide 'physical'
consistency of the time, it's all any sane algorithm needs.


Regards,
Nick Maclaren.

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

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

On 4/18/2014 1:54 AM, Nick Maclaren wrote:
> In article <lipq6r$l97$1@dont-email.me>,
> Ivan Godard  <ivan@ootbcomp.com> wrote:
>>
>> There is no global timestamp, although the participating programs can
>> create one using suitable locking protocols. There are also no atomic
>> (pessimistic concurrency) operations.
>
> See below.
>
>> We elected to use sequential concurrency because it is the intuitive
>> model; many programs are written under the assumption od sequential
>> consistency; and it is very difficult to get programs correct under
>> weaker models. We elected to use optimistic concurrency because it
>> removes the hardware single-point-of-contention that are present in
>> pessimistic primitives such as bus locking. We expect that
>> low-contention multicore will scale better on a Mill as a result of this
>> choice, although high-contention scaling is still bounded by the
>> contention, as on any other CPU.
>
> Do you mean the same thing by sequential consistency and sequential
> concurrency?

"Sequential concurrency" is not a familiar term to me, nor, it appears, 
to Google, which has only one cite and that for some slides that appear 
to have invented the term. So no, I don't :-)

> Anyway, all of my investigations and analyses agree with what you
> say.  I believe that some weak models ARE usable, but only in
> combination with enforced programming constraints that prevent the
> 'impossibilities' from being obtrusive.  And that would mean a
> completely new set of programming languages.
>
> However, I find it odd that there is no global clock, because it
> is easy to provide if you already have sequential consistency.
> The 'implementation' is just that one thread updates the clock
> and others read it.  While that does not provide 'physical'
> consistency of the time, it's all any sane algorithm needs.

I'm describing hardware; there is none in hardware, although a software 
clock is straightforward if you can accept the drawbacks. Global time is 
very difficult in hardware. There may be a single global clock, but 
non-uniform delays in reading the clock mean that two clients of the 
same clock will not agree on the time.

It is certainly possible to have a single global take-a-number that 
gives a unique number to each client on request, and that can be used to 
provide a global ordering, but such systems do not scale - tghe 
take-a-number is a single-point bottleneck, and the round-trip latency 
to the TAN and back is often non-trivial.

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

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

In article <liqrdp$13i$1@dont-email.me>,
Ivan Godard  <ivan@ootbcomp.com> wrote:
>>
>> Do you mean the same thing by sequential consistency and sequential
>> concurrency?
>
>"Sequential concurrency" is not a familiar term to me, nor, it appears, 
>to Google, which has only one cite and that for some slides that appear 
>to have invented the term. So no, I don't :-)

Then could you explain what you mean by it?  I am lost.

>> However, I find it odd that there is no global clock, because it
>> is easy to provide if you already have sequential consistency.
>> The 'implementation' is just that one thread updates the clock
>> and others read it.  While that does not provide 'physical'
>> consistency of the time, it's all any sane algorithm needs.
>
>I'm describing hardware; there is none in hardware, although a software 
>clock is straightforward if you can accept the drawbacks. Global time is 
>very difficult in hardware. There may be a single global clock, but 
>non-uniform delays in reading the clock mean that two clients of the 
>same clock will not agree on the time.

That is true but, if you have sequential consistency, they all
get consistent times.  That is all that almost all algorithms need.

>It is certainly possible to have a single global take-a-number that 
>gives a unique number to each client on request, and that can be used to 
>provide a global ordering, but such systems do not scale - tghe 
>take-a-number is a single-point bottleneck, and the round-trip latency 
>to the TAN and back is often non-trivial.

Now, there I disagree.  The point is that providing a global
time and providing a set of globally ordered tokens are entirely
separate requirements, and the former is fairly easy to scale.

The main requirement for a global clock is for debugging and
tracing - I had to write a mechanism for MPI when I needed it,
which delivers consistency comparable to the round-trip latency.
I could do better in hardware.  Absolute consistency with memory
accesses is not needed, but microsecond-level precision is.

The global take-a-number requirements DON'T need a timestamp,
but only something that is unique and increases monotonically.
I agree that those mechanisms don't scale.

There are two approaches that I know of.  One is that a single
'thread' updates a location, and let the sequentially consistent
memory access handle its distribution.  This means that, if other
threads start hammering on the timestamp, it runs like a drain,
but most genuine requirements for times don't do that.

The other is to have a hierarchical distribution, and not attempt
to maintain consistency with memory accesses.  This can still
provide a guaranteed, small error bound.  I prefer this one, as it
is both highly scalable even under heavy load and gives all that is
needed for almost all clock requirements.



Regards,
Nick Maclaren.

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

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

Nick Maclaren <nmm1@cam.ac.uk> wrote:
+---------------
| Ivan Godard  <ivan@ootbcomp.com> wrote:
| >> Do you mean the same thing by sequential consistency and sequential
| >> concurrency?
| >
| >"Sequential concurrency" is not a familiar term to me, nor, it appears, 
| >to Google, which has only one cite and that for some slides that appear 
| >to have invented the term. So no, I don't :-)
| 
| Then could you explain what you mean by it?  I am lost.
+---------------

Ivan,

What Nick is referring to is that *you* introduced the term
"sequential concurrency" to the thread in a prior posting
[capitalized below for visibility (*not* caps in the original)]:

    Newsgroups: comp.programming.threads,comp.programming,comp.arch
    Date: Thu, 17 Apr 2014 17:04:34 -0700
    Message-ID: <lipq6r$l97$1@dont-email.me>
    Subject: Re: About lockfree and waitfree... (2nd try)
    From: Ivan Godard <ivan@ootbcomp.com>
    ...
    We elected to use SEQUENTIAL CONCURRENCY because it is the intuitive 
    model; many programs are written under the assumption od sequential 
    consistency; and it is very difficult to get programs correct under 
    weaker models. We elected to use optimistic concurrency because it 
    removes the hardware single-point-of-contention that are present in 
    pessimistic primitives such as bus locking. ...

I suspect from your later protests that your use of "sequential
concurrency" above was probably a typo, and that you meant to say
either "sequential consistency" or "optimistic concurrency" there.

But if so, then, like Nick, I am confused as to which one you meant.  ;-}


-Rob

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

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

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

On 4/18/2014 4:26 AM, Rob Warnock wrote:
> Nick Maclaren <nmm1@cam.ac.uk> wrote:
> +---------------
> | Ivan Godard  <ivan@ootbcomp.com> wrote:
> | >> Do you mean the same thing by sequential consistency and sequential
> | >> concurrency?
> | >
> | >"Sequential concurrency" is not a familiar term to me, nor, it appears,
> | >to Google, which has only one cite and that for some slides that appear
> | >to have invented the term. So no, I don't :-)
> |
> | Then could you explain what you mean by it?  I am lost.
> +---------------
>
> Ivan,
>
> What Nick is referring to is that *you* introduced the term
> "sequential concurrency" to the thread in a prior posting
> [capitalized below for visibility (*not* caps in the original)]:
>
>      Newsgroups: comp.programming.threads,comp.programming,comp.arch
>      Date: Thu, 17 Apr 2014 17:04:34 -0700
>      Message-ID: <lipq6r$l97$1@dont-email.me>
>      Subject: Re: About lockfree and waitfree... (2nd try)
>      From: Ivan Godard <ivan@ootbcomp.com>
>      ...
>      We elected to use SEQUENTIAL CONCURRENCY because it is the intuitive
>      model; many programs are written under the assumption od sequential
>      consistency; and it is very difficult to get programs correct under
>      weaker models. We elected to use optimistic concurrency because it
>      removes the hardware single-point-of-contention that are present in
>      pessimistic primitives such as bus locking. ...
>
> I suspect from your later protests that your use of "sequential
> concurrency" above was probably a typo, and that you meant to say
> either "sequential consistency" or "optimistic concurrency" there.
>
> But if so, then, like Nick, I am confused as to which one you meant.  ;-}
>
>
> -Rob
>
> -----
> Rob Warnock		<rpw3@rpw3.org>
> 627 26th Avenue		<http://rpw3.org/>
> San Mateo, CA 94403
>


Oops - I see. Sorry, just a brain fart; "Sequential consistency" was 
intended. Thank you for pointing out my goof.

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

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

>"Ivan Godard"  wrote in message news:lis216$i8l$1@dont-email.me...

>On 4/18/2014 4:26 AM, Rob Warnock wrote:
>> Nick Maclaren <nmm1@cam.ac.uk> wrote:
[...]

I need #StoreLoad | #StoreStore semantics before I read the eventcount.

<crude, simple pseudo-code>
_____________________________________________
#define WAITBIT 0x1


int g_ustate = 0;
int g_ecstate = 0;


void multiple_producer_side()
{
    // A store to the user state that we might
    // want to signal about.

    g_ustate = 123;


    MEMBAR #StoreLoad | #StoreStore;


    // the following load has to occur _AFTER_
    // the mutation to the user state has become
    // visible to consumers!

    int local_load = ATOMIC_LOAD(&g_ecstate);


    if (local_load & WAITBIT)
    {
         // potentially wake a waiter...
    }
}

[...]
_____________________________________________

this is a critical part of the algorithm where I need all
of the waiting consumers to see g_ustate = 123 when
they wake up. This is why I need #StoreLoad ordering
here...


This eventcount governs conditional blocking. Some further
context:

http://dl.acm.org/citation.cfm?id=359076

https://software.intel.com/en-us/forums/topic/295834

https://groups.google.com/d/topic/comp.programming.threads/qoxirQbbs4A/discussion
(SenderX is me)




Carefully examine the waitset object in the following
code:

https://groups.google.com/d/msg/lock-free/acjQ3-89abE/idSNj77HsIIJ

http://pastebin.com/mtCh5Zxu


and how it provides conditional blocking wrt consumers/
producers hitting queue-empty/full conditions... 

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

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

> "Chris M. Thomasson"  wrote in message 
> news:lj42ch$60f$1@speranza.aioe.org...
> > "Ivan Godard"  wrote in message news:lis216$i8l$1@dont-email.me...
>
> > On 4/18/2014 4:26 AM, Rob Warnock wrote:
> >> Nick Maclaren <nmm1@cam.ac.uk> wrote:
> [...]
>
> I need #StoreLoad | #StoreStore semantics before I read the eventcount.
>
> <crude, simple pseudo-code>
> _____________________________________________
> [...]
> _____________________________________________
>
> this is a critical part of the algorithm where I need all
> of the waiting consumers to see g_ustate = 123 when
> they wake up. This is why I need #StoreLoad ordering
> here...

Also, there is another problem with a lost wakeup if
the #StoreLoad ordering is not properly honored...


WRT Mill, I understand that it will work if the affinity
masks bind everything to a single chip... Right?

What about inter-chip communication? Do I have to
use something special for that, like a message passing
interface?

Will the eventcount work with #StoreLoad ordering if
multiple producers/consumers are executing on different
physical chips and/or cores within a single chip? 

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

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

On 4/21/2014 2:31 PM, Chris M. Thomasson wrote:
>> "Chris M. Thomasson"  wrote in message
>> news:lj42ch$60f$1@speranza.aioe.org...
>>> "Ivan Godard"  wrote in message
>>> news:lis216$i8l$1@dont-email.me...
>>
>>> On 4/18/2014 4:26 AM, Rob Warnock wrote:
>>>> Nick Maclaren <nmm1@cam.ac.uk> wrote:
>> [...]
>>
>> I need #StoreLoad | #StoreStore semantics before I read the
>> eventcount.
>>
>> <crude, simple pseudo-code>
>> _____________________________________________ [...]
>> _____________________________________________
>>
>> this is a critical part of the algorithm where I need all of the
>> waiting consumers to see g_ustate = 123 when they wake up. This is
>> why I need #StoreLoad ordering here...
>
> Also, there is another problem with a lost wakeup if the #StoreLoad
> ordering is not properly honored...
>
>
> WRT Mill, I understand that it will work if the affinity masks bind
> everything to a single chip... Right?
>

We equate the scope of coherence with the single shared virtual address 
space. The Mill caches are in virtual, so coherence is by virtual 
address. Two different virtual addresses that are mapped to the same 
physical address do not cohere. However, cross-mapping like that is used 
only for constant data (or COW data) and for the OS access to the page 
tables; appplications, and the OS apart from the pager, do not see 
physical aliasing.

Affinity can migrate, but only within that single global space. 
Currently we plan to restrict a single address space to a single chip. 
Although family members may be configured with several global spaces on 
a single chip (each with their associated cores), none of those spaces 
extend off-chip. There is of course no coherence among different spaces, 
because there are no shared addresses to cohere.


> What about inter-chip communication? Do I have to use something
> special for that, like a message passing interface?

Yes. That on-chip/off-chip distinction seems to be the way HPC is going, 
and board/rack/room level coherence seems to be of legacy interest only. 
Of course, if a customer were willing to pay the NRE...

> Will the eventcount work with #StoreLoad ordering if multiple
> producers/consumers are executing on different physical chips and/or
> cores within a single chip?

I think so, on one chip and for cores that use the same global address 
space. But I'd really like someone who knows this stuff to work it 
through and confirm. It's not my expertise.

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web