Global Atomic Operations on Multi-word Data

[LouisJenkinsCS]

@e-kayrakli
@mppf

This is of importance to both the project and to Chapel as a whole (or so I believe).
I believe that this early prototype of the Global Descriptor Table (GDT), formerly
referred to as GlobalAtomicObject, demonstrates the potential power of global atomics.
There are a few key things here which were misconceptions that I've had and been told
since the beginning...

Communication Is NOT Bad

Communication, even if it is per-operation, is not bad, but it's not good either.
The true bottleneck is contention. I've tested time and time again, and each time
an algorithm containing some contention-causing operation which may cause an unbounded number
of failed operation resulting in an unbounded number of communications, has failed horribly
in terms of performance. For example, operations like this is bad...

while true {
  var _x = x.read();
  var _y = y.read();
  if _x < _y && _x.compareExchangeStrong(_x, _x + 1) {
    break;
  }
}

Will cause an unbounded number of communications. Reading x and y is relatively
expensive, and since the CAS operation not only causes remote contention, but the fact
that both x and y need to be read again, causes performance to drop.

Now, algorithms which are guaranteed to succeed are guaranteed to scale very well;
that is, only wait-free algorithms can see scalability. Code that uses
fetchAdd and exchange work wonderfully, which gives me hope that a global data
structure with very loose guarantees are possible and useful.

Global Descriptor Table

Next, is the new and novel idea of the GDT, the Global Descriptor Table. A 64-bit word
is used over a 128-bit wide pointer allowing us to take advantage of the benefits of
network atomics. In essence, we encode the locale number in the upper 32 bits and
the actual index in the lower 32 bits. Currently, an array is used, but in reality (perhaps
with runtime support if not already available) its possible that a descriptor can be directly
used like a normal pointer. Currently there is a large amount of overhead in needing
to keep a bitmap of usable memory and it cannot be resized without needing to synchronize
all accesses to it (as Chapel domains and arrays cannot be resized in a lock-free way).

Currently, it has been tested with simple exchange operations on class instances
remotely across all locales, versus needing to acquire a sync variable to do the same.
As stated above, a compareExchangeStrong kills performance, but that has nothing to do
with the GDT but with network atomic contention, so its kept simple. It works and it
scales. The below graph shows time to complete the same number of operations
(100,000 in this case). It shows the overall runtime of the average of 4 trials
(discarding the first warm-up), and that while sync will increase in an a near
exponential growth, GDT remains linear.

Now, to get a better look at it, here are the same results in Operations per Second.

Implications

