>>> Probably better to say an integer-data-path than a mini-CPU.
>>> It certainly is not taking interrupts, allowed to deal with exceptions, no
>>> FP and likely not even LD, ST, or even branches.
>>
>> I think I am going to try implementing a coherence point processor, CPP,
>> to see how well it works. I am sketching out a CPP with 16 opcodes, 13-bit
>> instructions. It will be able to load / store and branch according to counted
>> loop. Treating the instruction buffer as a shift register, so no program
>> counter even. I am reminded of the additional logic that does raster ops in
>> EGA video or something like the COPPER in the AMIGA. The CPP will have
>> a set of “programs” allowing it to do compare-and-swap and
>> exchange-and-add and others. My main core will pass arguments and a
>> program number to execute to the CPP.

>How is this CPP different from a single serializing lock?

It could be used to implement a single serializing lock so it is not different. I had
thought being able to issue more memory operations under the same lock
would be useful. However, once a flag is set to lock an area ordinary instructions
could be used.
I have set the CPP aside for now as being overly complex. Unless a really
complicated AMO is desired, it is easier just to implement indivisible RMW
cycles at the coherence point. Implementing the RMW cycles bumped up the
size of my memory controller a lot, about 25%. 21,000 to 26,000 LUTs. A CPP
would be worse still. It will be a challenge getting the whole project to fit.
From the core's perspective how things are implemented at the coherence point
should be irrelevant. It just sends out an opcode to that point. I think I have got
the idea now. And using the Wishbone bus has some to be desired as it does not
support CMPXCHG directly. I must build onto it.

robf...@gmail.com wrote:
>>>> Probably better to say an integer-data-path than a mini-CPU.
>>>> It certainly is not taking interrupts, allowed to deal with exceptions, no
>>>> FP and likely not even LD, ST, or even branches.
>>> I think I am going to try implementing a coherence point processor, CPP,
>>> to see how well it works. I am sketching out a CPP with 16 opcodes, 13-bit
>>> instructions. It will be able to load / store and branch according to counted
>>> loop. Treating the instruction buffer as a shift register, so no program
>>> counter even. I am reminded of the additional logic that does raster ops in
>>> EGA video or something like the COPPER in the AMIGA. The CPP will have
>>> a set of “programs” allowing it to do compare-and-swap and
>>> exchange-and-add and others. My main core will pass arguments and a
>>> program number to execute to the CPP.
>
>> How is this CPP different from a single serializing lock?
>
> It could be used to implement a single serializing lock so it is not different. I had
> thought being able to issue more memory operations under the same lock
> would be useful. However, once a flag is set to lock an area ordinary instructions
> could be used.
> I have set the CPP aside for now as being overly complex. Unless a really
> complicated AMO is desired, it is easier just to implement indivisible RMW
> cycles at the coherence point. Implementing the RMW cycles bumped up the
> size of my memory controller a lot, about 25%. 21,000 to 26,000 LUTs. A CPP
> would be worse still. It will be a challenge getting the whole project to fit.
> From the core's perspective how things are implemented at the coherence point
> should be irrelevant. It just sends out an opcode to that point. I think I have got
> the idea now. And using the Wishbone bus has some to be desired as it does not
> support CMPXCHG directly. I must build onto it.

There are two uses for Read-Modify-Write RMW memory operations:
as non-interruptible sequences for small communications between priority
interrupt handlers and lower or non-interrupt levels within a single core,
and atomic operation between cores in an SMP system.

Non-interruptible operations are needed so that an OS does not
have to be continually disabling and enabling interrupts as that
can be very expensive.

Non-interruptible operations are locally coherent because a
single core is always sees its own memory operations in order
and so do not require any memory barriers.

The set non-interruptible instructions is the same as atomic ones,
NFADD Non-interruptible fetch then ADD
NFAND Non-interruptible fetch then AND
NFOR Non-interruptible fetch then OR
NFXOR Non-interruptible fetch then XOR
NSWAP Non-interruptible SWAP
NCAS Non-interruptible Compare-And-Swap

