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

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

> "Ivan Godard"  wrote in message news:lj4412$s26$1@dont-email.me... 
> On 4/21/2014 2:31 PM, Chris M. Thomasson wrote:
> [massive snip]

> > 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.

First test would be can you emulate Linux on a box with
multiple chips, and run the futexs through a contrived heavy
load environment, with all affinity masks of participating threads
bound to a single chip?

So, using two chips reading with non-conflicting pieces of a single
shared main memory is bad? Think of RCU, with two reader chips...

RCU = Read-Copy Update

Another chip is the writer; the update part in RCU.

So, three chips, two readers, one writer.


A simple description:

http://en.wikipedia.org/wiki/Read-copy-update

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

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

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

> "Ivan Godard"  wrote in message news:lj4412$s26$1@dont-email.me... On 
> 4/21/2014 2:31 PM, Chris M. Thomasson wrote:
> [massive snip]

> > 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.

[RCU snip]

FWIW,

Some RCU implementations assume that inter-chip
communication can be realized with atomic loads/stores
guarded with the "least intrusive set" of required
memory barriers to a shared memory...

Think of a x86 dual chip system. Chip A and Chip B can
perform loop less atomic load/store operations on a shared
location. Think of a single producer, single consumer shared
waitfree queue...

Loads and stores on an x86 have implied acquire/release
semantics, such that you do not need an explicit memory
barrier when you release a spinlock.

However, if you need a store to cache line A to be rendered
visible before a subsequent load from cache line B, well, you
need something to provide the #StoreLoad ordering.

A futex or eventcount with a fastpath signal via loading and
testing a waitbit depends on the membars it has in existing
code to work as expected. Inter-chip or not.


http://sourceware.org/binutils/docs/as/Sparc_002dConstants.html 

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

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

On 4/22/2014 2:21 PM, Chris M. Thomasson wrote:
>> "Ivan Godard"  wrote in message news:lj4412$s26$1@dont-email.me... On
>> 4/21/2014 2:31 PM, Chris M. Thomasson wrote:
>> [massive snip]
>
>> > 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.
>
> First test would be can you emulate Linux on a box with
> multiple chips, and run the futexs through a contrived heavy
> load environment, with all affinity masks of participating threads
> bound to a single chip?
>
> So, using two chips reading with non-conflicting pieces of a single
> shared main memory is bad? Think of RCU, with two reader chips...
>
> RCU = Read-Copy Update
>
> Another chip is the writer; the update part in RCU.
>
> So, three chips, two readers, one writer.
>
>
> A simple description:
>
> http://en.wikipedia.org/wiki/Read-copy-update

In-memory RCU and all other memory-based coordination does not work on a 
Mill, because on a Mill the data in cache may be backless and have no 
DRAM behind it. Consequently RCU and other algorithms must be 
cache-based. However, the critical read and write operations to the key 
pointer are atomic (so long as the pointer is aligned or, if not 
aligned, does not cross a line boundary) for both backed and backless 
data, so I see no problem there.

The basic RCU trick of serializing writers by forcing them to be readers 
and scheduling around the cores should work on a Mill. However, this 
scheme has costs that scale at least with the number of cores. I'm 
doubtful about usage in high-update-high-corecount environments, on any 
architecture. The scaling should be no worse on a Mill, although the 
constant factor may be higher: Mills do significantly less task 
switching than other architectures because most of what involves IPC on 
a conventional machine uses portal calls instead of task switches on a 
Mill; as a result we expect more of a time slice to be consumed on 
average, so daisy-chaining around the cores will take longer.

I also expect the Mills optimistic synchronization primitive will 
provide a better way to do writer serialization than classic RCU. To 
begin with, it deals with multiple-update algorithms, such as updating a 
bi-linked list, which RCU doesn't do. Secondly, it permits writers to 
update at rates faster than the daisy-chain latency, although it could 
still use the daisy-chain to know that readers have been purged for 
scavenge. Thus adding a new node to a list (using the Mill primitive, 
and assuming no update contention) takes a read and two writes, without 
any trip around the cores. Deleting one takes two loads and a store 
before the next writer can go to work, although scavenging the deleted 
node requires a trip around, although more likely the deleted node is 
put on the work list of a scavenge thread that does the daisy chain on 
behalf of the deleting thread.