I believe this is some very valuable information, which is why I include Michael as well.
Not only is the implementation very immature (there are so many optimizations that
can be made, that there's no saying how much more this can scale), it also surpasses
the only way to perform atomics on global class instances. As well, this opens some
very unconventional means of concurrency, the first being the DSMLock (WIP) that is
based on the DSM-Synch (Distributed Shared Memory Combined Synchronization)
in the publication that had CC-Synch (Cache-Coherent Combined Synchronization). As I can confirm
that this scales, I can possibly even make DSMLock scale in such a way that global
lock-based algorithms can scale (not just wait-free). Extremely exciting!

Edit:

If this is extended on for the runtime, I can imagine having the entire global address space chunked up into a 4GB (2^32) zones, with 2^8 zones on 2^24 locales. With 256 of 4GB zones, that's 1TB address space per locale, with 16M+ locales.

[mppf]

Re "Communication is not bad", I think your example was interesting but I'm not sure I'd describe it that way. I mean, you're saying that an unbounded amount of communication under contention kills performance. And it's probably worse to have unbounded number of compare-exchange when communication is involved than it is locally, because the latency on the operation is higher (so it might be more likely another operation changes the value).

My main question here is - what are these bit-maps of all memory you mentioned? Nothing about the descriptor table idea implies to me that we need bitmaps... but perhaps I have not thought through some issue.

[LouisJenkinsCS]

My main question here is - what are these bit-maps of all memory you mentioned? Nothing about the descriptor table idea implies to me that we need bitmaps... but perhaps I have not thought through some issue.

The bitmaps are mainly to keep track of which descriptors are in use and which are not. The descriptors themselves do not refer to the actual address space, but some index into an array on some locale. The bitmap is to provide a lower (but essential) overhead to keeping track of which indices can be used/reused.

Bitmaps may not be needed if instead of Chapel arrays we use just raw pointers to memory like c_malloc (but this is a prototype after all). Currently the user must allocate the data first using new and then 'register' it (I.E: Adding to array) which will return the descriptor (I.E: Index the data was added to). Ideally, allocating large chunks of memory and implementing a basic memory manager would provide much better performance (but takes more time to implement).

[LouisJenkinsCS]

Code in question:

GDT and Bitmap.

Note that they are very early (but promising) implementations.

[mppf]

I would expect a pattern like this:

class C { ... }
proc test() {
   var a = new C(1);
   var b = new C(2);
   var x: atomic C;
   var result:bool;
   x.write(a);
   result = x.compareExchange(a, b);
   assert(result);
   assert(x.read() == b);
   delete a;
   delete b;
}

I would imagine that would mean you would need to perform this register operation on the first atomic operation for that class.

[LouisJenkinsCS]

Truth be told, under more ideal cases it would be better if a and b could be created by some other object and used as such...

class C { ... }
var gdt = new GDT(C);
proc test() {
   // Maybe have parameters passed be used to reflectively call the constructor of C?
   var (idxA, a) = gdt.create(1);
   var (idxB, b) = gdt.create(2);
   var x: atomic uint;
   var result:bool;
   x.write(idxA);
   result = x.compareExchange(idxA, idxB);
   assert(result);
   assert(gdt.read(idxB) == b);
}

Currently its ugly, but either the runtime or compiler will need to keep track of the actual index of the object or the user has to. I'm not sure if you can hash the actual pointer address to an index, but maybe something similar can be done to remove the need to use the index and support just using the raw object. I can experiment with this as well.

[mppf]

Right, it's clear that would be more convenient to implement, but I'm not so sure I'd consider it a full solution to the problem. After all, we are trying to make a productive parallel language, so we want to minimize concerns for our users.

Anyway, as far is implementing goes, yeah, keep going & experiment with what it would take to get my example pattern to work. Thanks!

[LouisJenkinsCS]

@mppf @e-kayrakli

Here is a document detailing how I plan to implement global atomics in a fashion that can provide reasonable semantics (I.E: No need to carry descriptors, wide-pointer compression strategy, global atomics, etc.)

I wish to start on it this weekend (as after I need to satisfy Engin's requirements for the Queue) so by then I should know if it does work or not. As well, the FCHLock (Flat Combining Hierarchical Lock) determines if I can make a global priority queue or not with reasonable performance, which also can be affected by this. If any advice or feedback could be given on it by Friday night I'd appreciate it.

[LouisJenkinsCS]

Also as well, @mppf I believe it was mentioned before that Linux only allows a 47-bit virtual address space, but I can't 100% verify that. I mean, if that is the case for a work-around I can always just shave off the top 17 bits for locale id (which only allows 131K locales, but it could be an even more temporary but immediate solution, taking literally next to no effort to do). I just can't make assumptions without knowing how Chapel handles things currently. gbt1 mentioned that network tops at 128k, but I can see it increasing easily within a few years (of which my solution won't work for). However, if both are 'fine for now' solutions, then its sufficient to just have top 17 bits be locale id, lower 47 bits be virtual address.

Edit:

Turns out, as seen here that my solution is rather overly complicated. "Most operating systems and applications will not need such a large address space for the foreseeable future, so implementing such wide virtual addresses would simply increase the complexity and cost of address translation with no real benefit." Absolutely crazy... so I can just actually compress it as I see fit. Or rather, my solution isn't overly complicated, but one that is resistant to change.

[mppf]

I think it's important that we have a strategy for my above Chapel code example to work, even if it's not the first thing we implement.

I don't understand why you need a "Zone" strategy at all. Let's back up a bit and talk through the problems that really need to be solved here.

I think what I was imagining was:
a) wide pointer compression into 64-bits
b) a fall-back strategy that works differently (e.g. by referring to an allocated descriptor index in a table of descriptors).

See https://github.com/chapel-lang/chapel/blob/master/runtime/include/chpl-wide-ptr-fns.h for some existing code that does wide pointer compression, but that wouldn't work on very large systems. (I.e. I'm asserting (a) is already implemented and you could steal/reuse that implementation. ).

Anyway, for (b), could we propagate information about a mapping from index to node in a dynamic way, only when needed? For example, here is an "obvious" strategy for (b) - that is, a straw-man:

• have a global array of objects
• creating a descriptor simply adds a class instance pointer to a free slot in the array & returns its index
• :atomic obj can either store a compressed pointer or a descriptor (so you'd use the top or bottom bit to distinguish between these two. Note that the bottom bit can be "stolen" from an address because all class instances are allocated & so will be aligned - usually 16 byte aligned in practice).

For terminology, let's call the thing we actually store in an atomic class variable an "atomic instance descriptor".

How would that work with my example?

class C { ... }
proc test() {
   var a = new C(1);  // works as it does now
   var b = new C(2); // as it does now
   var x: atomic C; // atomic C is 64 bits in a format we are inventing: "atomic instance descriptor".
   var result:bool;
   x.write(a);
   result = x.compareExchange(a, b);
   // compareExchange will:
   //  1) Convert a and b to atomic instance descriptors (possibly by compression,
   //      possibly by searching in or updating some data structures)
   //  2) Perform the 64-bit atomic compareExchange operation on the descriptors
   assert(result);
   assert(x.read() == b);
   // read() will:
   // 1) atomically read a 64-bit atomic instance descriptor
   // 2) unpack the atomic instance descriptor into a 128-bit wide pointer
   //      (possibly by reading it directly, possibly with some data structure).
   delete a;
   // delete a could remove the atomic instance descriptor for a from some data structure
   delete b;
   // delete b could remove the atomic instance descriptor for a from some data structure
}

So, for the example to be efficient, we need to have reasonable ways to do:
i) Go from a wide address of a class instance to an atomic instance descriptor
ii) Go from a atomic instance descriptor to an address

