[gambit-list] Memory ordering considerations in Gambit SMP?

Adam adam.mlmb at gmail.com
Sat Nov 18 22:57:55 EST 2017


My vote:

Yes I vote for lowlevel also.


Gambit *can* not abstract away the way the hardware does memory alignment
and ordering, so your question ("Should Gambit .. abstract[..], or ..
programmer has to deal with such issues") is a bit ambiguous.


In order to provide a competent vote here, I read through the documentation
of *all* of the mainstream CPU architectures (AMD64, Sparc, ARM, MIPS, IBM
Power), and what I find is that there is indeed a universal way among all
these architectures, to do data accesses inexpensively and atomically
locally on a CPU core and between CPU cores, and that is by doing *all* your
loads and stores naturally aligned, so that is, byte accesses on any
address, word (16bit) accesses on memory addresses that are a multiple of
2, dword (32bit) on 4 byte multiples, and qword (64bit) accesses on 8 byte
multiples [1].

As long as that convention is followed, then a value will always be loaded
atomically (on any receiving core, following a store made on any core,) as
in there will be no data destruction where your load retrieves a
half-updated value.

The last consideration then is the memory ordering, and here, the strongly
ordered architectures (AMD64 and Sparc) require no additional
considerations, while the weakly ordered architectures (ARM, MIPS, IBM
Power) need a barrier operation to force uncommitted stores to be flushed.


Therefore, an overall strategy for all of Gambit for functioning coherently
in multicore (SMP) use is:

   - Gambit locates all variable and other value slots on the heap to
   aligned memory addresses only.

   This way, the passing of object references and unallocated objects
   between CPU cores will always happen gracefully as all Gambit accesses of
   such data will be in a way that is automatically atomic (as in
   corruption-proof) between CPU cores.

   - Gambit provides a memory barrier primitive for weakly ordered CPU
   architectures only.

   It could be called |force-order!|.

   It's a NOOP on strongly ordered CPU architectures.



Next, with respect to Gambit's design, the way a user relates to Gambit and
interfaces it, I presume will work like this:

   - Gambit internal level:

   Gambit internally is self-contained and does not need any particular
   intervention from the user to work on a given CPU architecture (for
   atomicity and ordering matters to work out, so that is, Gambit internally
   makes memory barriers as needed).

   - Gambit runtime - with - user interface level:

   The parts of Gambit's exports that relate to multiprocessing, so that
   would be message passing, IO, threading, locking (e.g.
   read/write-u8vector/u8 etc., thread-send/thread-receive,
   mutex-lock!/mutex-unlock! , thread-start!/thread-terminate!), should be
   multicore-proof by default. (Higher-speed non-multicore versions may be
   available.)

   E.g.,

   (define m (make-mutex)) (mutex-lock! m)
   (define t (thread-start! (make-thread (lambda () (display
   (thread-receive)) (mutex-unlock! m))))) (thread-send t '(my struct))

   is safe out of the box on any architecture - Gambit takes care of all
   atomicity, ordering, including memory barriers (on weakly ordered
   architectures).

   Note here that thread-send must imply a memory barrier on a weakly
   ordered architectures, for the case that it runs on another CPU core.

   - User level:

   Obviously for execution within the local CPU core, no particular
   atomicity or ordering considerations are needed.

   For access that does or may span CPU cores, the user must sugar the code
   properly with |force-order!| calls properly at the points where values have
   been mutated or new values have been allocated, and another CPU core will
   access those values.



The "crash profile" we get is that attempting to access on core B an object
that was newly allocated on core A, may crash on a weakly ordered
architecture, if the code was not properly sugared with |force-order!|:s.

A partially remedy exists in the form that for a structure that already has
been flushed to core B, if a mutation is made from core A but is not
flushed to core B, then any retrievals on core B will get the old value
rather than a broken value, and so at least Gambit will not crash in such
circumstances.

Example: If core A does (define v (vector #f)) (force-order!) ...
(vector-set! v 0 #t), then any accesses from core B to the slot in |v|
after the first |force-order!|, will be crash-proof for unallocated values,
as in (vector-ref v 0) on core B will always retrieve a valid value
(presuming that it is unallocated e.g. fixnum, boolean, character, a
previously allocated symbol, etc.), the only risk would be that you might
get an older value.

No such risk of crashes applies on strongly ordered architectures.


Please note that we use the atomicity guarantee that we get on all
architectures for accesses that are naturally aligned, as a fundament for
the management of object references (as these are ordinary 64/32bit values);

The atomicity guarantees may not necessarily apply for floating point
values on weakly ordered architectures, so on those architectures any use
of floating point values may need additional considerations, and which
would be subject to another, separate discussion here.


One thought that comes to my mind here is, must the C compiler be given any
particular instructions or type definitions, to deliver for this SMP
usecase (as in, honor the atomicity and ordering)?


Feedback?

Adam

[1] Intel-manufactured AMD64 CPU:s provide atomicity within 64 byte
multiple memory address intervals and AMD-manufactured AMD64 CPU:s provide
atomicity within 8 byte multiples. For there to be compatibility with
AMD-manufactured AMD64 CPU:s, we can as well just omit to use the more
extensive atomicity guarantee of Intel manufactured CPU:s, and stick to the
safe crossplatform principle described above.

Also AMD64, in particular Intel-manufactured CPU:s, stick out by making
unaligned accesses cheaply. I think Gambit has no utility in exploiting the
ability for cheap unaligned access for heap-based structures, so again we
have no utility in exploiting this particular architecture-specific feature.

A Gambit OS thread's local execution within the C stack may obviously
involve various C compiler optimizations which may use any
architecture-specific features and optimizations that could involve
unaligned accesses, however for any data accesses between cores, at least
made by user code, heap based values will be used only (and references to
heap based values will be passed only), and those will not be touched by
compiler optimization tricks and so the atomicity and ordering described
above will indeed apply for those and so the model is intact.

2017-11-14 15:47 GMT+08:00 Dimitris Vyzovitis <vyzo at hackzen.org>:

> low level language pls.
>
> -- vyzo
>
> On Tue, Nov 14, 2017 at 4:08 AM, Marc Feeley <feeley at iro.umontreal.ca>
> wrote:
>
>> I don’t know what the correct semantics is.  Should Gambit Scheme be
>> considered a high-level language where such details are abstracted, or a
>> low-level language where the programmer has to deal with such issues?
>> Please cast your vote now!
>>
>> Marc
>>
>>
>>
>> > On Nov 13, 2017, at 11:00 AM, Adam <adam.mlmb at gmail.com> wrote:
>> >
>> > Say two Gambit threads that execute concurrently in two different OS
>> threads, are communicating by mutating a structure. E.g.
>> >
>> > Global:
>> >
>> > (define itc-state:set? #f)
>> > (define itc-state:message #f)
>> >
>> >
>> > Thread 1 does:
>> > (set! itc-state:message ..something..)
>> > (set! itc-state:set? #t)
>> >
>> >
>> > And thread 2 polls:
>> > (do loop ()
>> >
>> > (if itc-state:set? (act-on! itc-state:message))
>> >
>> > (loop))
>> >
>> >
>> > Is any direct polling of structures between OS threads illegal in SMP
>> Gambit, or what is the intended way for this to be coherent?
>> >
>> >
>> > (If this was ordinary C code, on a weakly ordered architecture, the
>> worry would be that the |itc-state:set?| update would reach the other CPU
>> core before the |itc-state:message| update reached it and that the program
>> hence would enter into an undefined state - and for this reason programs do
>> a write barrier between.)
>> >
>> >
>> >
>> >
>> >
>> > 2017-11-13 21:44 GMT+08:00 Marc Feeley <feeley at iro.umontreal.ca>:
>> >
>> > > On Nov 11, 2017, at 5:13 PM, Adam <adam.mlmb at gmail.com> wrote:
>> > >
>> > > Dear Marc,
>> > >
>> > > Are there any constraints on what underlying hardware platform SMP
>> Gambit can work on, e.g. architectures with strong memory ordering (AMD64)
>> versus architectures with weak memory ordering (ARM64)?
>> >
>> > No foreseen constraints.
>> >
>> > >
>> > > Does Gambit export any memory barrier primitive?
>> >
>> > No
>> >
>> > >
>> > > Do any particular Gambit primitives imply a memory barrier, so these
>> are abstracted away from the user?
>> >
>> > mutex-lock! and there might be others…
>> >
>> > >
>> > > E.g. (thread-send! t (list 1 2 3)) would imply a memory barrier on
>> weakly ordered systems, if t is being executed on another OS thread, so
>> that when the message is received on the other side, Gambit has
>> automatically ensured that the structure is actually accessible on the
>> receiving end?
>> >
>> > This should work.  If it doesn’t please submit an issue report.
>> >
>> > Marc
>> >
>> > >
>> > > (https://en.wikipedia.org/wiki/Memory_ordering#Runtime_memor
>> y_ordering)
>> > >
>> > > Will appreciate a lot to understand how to manage this.
>> > >
>> > > Thanks!
>> > > Adam
>> >
>> >
>>
>> _______________________________________________
>> Gambit-list mailing list
>> Gambit-list at iro.umontreal.ca
>> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20171119/73bfd163/attachment.htm>


More information about the Gambit-list mailing list