Conclusion: classic RCU should work with the same costs and scale 
factors, but using the Mill optimistic concurrency is more general and 
scales better than classic, especially in high-update and high core 
count environments.

That is, if I have understood the RCU :-)

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

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

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

> On 4/22/2014 2:21 PM, Chris M. Thomasson wrote:
[...]

> Conclusion: classic RCU should work with the same costs and scale 
> factors, but using the Mill optimistic concurrency is more general and 
> scales better than classic, especially in high-update and high core 
> count environments.

> That is, if I have understood the RCU :-)

I think you have: Thanks Ivan.


FWIW, here is some more interesting
information on RCU:

https://lwn.net/Articles/573424

There is a quick quiz in the article on
using RCU within the realm of Linux...

;^)

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

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

> "Chris M. Thomasson"  wrote in message 
> news:ljsu7l$1ou$1@speranza.aioe.org...

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

> On 4/22/2014 2:21 PM, Chris M. Thomasson wrote:
> [...]

> > Conclusion: classic RCU should work with the same costs and scale 
> > factors, but using the Mill optimistic concurrency is more general and 
> > scales better than classic, especially in high-update and high core 
> > count environments.

The writer side of RCU can be based on clever optimistic
concurrency impl for sure. IMVHO, a mix of simple
atomic exchange, and fetch-and-add along with the
existing optimistic concurrency scheme might be able
to give the best of both worlds.


> That is, if I have understood the RCU :-)

FWIW, the reader side of RCU has to be "as free as can
be". If it is not, then the read part of RCU can quickly loose
its luster.

A DEC Alpha forces RCU to execute a damn memory barrier
for a simple data-dependent load... Ouch. 

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

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

> "Chris M. Thomasson"  wrote in message 
> news:lj42ch$60f$1@speranza.aioe.org... [...]

FWIW, the eventcount is kind of similar to a FUTEX... 

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

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

On Fri, 18 Apr 2014 02:31:29 -0700, Ivan Godard <ivan@ootbcomp.com>
wrote:

>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.


So long as you don't need to hand out sequential numbers it's not that
hard.  Just keep a synchronized clock in each CPU, running at roughly
the clock rate (or the maximum rate numbers can be requested).  Tack
on an ID for the CPU, so that each CPU's "get value" will generate a
different result.

The synchronization is the only semi-hard part, but you only need to
synchronize any pair of CPU timers to about the speed-of-light delay
between them.  So the clocks on the cores on a single chip need to be
synchronized sub-nanosecond (easy), chips on a single boards at the ns
level (easy) chips on different NUMA nodes with within 10ns (easy),
cores in different machines in a cluster 100ns (again easy).

The speed-of-light thing makes it impossible for events on cores
separated by a distance to really have meaningful orderings with
resolutions less than the minimum implied by the speed of light (or
whatever your actual minimum propagation delay for any signal between
those nodes).

Of course I've just described the S/370 clock.

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

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

On 4/21/2014 2:42 PM, Robert Wessel wrote:
> On Fri, 18 Apr 2014 02:31:29 -0700, Ivan Godard <ivan@ootbcomp.com>
> wrote:

<snip>

>> 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.
>
>
> So long as you don't need to hand out sequential numbers it's not that
> hard.  Just keep a synchronized clock in each CPU, running at roughly
> the clock rate (or the maximum rate numbers can be requested).  Tack
> on an ID for the CPU, so that each CPU's "get value" will generate a
> different result.
>
> The synchronization is the only semi-hard part, but you only need to
> synchronize any pair of CPU timers to about the speed-of-light delay
> between them.  So the clocks on the cores on a single chip need to be
> synchronized sub-nanosecond (easy), chips on a single boards at the ns
> level (easy) chips on different NUMA nodes with within 10ns (easy),
> cores in different machines in a cluster 100ns (again easy).
>
> The speed-of-light thing makes it impossible for events on cores
> separated by a distance to really have meaningful orderings with
> resolutions less than the minimum implied by the speed of light (or
> whatever your actual minimum propagation delay for any signal between
> those nodes).
>
> Of course I've just described the S/370 clock.
>