We could conceivably store the atomic instance descriptor in the class instance,
once it is computed. We're making the compiler/language after all, so we could
add a 64-bit element to all class instances. That might solve (i). Or maybe there is a better solution.

For (ii), we could literally use a global array as I was describing above. It could even be block distributed... Or, maybe the best solution here uses a limited number of atomic descriptors per locale. So that the format would be 32-bits of locale number/node id, and then a 32-bit offset into that locale's individual table. That's not really that different from using a Block distributed array, but it might add some flexibility. In particular, you could imagine using a skip list (or something) instead of an array, to make inserting/freeing more efficient.

Or, what if these arrays were per-pthread, so that there isn't even any locking overhead in managing the data structures? Whatever pthread is doing (i) would update its table.

Is it a significant limitation to only allow 2^32 atomic instance descriptors at a given time? I'm not sure.

• A big machine could allocate that many class instances. An allocated class instance is going to be 32 bytes at a minimum, in practice, as far as I understand. (16 byte aligned but storing >= 1 byte). So that's 128 GiB of storage for the classes themselves, which is a lot, but might even be possible on 1 node.
• One might investigate how many atomic instance descriptors would be used in a sample application using atomic class instances.
• Or, we start with 2^32 max and expect to extend that in the future if the limit becomes a problem.

Related ideas:

• (i) and (ii) also reminds me of some work I did on the cache for remote data. Basically the cache is a mapping from addresses to values.
• The Zones idea reminds me a little bit of work gbt is doing on dynamic memory registration.

Even though these are related, I don't think it's a good idea to tie this effort to those other components, unless we really really need to.

[LouisJenkinsCS]

I don't understand why you need a "Zone" strategy at all.

I believe I should reiterate on the point of Zones. Zones makes an assumption on
3 things to compress the most significant 32-bits of the addr portion of
a wide pointer...

1. The Virtual Memory Manager will monotonically allocate virtual addresses and are not random, decreasing the amount of unique most significant 32-bits.
2. Chapel's memory manager reuses memory, further reducing the unique most significant 32-bits.
3. The number of unique most significant 32-bits do not exceed the amount of bits used to keep track of it.