There is also a use for some double wide swap operations
NSWAPW Non-interruptible SWAP Wide
NCASW Non-interruptible Compare-And-Swap Wide

Atomic operations have the additional requirement for various
memory barriers to ensure the global coherence rules are followed.
The barriers are applied locally first, such as flushing local caches,
then at the cache coherence level, such synchronizing with the
inbound and outbound cache comms message queues,
before the memory RMW changes can be applied.

Those barriers can be explicit or implicit.
If those barriers are explicit then to get atomic operations
they would be combined with the non-interruptible instructions:
MEMBAR_RW
NFADD
MEMBAR_RW

If those barriers are implied in the atomic instruction then there
is a second set of RMW instruction which combine the non-interruptible
operations with the implied barriers:
AFADD, AFAND, AFOR, AFXOR, ASWAP, ACAS, ASWAPW, and ACASW.

The advantage to having the barriers explicit is that a
programmer may know more about their use context and may
be able to use a weaker barrier with less performance implications.
Also multiple instructions can occur between two barriers.

With the implied barriers in atomic instructions they must
assume the worst case an use the strongest barrier possible
applied both before and after each atomic instruction.

My inclination would be to do all of the above, and implement
both the non-interruptible and atomic RMW's in the cache controller.
Sorting out the barriers and their effects on various things
like load-store-queue, store buffers, synchronizing with
pending inbound and outbound coherence messages,
looks to me like a far bigger job than the RMW operations.

robf...@gmail.com wrote:
> I have set the CPP aside for now as being overly complex. Unless a really
> complicated AMO is desired, it is easier just to implement indivisible RMW
> cycles at the coherence point. Implementing the RMW cycles bumped up the
> size of my memory controller a lot, about 25%. 21,000 to 26,000 LUTs. A CPP
> would be worse still. It will be a challenge getting the whole project to fit.
> From the core's perspective how things are implemented at the coherence point
> should be irrelevant. It just sends out an opcode to that point. I think I have got
> the idea now. And using the Wishbone bus has some to be desired as it does not
> support CMPXCHG directly. I must build onto it.

If implementation cost is a consideration then LL/SC might be
the way to go. It doesn't require putting an ALU and
sequencing logic into the cache controller, it just requires
pinning the cache line for a period of time while the lock is held.
It requires releasing the lock if an interrupt occurs,
or a timer-counter times out, or when a SC is successful.
LL/SC also gives you all the non-interruptible operations for free.

The performance cost is the line stays pinned slightly longer than
it would with the explicit atomic RMW's, and that may require
shutting off the cache coherence comms queues,
and maybe that affects system wide performance.

The memory barrier functions look the same either way.

Scott Lurndal wrote:
> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> scott@slp53.sl.home (Scott Lurndal) writes:
>>> No, they started with the old ARMv7 mechanism and realized that it
>>> didn't scale to large processor counts in ARMv8 around which high-core
>>> count systems were being designed.
>> Why did it not scale? The only thing that comes to my mind is that
>> it's a contended memory location that several cores want to change at
>> the same time, much of the time).
>
> A big problem was fairness, i.e. avoiding starvation, when a large
> number of cores were accessing the same object.
>
>> Yes, in that case I can see that
>> doing it at a central place and only sending the results to the
>> individual cores can result in much higher throughput (say one change
>> every few ns) than sending the cache lines involved to one of the
>> cores (20ns-80ns on current multi-core CPUs), and letting it make the
>> change there, and then sending it onwards to the next core; and that
>> assumes that the other cores asking for the cache lines do not disturb
>> the chosen one.
>
> Indeed.
>
>> But can such high contention not be avoided by redesigning the
>> software? Admittedly, solving a problem in hardware is often less
>> effort, but it's not clear to me why that should be the case here.
>
> I spent a few weeks at LLNL a bit over a decade ago. One of their
> acceptance tests include spinning on a single spinlock from all
> cores (256 in our system) at the same time. The system we were testing was built
> from AMD instanbul cores with a custom ASIC on hypertransport to
> extend the processor coherency domain to other nodes over infiniband
> (or 10G ethernet, but ethernet switches had double the latency of
> IB switches). In Intel/AMD systems, when cache line contention
> causes an internal cache timer to fire because the cache couldn't
> acquire the line, the core will revert to the system-wide
> bus lock. Which absolutely killed performanace.