The TANs I had in mind need not be sequential but must be ordered by 
access. That is, they must map to the time arrow but may have holes in 
the sequence. The numbers are to be used to give a priority ordering to 
ensure fairness in places where starvation is possible. The scheme you 
describe gives unique numbers, but not a global ordering. Or at least, 
if I have understood it :-)

When talking about speed-of-light latency we are getting into 
event-horizon issues. I don't want a Mill to start manufacturing mini 
black holes :-)

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

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

In article <lj44ik$437$1@dont-email.me>,
Ivan Godard  <ivan@ootbcomp.com> wrote:
>
>The TANs I had in mind need not be sequential but must be ordered by 
>access. That is, they must map to the time arrow but may have holes in 
>the sequence. The numbers are to be used to give a priority ordering to 
>ensure fairness in places where starvation is possible. The scheme you 
>describe gives unique numbers, but not a global ordering. Or at least, 
>if I have understood it :-)

Yes.  Providing something that supports those algorithms is hard
to make efficient on more than a few cores.

>When talking about speed-of-light latency we are getting into 
>event-horizon issues. I don't want a Mill to start manufacturing mini 
>black holes :-)

You needn't worry!  There's no gravity, so we are dealing with
only special relativity :-)

However, Robert is right.  Parallel processes are synchronisable
only to a precision of the transmission latency, without relying
on extra constraints.  Lower resolutions are (fairly) easy; higher
are hard to very hard.


Regards,
Nick Maclaren.

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

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

On 4/22/2014 1:05 AM, Nick Maclaren wrote:
> In article <lj44ik$437$1@dont-email.me>,
> Ivan Godard  <ivan@ootbcomp.com> wrote:
>>
>> The TANs I had in mind need not be sequential but must be ordered by
>> access. That is, they must map to the time arrow but may have holes in
>> the sequence. The numbers are to be used to give a priority ordering to
>> ensure fairness in places where starvation is possible. The scheme you
>> describe gives unique numbers, but not a global ordering. Or at least,
>> if I have understood it :-)
>
> Yes.  Providing something that supports those algorithms is hard
> to make efficient on more than a few cores.

Yes, but as I understand Ivan's previous posts, there is no intent to 
provide this capability over more cores than are in a single chip.  Is 
that correct Ivan?  If that is so, then the scaling issues aren't a 
problem.  Heck, even for a system with a few chips on a board, with say 
core total counts in the 10s of cores, a simple scheme should work 
pretty well.  You can create problem situations like every executing 
reads of that register in a single instruction loop, but in real world 
usage, it should be fine.

All you really need is a single register (with appropriate arbitration) 
that is incremented after each read.  Or, if you already have a global 
time of day/date clock, you can use that with another, shorter, register 
logically appended to it with the shorter register incremented on each 
read and reset to zero on each TOD click.




-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

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

On 4/22/2014 9:27 AM, Stephen Fuld wrote:
> On 4/22/2014 1:05 AM, Nick Maclaren wrote:
>> In article <lj44ik$437$1@dont-email.me>, Ivan Godard
>> <ivan@ootbcomp.com> wrote:
>>>
>>> The TANs I had in mind need not be sequential but must be ordered
>>> by access. That is, they must map to the time arrow but may have
>>> holes in the sequence. The numbers are to be used to give a
>>> priority ordering to ensure fairness in places where starvation
>>> is possible. The scheme you describe gives unique numbers, but
>>> not a global ordering. Or at least, if I have understood it :-)
>>
>> Yes.  Providing something that supports those algorithms is hard to
>> make efficient on more than a few cores.
>
> Yes, but as I understand Ivan's previous posts, there is no intent to
>  provide this capability over more cores than are in a single chip.
> Is that correct Ivan?

Yes; there is no Mill state off-chip, in general. Or that's the plan, 
anyway. Remember though: "No plan survives contact with the enemy" - N. 
Bonaparte.

  If that is so, then the scaling issues aren't
