Re: Non-uniform address spaces

[Michael Eager <eager@eagercon.com>]

Jim Blandy wrote:
> Michael Eager <eager@eagercon.com> writes:
>> This is the problem:  the pervasive assumption in GDB is that a CORE_ADDR
>> is a simple, linear value.   In a NUMA architecture, this is not true.
>> Actual pointers on the hardware may be simple addresses, but they may be
>> in arbitrary address spaces.  The translation to a target address is OK,
>> but the operations on CORE_ADDR are incorrect.
> 
> Can you show me a specific example?

An address on a multiprocessor system can have the following structure:
   <processor, thread, offset>

(Thread may or may not be a real thread of execution -- it represents an
entity that has a certain memory allocation.)

An array can occupy an extent which is distributed across several different
threads or processors.  For example, an array may be split into four
pieces, with each piece allocated to four different processors.  Indexing
an array involves determining which <processor,thread> a subscript is
in, then computing the correct offset within that memory.

> (I think using a 128-bit CORE_ADDR is probably the way to go.)
> 
>> Operations as simple as array indexing may require a computation that
>> is more complex than a simple multiplication.  An array may be split
>> between multiple address spaces.  The computation may not be complex,
>> but it is not as simple as a multiply and addition.
> 
> This, I'd really like to learn more about.

For an example, the SPEs in a Cell processors could be configured
to distribute pieces of an array over different SPEs.

> How do you declare such an array?  How do you index it?  What code is
> generated for an array access?  How does it relate to C's rules for
> pointer arithmetic?

In UPC (a parallel extension to C) there is a new attribute "shared"
which says that data is (potentially) distributed across multiple processors.

In UPC, pointer arithmetic works exactly the same as in C: you can
compare pointers, subtract them to get a difference, and add integers.
The compiler generates code which does the correct computation.

>>> I think you'll find that the operations on CORE_ADDR itself will all
>>> be harmless.  GDB shouldn't be walking off the end of an object
>>> anyway, so if objects don't overlap address space boundaries, then GDB
>>> won't either.
>> The assumption that objects don't cross address space boundaries
>> is not valid.  Multiprocessor systems split data across multiple
>> processors, each of which has a separate data space.
> 
> There I'm using 'object' in the sense the C standard uses it.  If you
> can answer my questions above, I think I'll understand this better.

The C standard doesn't require objects to be contiguous or to be
stored entirely in a single memory space.  Objects can be partially
in memory and partially in registers, for example.  Or an array
can be distributed across multiple address ranges.  (The C standard
[working from an old draft] says "region of data storage", but it
doesn't expand on this definition.)

The only relevant requirement in the C standard is that when you
increment a pointer in an array that the result points to the next
element.  Whether that's a simple addition of a constant or something
more involved is not part of the standard.

-- 
Michael Eager	 eager@eagercon.com
1960 Park Blvd., Palo Alto, CA 94306  650-325-8077