This is a well know problem for Test and Test and Set (TTS) spinlocks
under high contention - high rates of cache line ping-pong,
many nodes trying to do a read_exclusive at the same instant
causing timeouts and retries at the coherence protocol level,
floods of messages on the coherence network causing transmission backlogs.

> Removing the
> cache contention by handling atomics at the cache rather than
> acquiring the cache line is a partial solution for this type of
> scaling problem

Moving the atomic operations from the core to the cache controller
should eliminate the window during which a cache line is pinned
and that may help system performance, but does not eliminate the
ping-pongs or lessen the number of messages.

> (Customers aren't generally willing to
> rewrite applications if they don't have to....)

TTS spinlocks are used because they are cheap - 1 DWORD per lock.
The problem is that the TTS spinlock method is too simple and
it should only be used when contention is known to be unlikely.

The solution is a spin-queue which builds a linked list of cache lines
with each waiter spinning on a separate cache line, so no ping-pongs,
no thundering herds fighting for exclusive access to the same DWORD.
Most major OS and many user mode multithreading apps now use such
spin-queues wherever there is high contention for a data structure.
The cost is one cache line per lock, plus one line per contender,
and each lock has a pointer to the list head.
Enqueing a lock request is just an atomic exchange on the list head
which has none to very light contention.

In terms of code changes, its a few hours work replacing SpinlockXxx
functions with SpinqueueXxx functions.

EricP <ThatWouldBeTelling@thevillage.com> writes:
>Scott Lurndal wrote:
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> scott@slp53.sl.home (Scott Lurndal) writes:
>>>> No, they started with the old ARMv7 mechanism and realized that it
>>>> didn't scale to large processor counts in ARMv8 around which high-core
>>>> count systems were being designed.
>>> Why did it not scale? The only thing that comes to my mind is that
>>> it's a contended memory location that several cores want to change at
>>> the same time, much of the time).
>>
>> A big problem was fairness, i.e. avoiding starvation, when a large
>> number of cores were accessing the same object.
>>
>>> Yes, in that case I can see that
>>> doing it at a central place and only sending the results to the
>>> individual cores can result in much higher throughput (say one change
>>> every few ns) than sending the cache lines involved to one of the
>>> cores (20ns-80ns on current multi-core CPUs), and letting it make the
>>> change there, and then sending it onwards to the next core; and that
>>> assumes that the other cores asking for the cache lines do not disturb
>>> the chosen one.
>>
>> Indeed.
>>
>>> But can such high contention not be avoided by redesigning the
>>> software? Admittedly, solving a problem in hardware is often less
>>> effort, but it's not clear to me why that should be the case here.
>>
>> I spent a few weeks at LLNL a bit over a decade ago. One of their
>> acceptance tests include spinning on a single spinlock from all
>> cores (256 in our system) at the same time. The system we were testing was built
>> from AMD instanbul cores with a custom ASIC on hypertransport to
>> extend the processor coherency domain to other nodes over infiniband
>> (or 10G ethernet, but ethernet switches had double the latency of
>> IB switches). In Intel/AMD systems, when cache line contention
>> causes an internal cache timer to fire because the cache couldn't
>> acquire the line, the core will revert to the system-wide
>> bus lock. Which absolutely killed performanace.
>
>This is a well know problem for Test and Test and Set (TTS) spinlocks
>under high contention - high rates of cache line ping-pong,
>many nodes trying to do a read_exclusive at the same instant
>causing timeouts and retries at the coherence protocol level,
>floods of messages on the coherence network causing transmission backlogs.

It's been well known for half a century. By computer scientists.

The engineers and scientists who have written the applications, however,
not so much.