> a problem.  Heck, even for a system with a few chips on a board, with
> say core total counts in the 10s of cores, a simple scheme should
> work pretty well.  You can create problem situations like every
> executing reads of that register in a single instruction loop, but in
> real world usage, it should be fine.
>
> All you really need is a single register (with appropriate
> arbitration) that is incremented after each read.  Or, if you already
> have a global time of day/date clock, you can use that with another,
> shorter, register logically appended to it with the shorter register
> incremented on each read and reset to zero on each TOD click.

I see you agree that it doesn't scale. Yes, a single central TAN scales 
OK for a handful of cores and a 10-cycle or so cross-chip latency. 
However, we try to avoid building process dependence into the 
architecture. That TAN won't scale when there are 10,000 cores or 
hundred-cycle edge-to-edge transit, and we're not about to assume that 
the process industry is incapable of making such chips within the 
lifetime of the Mill architecture.

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

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

In article <lj66c0$6ji$1@dont-email.me>,
Ivan Godard  <ivan@ootbcomp.com> wrote:
>
>Yes; there is no Mill state off-chip, in general. Or that's the plan, 
>anyway. Remember though: "No plan survives contact with the enemy" - N. 
>Bonaparte.

Helmuth von Moltke, shirley?

>  If that is so, then the scaling issues aren't
>> a problem.  Heck, even for a system with a few chips on a board, with
>> say core total counts in the 10s of cores, a simple scheme should
>> work pretty well.  You can create problem situations like every
>> executing reads of that register in a single instruction loop, but in
>> real world usage, it should be fine.
>>
>> All you really need is a single register (with appropriate
>> arbitration) that is incremented after each read.  Or, if you already
>> have a global time of day/date clock, you can use that with another,
>> shorter, register logically appended to it with the shorter register
>> incremented on each read and reset to zero on each TOD click.
>
>I see you agree that it doesn't scale. Yes, a single central TAN scales 
>OK for a handful of cores and a 10-cycle or so cross-chip latency. 
>However, we try to avoid building process dependence into the 
>architecture. That TAN won't scale when there are 10,000 cores or 
>hundred-cycle edge-to-edge transit, and we're not about to assume that 
>the process industry is incapable of making such chips within the 
>lifetime of the Mill architecture.

It's a problem even for dozens of cores when you want to use it
to order shared-cache accesses, right across the chip!


Regards,
Nick Maclaren.

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

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

On 4/22/2014 9:45 AM, Ivan Godard wrote:
> On 4/22/2014 9:27 AM, Stephen Fuld wrote:
>> On 4/22/2014 1:05 AM, Nick Maclaren wrote:
>>> In article <lj44ik$437$1@dont-email.me>, Ivan Godard
>>> <ivan@ootbcomp.com> wrote:
>>>>
>>>> The TANs I had in mind need not be sequential but must be ordered
>>>> by access. That is, they must map to the time arrow but may have
>>>> holes in the sequence. The numbers are to be used to give a
>>>> priority ordering to ensure fairness in places where starvation
>>>> is possible. The scheme you describe gives unique numbers, but
>>>> not a global ordering. Or at least, if I have understood it :-)
>>>
>>> Yes.  Providing something that supports those algorithms is hard to
>>> make efficient on more than a few cores.
>>
>> Yes, but as I understand Ivan's previous posts, there is no intent to
>>  provide this capability over more cores than are in a single chip.
>> Is that correct Ivan?
>
> Yes; there is no Mill state off-chip, in general. Or that's the plan,
> anyway. Remember though: "No plan survives contact with the enemy" - N.
> Bonaparte.
>
>   If that is so, then the scaling issues aren't
>> a problem.  Heck, even for a system with a few chips on a board, with
>> say core total counts in the 10s of cores, a simple scheme should
>> work pretty well.  You can create problem situations like every
>> executing reads of that register in a single instruction loop, but in
>> real world usage, it should be fine.
>>
>> All you really need is a single register (with appropriate
>> arbitration) that is incremented after each read.  Or, if you already
>> have a global time of day/date clock, you can use that with another,
>> shorter, register logically appended to it with the shorter register
>> incremented on each read and reset to zero on each TOD click.
>
> I see you agree that it doesn't scale. Yes, a single central TAN scales
> OK for a handful of cores and a 10-cycle or so cross-chip latency.
> However, we try to avoid building process dependence into the
> architecture. That TAN won't scale when there are 10,000 cores or
> hundred-cycle edge-to-edge transit, and we're not about to assume that
> the process industry is incapable of making such chips within the
> lifetime of the Mill architecture.