Assuming all locales cache each other's Zone base offsets and their respective mappings, then we can easily do this without necessary intervention from the runtime or compiler. Note again, this was from the perspective of using GDT as a module, but in your example it can still work, and if anything it can do so in a much better way. Assuming instead of just having the atomic C be an 'atomic instance descriptor', have it just be a GDT.

To skip to the good part... We'll assume that a.addr and a.localeId refer to the address
and localeId respectively...

  x.write(a);
  // write will:
  //  1) Descriptor becomes (a.localeId << 40) | zoneId(a) << 32 | a.addr & 0xFFFFFFFF
  //  2) This is written to some atomic uint field.
  // Note: zoneId performs the 'magic' in terms of compression... that's certainly possible but a WIP
  result = x.compareExchange(a, b);
  // compareExchange will:
  //  1) Convert a and b to atomic instance descriptors (possibly by compression,
  //      possibly by searching in or updating some data structures)
  //  2) Perform the 64-bit atomic compareExchange operation on the descriptors
  assert(result);
  assert(x.read() == b);
  // read() will:
  // 1) atomically read a 64-bit atomic instance descriptor
  // 2) Unpacks by doing the following:
  //      var descr = ...;
  //      var localeId = descr >> 40;
  //      var addr = (zone((descr >> 32) & 0xFF)) | descr & 0xFFFFFFFF;
  //      return ...; /* Handle conversion back to wide pointer with localeId and addr */
  //    Note: zone performs the 'magic' in terms of decompression... while it is a WIP, what it does
  //          is return a 64-bit base that the offset (lower 32 bits) is added to.

The above again makes relatively dangerous assumptions: Only 256 unique most significant 32 bits
are used. Truth be told, it could be potentially improved by changing how many bits are
kept the addr part and how many can be used for zoneId. Just needed to make this case apparent
before its dismissed, as I still think it could work (as you said, the language can be changed
to provide certain guarantees)

a) wide pointer compression into 64-bits

Its good to hear that its been done before, definitely makes my job easier and also makes more sense
that someone else on the development team thought of it first.

b) a fall-back strategy that works differently (e.g. by referring to an allocated descriptor index in a table of descriptors).

creating a descriptor simply adds a class instance pointer to a free slot in the array & returns its index

This is definitely viable if we do what you said...

We could conceivable store the atomic instance descriptor in the class instance,
once it is computed.

This would be acceptable. If we had each type keep track of it's descriptor, and each type have a specific GDT it would also work out well. This allows the current approach of keeping a bitmap, as well as allow me to incrementally grow the GDT by allocating and chaining another array (twice the original size) and to allow reads of currently existing descriptors to be free of synchronization. This may be the easiest way as well as an acceptable proof-of-concept/prototype.

using a skip list (or something) instead of an array, to make inserting/freeing more efficient.

Makes any remote operation (such as a read on another node) to become too expensive, as they too need to traverse the nodes in the list to find it.

Or, what if these arrays were per-pthread, so that there isn't even any locking overhead in managing the data structures?

That's an interesting one... would this also allow certain NUMA-friendly/aware optimizations? Perhaps you could just have it be one for each NUMA node if its that the case. However, having one per pthread, especially if its hyperthreaded and has tons of processors per node and tons of nodes, then I can forsee it being an issue. Having too many GDT structures is a huge space-overhead, but per NUMA-node should be okay since each has their own memory anyway, right?

[mppf]

Assuming instead of just having the atomic C be an 'atomic instance descriptor', have it just be a GDT.

I can't really make sense of that one...

using a skip list (or something) instead of an array, to make inserting/freeing more efficient.

Makes any remote operation (such as a read on another node) to become too expensive, as they too need to traverse the nodes in the list to find it.

Which operations need to access this data structure, and how do they access it?
myAtomicC.read() goes from index to class instance wide pointer. That basically just amounts to accessing the i'th element of the array/whatever. Different data structures we could choose will represent different tradeoffs between the speed of the various operations.

