comp.programming.threads

Stephen Fuld

4/25/2014 8:39:00 PM

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


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)