I have been thinking about this.  Does the following work?

There are three parts.  The first part solves the scalability problem, 
but introduces a potential duplicates problem.  The second part solves 
the potential duplicates problem, but introduces a priority problem. 
The third part roughly solves the priority problem.

To solve the scalability problem, you have multiple incrementing counter 
registers, perhaps one per core, or one per few cores with arbitration, 
that are distributed around the chip, but synchronized quite closely, 
say at the sub nanosecond level.  Now each core can read one of the 
registers and get a number.  Reads of the same register are guaranteed 
to be unique and in ascending order, but it is possible for readers of 
different registers to get the same value.

To fix that, the when a core reads the register, it also gets appended 
to the counter, the value of an identifier register that is initialized 
to a unique value such as "core number".  This assures that readers that 
read different registers within the chip get unique values, even if the 
counter part is the same.  But this solution creates a priority problem 
in that cores with lower core number always have lower numbers (higher 
priority?) than cores with higher numbers where the code reads the same 
value for the counter.

To fix the priority problem, independently for each counter, when the 
counter increments to so value mod a predefined constant (say perhaps 
about one microsecond), the value of the identifier register is 
incremented, mod the number of registers.  This changes the priority 
such that priority "rotates" among all the cores preventing one core 
from abusing its high priority.

Does this solve the TAN problem, at least for a supposed 10,000 core chip?


-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

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

In article <lj933b$i85$1@dont-email.me>,
Stephen Fuld  <SFuld@Alumni.cmu.edu.invalid> wrote:
>
>I have been thinking about this.  Does the following work?

No.  Sorry.

>To solve the scalability problem, you have multiple incrementing counter 
>registers, perhaps one per core, or one per few cores with arbitration, 
>that are distributed around the chip, but synchronized quite closely, 
>say at the sub nanosecond level.  ...

First problem.  How?  That's probably not impossible, but it's
not obviously possible, either.

>Does this solve the TAN problem, at least for a supposed 10,000 core chip?

No, for two reasons:

    That won't deliver temporarily consistent timestamps, which are
the critical requirement for that facilities.  That is essentially
sequential consistency on the timestamps.

    What many such algorithms need is a timer that can be used to
determine in which order memory accesses were made.  I think those
are a hopeless idea, but that doesn't stop people wanting them.


Regards,
Nick Maclaren.

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

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

On 4/23/2014 12:32 PM, Nick Maclaren wrote:
> In article <lj933b$i85$1@dont-email.me>,
> Stephen Fuld  <SFuld@Alumni.cmu.edu.invalid> wrote:
>>
>> I have been thinking about this.  Does the following work?
>
> No.  Sorry.
>
>> To solve the scalability problem, you have multiple incrementing counter
>> registers, perhaps one per core, or one per few cores with arbitration,
>> that are distributed around the chip, but synchronized quite closely,
>> say at the sub nanosecond level.  ...
>
> First problem.  How?  That's probably not impossible, but it's
> not obviously possible, either.

Well, I am not a circuits guy, but I am basing this on Ivan's post, 
quoted below.

>  So the clocks on the cores on a single chip need to be
> synchronized sub-nanosecond (easy),



>
>> Does this solve the TAN problem, at least for a supposed 10,000 core chip?
>
> No, for two reasons:
>
>      That won't deliver temporarily consistent timestamps, which are
> the critical requirement for that facilities.  That is essentially
> sequential consistency on the timestamps.

I thought the TAN problem was stated as no two people get the same 
number but the numbers need not be strictly sequential (i.e. there nay 
be holes), and no requester has enough priority to starve another 
requester.  BTW, did you mean "temporally"?


>      What many such algorithms need is a timer that can be used to
> determine in which order memory accesses were made.  I think those
> are a hopeless idea, but that doesn't stop people wanting them.

I don't think that is what Ivan asked for, but I agree that my proposal 
doesn't solve that problem.



-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

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

