Groups > comp.programming.threads > #2225

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

From	Stephen Fuld <SFuld@alumni.cmu.edu.invalid>
Newsgroups	comp.programming.threads, comp.programming, comp.arch
Subject	Re: About lockfree and waitfree... (2nd try)
Date	2014-04-23 12:08 -0700
Organization	A noiseless patient Spider
Message-ID	<lj933b$i85$1@dont-email.me> (permalink)
References	(2 earlier) <od3bl95plai9mrkbi0saa12314j1aolh6m@4ax.com> <lj44ik$437$1@dont-email.me> <lj57rr$e7q$1@needham.csi.cam.ac.uk> <lj659h$u1s$1@dont-email.me> <lj66c0$6ji$1@dont-email.me>

Cross-posted to 3 groups.

Show all headers | View raw

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)

Thread

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

csiph-web