>
>> Removing the
>> cache contention by handling atomics at the cache rather than
>> acquiring the cache line is a partial solution for this type of
>> scaling problem
>
>Moving the atomic operations from the core to the cache controller
>should eliminate the window during which a cache line is pinned
>and that may help system performance, but does not eliminate the
>ping-pongs or lessen the number of messages.

It does eliminate a substantial fraction of line movement between
cores, particularly when replacing LL/SC style primitives.

>
>> (Customers aren't generally willing to
>> rewrite applications if they don't have to....)
>
>TTS spinlocks are used because they are cheap - 1 DWORD per lock.
>The problem is that the TTS spinlock method is too simple and
>it should only be used when contention is known to be unlikely.

Yes, that is also true and rather self-evident.

>
>The solution is a spin-queue which builds a linked list of cache lines
>with each waiter spinning on a separate cache line, so no ping-pongs,
>no thundering herds fighting for exclusive access to the same DWORD.
>Most major OS and many user mode multithreading apps now use such
>spin-queues wherever there is high contention for a data structure.
>The cost is one cache line per lock, plus one line per contender,
>and each lock has a pointer to the list head.
>Enqueing a lock request is just an atomic exchange on the list head
>which has none to very light contention.
>
>In terms of code changes, its a few hours work replacing SpinlockXxx
>functions with SpinqueueXxx functions.

That is likely underestimating the effort of both replacing the
existing synchronization primitives and testing the resulting
codebase.

The folks responsible for those codebases would rather be doing
science and engineering; not rewriting working code.

There is a reason that LLNL tests how systems behave under such
behavior.

On Sunday, January 8, 2023 at 7:14:11 PM UTC+2, Scott Lurndal wrote:
> EricP <ThatWould...@thevillage.com> writes:
> >Scott Lurndal wrote:
> >> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> >>> sc...@slp53.sl.home (Scott Lurndal) writes:
> >>>> No, they started with the old ARMv7 mechanism and realized that it
> >>>> didn't scale to large processor counts in ARMv8 around which high-core
> >>>> count systems were being designed.
> >>> Why did it not scale? The only thing that comes to my mind is that
> >>> it's a contended memory location that several cores want to change at
> >>> the same time, much of the time).
> >>
> >> A big problem was fairness, i.e. avoiding starvation, when a large
> >> number of cores were accessing the same object.
> >>
> >>> Yes, in that case I can see that
> >>> doing it at a central place and only sending the results to the
> >>> individual cores can result in much higher throughput (say one change
> >>> every few ns) than sending the cache lines involved to one of the
> >>> cores (20ns-80ns on current multi-core CPUs), and letting it make the
> >>> change there, and then sending it onwards to the next core; and that
> >>> assumes that the other cores asking for the cache lines do not disturb
> >>> the chosen one.
> >>
> >> Indeed.
> >>
> >>> But can such high contention not be avoided by redesigning the
> >>> software? Admittedly, solving a problem in hardware is often less
> >>> effort, but it's not clear to me why that should be the case here.
> >>
> >> I spent a few weeks at LLNL a bit over a decade ago. One of their
> >> acceptance tests include spinning on a single spinlock from all
> >> cores (256 in our system) at the same time. The system we were testing was built
> >> from AMD instanbul cores with a custom ASIC on hypertransport to
> >> extend the processor coherency domain to other nodes over infiniband
> >> (or 10G ethernet, but ethernet switches had double the latency of
> >> IB switches). In Intel/AMD systems, when cache line contention
> >> causes an internal cache timer to fire because the cache couldn't
> >> acquire the line, the core will revert to the system-wide
> >> bus lock. Which absolutely killed performanace.
> >
> >This is a well know problem for Test and Test and Set (TTS) spinlocks
> >under high contention - high rates of cache line ping-pong,
> >many nodes trying to do a read_exclusive at the same instant
> >causing timeouts and retries at the coherence protocol level,
> >floods of messages on the coherence network causing transmission backlogs.
> It's been well known for half a century. By computer scientists.
>
> The engineers and scientists who have written the applications, however,
> not so much.
> >
> >> Removing the
> >> cache contention by handling atomics at the cache rather than
> >> acquiring the cache line is a partial solution for this type of
> >> scaling problem
> >
> >Moving the atomic operations from the core to the cache controller
> >should eliminate the window during which a cache line is pinned
> >and that may help system performance, but does not eliminate the
> >ping-pongs or lessen the number of messages.
> It does eliminate a substantial fraction of line movement between
> cores, particularly when replacing LL/SC style primitives.
> >
> >> (Customers aren't generally willing to
> >> rewrite applications if they don't have to....)
> >
> >TTS spinlocks are used because they are cheap - 1 DWORD per lock.
> >The problem is that the TTS spinlock method is too simple and
> >it should only be used when contention is known to be unlikely.
> Yes, that is also true and rather self-evident.
> >
> >The solution is a spin-queue which builds a linked list of cache lines
> >with each waiter spinning on a separate cache line, so no ping-pongs,
> >no thundering herds fighting for exclusive access to the same DWORD.
> >Most major OS and many user mode multithreading apps now use such
> >spin-queues wherever there is high contention for a data structure.
> >The cost is one cache line per lock, plus one line per contender,
> >and each lock has a pointer to the list head.
> >Enqueing a lock request is just an atomic exchange on the list head
> >which has none to very light contention.
> >
> >In terms of code changes, its a few hours work replacing SpinlockXxx
> >functions with SpinqueueXxx functions.
> That is likely underestimating the effort of both replacing the
> existing synchronization primitives and testing the resulting
> codebase.
>
> The folks responsible for those codebases would rather be doing
> science and engineering; not rewriting working code.
>

So, your solution improves performance from 0.1% of what it should be
to 1% of what it should be.
Marketing can spin it as 10x improvement, but engineers should understand
that it is improvement by 0.9%.

> There is a reason that LLNL tests how systems behave under such
> behavior.

Sure there is a reason. But not a good reason.

Scott Lurndal wrote:
> EricP <ThatWouldBeTelling@thevillage.com> writes:
>> Scott Lurndal wrote:
>>> I spent a few weeks at LLNL a bit over a decade ago. One of their
>>> acceptance tests include spinning on a single spinlock from all
>>> cores (256 in our system) at the same time. The system we were testing was built
>>> from AMD instanbul cores with a custom ASIC on hypertransport to
>>> extend the processor coherency domain to other nodes over infiniband
>>> (or 10G ethernet, but ethernet switches had double the latency of
>>> IB switches). In Intel/AMD systems, when cache line contention
>>> causes an internal cache timer to fire because the cache couldn't
>>> acquire the line, the core will revert to the system-wide
>>> bus lock. Which absolutely killed performanace.
>
>> The solution is a spin-queue which builds a linked list of cache lines
>> with each waiter spinning on a separate cache line, so no ping-pongs,
>> no thundering herds fighting for exclusive access to the same DWORD.
>> Most major OS and many user mode multithreading apps now use such
>> spin-queues wherever there is high contention for a data structure.
>> The cost is one cache line per lock, plus one line per contender,
>> and each lock has a pointer to the list head.
>> Enqueing a lock request is just an atomic exchange on the list head
>> which has none to very light contention.
>>
>> In terms of code changes, its a few hours work replacing SpinlockXxx
>> functions with SpinqueueXxx functions.
>
> That is likely underestimating the effort of both replacing the
> existing synchronization primitives and testing the resulting
> codebase.
>
> The folks responsible for those codebases would rather be doing
> science and engineering; not rewriting working code.
>
> There is a reason that LLNL tests how systems behave under such
> behavior.

Replacing with spin queues would likely completely change the behavior
of such an application by eliminating overhead and changing the order
threads are released. Things happen quicker and in a different order.

And that could expose latent bugs, maybe an argument alias that went
unnoticed. Before the app had a chance to finish one calculation before
the next started, but now the two are overlapped so the alias bites you.

So yes it would have to be completely re-tested and re-tuned.