In article <lj97cc$hfk$1@dont-email.me>,
Stephen Fuld  <SFuld@Alumni.cmu.edu.invalid> wrote:
>>
>Well, I am not a circuits guy, but I am basing this on Ivan's post, 
>quoted below.
>
>>  So the clocks on the cores on a single chip need to be
>> synchronized sub-nanosecond (easy),

Nor am I, but I didn't think that was a known easy task.  However,
it might be - what I am pretty sure is that it is not obviously
so for 100,000 cores, to anyone who hasn't looked at the problem
fairly hard.

>>> Does this solve the TAN problem, at least for a supposed 10,000 core chip?
>>
>> No, for two reasons:
>>
>>      That won't deliver temporarily consistent timestamps, which are
>> the critical requirement for that facilities.  That is essentially
>> sequential consistency on the timestamps.
>
>I thought the TAN problem was stated as no two people get the same 
>number but the numbers need not be strictly sequential (i.e. there nay 
>be holes), and no requester has enough priority to starve another 
>requester.  BTW, did you mean "temporally"?

Yes :-)  Simply getting distinct sequences of keys with each thread's
sequence sequential is easy, but not very useful.  Your description
is correct, but incomplete, because there is also the requirement
for sequential consistency.  And some (many?) algorithms that want
numbers of that form want them consistent with memory accesses.

>>      What many such algorithms need is a timer that can be used to
>> determine in which order memory accesses were made.  I think those
>> are a hopeless idea, but that doesn't stop people wanting them.
>
>I don't think that is what Ivan asked for, but I agree that my proposal 
>doesn't solve that problem.

Nor does anything else, at least not scalably :-)


Regards,
Nick Maclaren.

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

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

nmm@needham.csi.cam.ac.uk (Nick Maclaren) writes:

> Yes :-)  Simply getting distinct sequences of keys with each thread's
> sequence sequential is easy, but not very useful.  Your description
> is correct, but incomplete, because there is also the requirement
> for sequential consistency.  And some (many?) algorithms that want
> numbers of that form want them consistent with memory accesses.

I promised myself I wouldn't post on this group, since I'm not qualified, but
I've been thinking about this one. I too am a software guy.

What exactly does "sequential consistency" mean? Does it mean that successive
reads of the TAN facility return a strict counting sequence of values? If so,
then I certainly can't see any kind of realistic solution.

If, however, you only need successive reads by a given reader to always
return increasing values, and that reads by different readers never return
the same value, then Stephen's solution looks good to me. I had thought that
the only consistency needed was what it provides. Other systems use simple
clock registers, and using those there can be other ways in which gaps can
appear in the sequence as read by any given reader. Note that Stephen's
solution does create a global ordering among all of the requesters, and that
ordering makes sense temporally. There is nothing said about the ordering
received by different requesters that make their requests "at the same time",
but that pretty much has to be the case. The solution decides that ordering
based on the per-"register" ID bits.


Now as a software guy, I also wonder about the implementability of this stuff
at the hardware level. If a "register" has two parts, and the two parts are
updated by independent mechanisms, when is the register stable? This is
especially important if one part is being decreased and a higher part is
being increased. It's the same as a simple counter, in that you have to read
the value after the carry has propagated all the way to the top of the
register. Since that works, I assume Stephen's scheme can work too. Perhaps
the HW guys just design things so that values are stable by the first half of
a cycle, and all reads are done in the second half of the cycle, or some
such.

I also wonder about the ideas of a counter being updated on a read. My naive
view of registers (or belt positions) was that they could just be gated onto
buses as needed. If readers are supposed to get different values, such a
setup won't work. What if multiple readers on a multiple issue core request a
value during the same cycle? How can the hardware guarantee they all get
different values? You would have to expand Stephen's solution to provide a
separate TAN source for each execution unit.

-- 
Chris Gray

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

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

In article <87y4yu654p.fsf@GraySage.COM>, Chris Gray  <cg@GraySage.COM> wrote:
>
>> Yes :-)  Simply getting distinct sequences of keys with each thread's
>> sequence sequential is easy, but not very useful.  Your description
>> is correct, but incomplete, because there is also the requirement
>> for sequential consistency.  And some (many?) algorithms that want
>> numbers of that form want them consistent with memory accesses.
>
>I promised myself I wouldn't post on this group, since I'm not qualified, but
>I've been thinking about this one. I too am a software guy.