I don't object to the zone idea exactly, I just think it needs to fit into the framework I was describing & should be evaluated among some of these other ideas.

[LouisJenkinsCS]

Assuming instead of just having the atomic C be an 'atomic instance descriptor', have it just be a GDT.

I can't really make sense of that one...

That's my fault, I mean that atomic C becomes some other object that keeps track of both the GDT (Global Descriptor Table/Global Array of class instances) and the current descriptor set.

That basically just amounts to accessing the i'th element of the array/whatever.

Now that's another thing that's my fault. Truthfully, I've never implemented a skip list before so when I thought 'list' I thought 'linked list', not that it could be array based. I rescind what I said, a skip list seems to be the ticket then.

I don't object to the zone idea exactly, I just think it needs to fit into the framework I was describing & should be evaluated among some of these other ideas.

Gotcha, the thing is when it comes to the runtime or compiler I have no idea what is and isn't possible. As well, I've never developed applications for HPC clusters (and this is my first time delving into distributed computing) so I don't have any input to give on whether or not something is enough or what is expected of a sample user program. However to give what little input I can give now...

Or, we start with 2^32 max and expect to extend that in the future if the limit becomes a problem.

This is one thing I can agree with. I honestly can't say whether or not its good enough even in the present, but that's all I can assume.

A big machine could allocate that many class instances. An allocated class instance is going to be 32 bytes at a minimum, in practice, as far as I understand. (16 byte aligned but storing >= 1 byte). So that's 128 GiB of storage for the classes themselves, which is a lot, but might even be possible on 1 node.

I honestly don't know, but my opinion on it would be that if a node exceeds what is set as the maximum threshold, it should just be a runtime error, and that the user should try another work-around. Of course, a fallback for this could be to just use the hwlock solution if the user passes a certain flag, --atomics=hwlock or something? Again, I'm not even sure what the standard way of handling this in Chapel is.

One might investigate how many atomic instance descriptors would be used in a sample application using atomic class instances.

This could be doable for my project by just using it in the queue. If a data structure can't exceed that limit, then I doubt anything else can.

[LouisJenkinsCS]

As well, to reiterate, the best thing I can potentially do is to implement it as an actual module, and then analyze how it can be integrated into the language itself. Currently a way to hash pointers to actual indexes are needed, and the only way to prove a solution works currently is to build an early prototype for it (at least IMO). The solution I agree with is having fields in class instances for it's descriptor unique to an atomic variable (definitely most straight forward). Its impossible from a module, but the 'zone' one might work. At least after the module is established/developed, it should make it 10x easier to add to the language itself and/or make other modifications to it.

[mppf]

Right, but when you're doing such a prototype implementation, it's important to know what a plausible API for the compiler to use will be.

[LouisJenkinsCS]

I can think of an adaptive 4-phase strategy...

NumLocales ≤ 2^17

Normal Compression of Wide Pointers (17 bits for locale, 47 Bits for offset, based on assumption that only 47 bits are ever used), which allows 131K locales and the entire usable address space. This should be sufficient and does not cause any performance loss whatsoever as barely any translation is needed. Note that I don't leave a bit for marking/tagging, but one can be added if you need to pack it into a 64-bit word, then it would change the condition to NumLocales ≤ 2^16.

NumLocales < 2^32

We use the Zone compression strategy to keep track of things like this. The more nodes you have, the less bits you have for Zone (and if you exceed the zone, then we can adapt into the third phase). In this case, if you have exactly 2^18 NumLocales, then you can reserve the rest for zones, meaning its more likely that you can continue using this strategy. As mentioned before, Zones just map the most significant 32 bits of the address to a zone id as they are encountered, which only has slight minor performance losses for caching another locale's zone mappings.

NumLocales = 2^32 or ZoneId bits exceeded...

We use the global descriptor table strategy. Any allocations that exceed the zone, will be instead added here. There is a significant penalty in terms of managing everything, but what else can you do?

NumLocales > 2^32

Just fall back to using a sync variable or some other lock. No amount of compression will help in that case.

Would you agree to something like this?

Edit:

Updated a 4th phase