Don't worry - few of us are - indeed, I am about as unqualified in
IT (in a formal sense) as anyone, being of an era when we learnt
by being dropped in the deep end :-)

>What exactly does "sequential consistency" mean? Does it mean that successive
>reads of the TAN facility return a strict counting sequence of values? If so,
>then I certainly can't see any kind of realistic solution.

No.  It means that separate threads see sequences of numbers that
could have been produced from a single server returning monotonically
increasing values.

    http://en.wikipedia.org/wiki/Sequential_consistency


Regards,
Nick Maclaren.

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

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

On 4/24/2014 10:02 AM, Nick Maclaren wrote:
> In article <87y4yu654p.fsf@GraySage.COM>, Chris Gray  <cg@GraySage.COM> wrote:
>>
>>> Yes :-)  Simply getting distinct sequences of keys with each thread's
>>> sequence sequential is easy, but not very useful.  Your description
>>> is correct, but incomplete, because there is also the requirement
>>> for sequential consistency.  And some (many?) algorithms that want
>>> numbers of that form want them consistent with memory accesses.
>>
>> I promised myself I wouldn't post on this group, since I'm not qualified, but
>> I've been thinking about this one. I too am a software guy.
>
> Don't worry - few of us are - indeed, I am about as unqualified in
> IT (in a formal sense) as anyone, being of an era when we learnt
> by being dropped in the deep end :-)
>
>> What exactly does "sequential consistency" mean? Does it mean that successive
>> reads of the TAN facility return a strict counting sequence of values? If so,
>> then I certainly can't see any kind of realistic solution.
>
> No.  It means that separate threads see sequences of numbers that
> could have been produced from a single server returning monotonically
> increasing values.
>
>      http://en.wikipedia.org/wiki/Sequential_consistency


I have been thinking more about this.  Based on the ideas given in the 
above reference I believe that my proposal does this as well as is 
theoretically possible.

Consider a concrete example,  Let's assume there are 64 cores, each with 
its own copy of the counter register and that they are synchronized to 
sub 1 ns. and that they count at the rate of 1 ns. So 1 ns is the 
"quantum" or granularity of the information.

Thus any process reading one of the registers receives a value in ns 
plus 6 extra low order bits (from the id), that, to all intents are to 
it, random.  I think we agree that if two processes on different cores 
read values and they are separated by say several nanoseconds, there is 
no problem.  We know which came first.

A question arises if two processes read their respective registers 
within the same ns, and get the same high order value, but different low 
order bits due to the id.  The results are unique, but since they are 
below the granularity of the counter, we don't know which came first, 
that is, process 1 could have been at a nanosecond plus .25ns and 
process two at a nanosecond plus .75.  It is possible that the id 
numbers will be such that process two's value will actually be lower 
than process one's value, and this would violate sequentiality.  But I 
maintain that, short of an infinitely precise clock, obviously 
impossible, two processes could read the read the clock within the same 
granularity and get the same number.  But below the granularity it is 
impossible to know which came first, so the choice is arbitrary.  Thus 
the choice imposed by the id is as good as any other, and has the 
advantage of enforcing uniqueness.

What am I missing?

I should also note that I don't doubt that there are algorithms that 
need something more, I maintain that there are useful scenarios for 
which my proposal is entirely adequate.  These include, for example, 
transaction numbers in a database system.  The requirement is for 
uniqueness and they occur say several hundred thousand times per second. 
  The exact sequential order, down to sub nanoseconds is not really needed.




-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

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

"Ivan Godard"  wrote in message news:lj44ik$437$1@dont-email.me...
[...]
> When talking about speed-of-light latency we are getting into 
> event-horizon issues. I don't want a Mill to start manufacturing mini 
> black holes :-)

Ahh, I love the extreme beauty of the MSO735 and/or 0J287 galaxy(s).
With x-ray cavities extending over 600,000 light years across!

Explosion with the energy of several billion super novas occurring
within the giant central galaxy?

Pardon my French, but Holy C$Q@#$@P!!!!!!

:^o 

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

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

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

csiph-web