3 ms·
Yet another article discussing atomics without discussing the memory model or memory fences. Atomics are the easy part to understand. Memory fences and memory-
by dragontamer 7y ago
Yet another article discussing atomics without discussing the memory model or memory fences.
Atomics are the easy part to understand. Memory fences and memory-ordering is the hard part that needs far more discussion. If you use atomics with the wrong memory fence, everything will break.
Memory fences are necessary to make the compiler, CPU, and caches put the data into main-memory in the correct order.
----------
Do NOT write Atomics unless you understand fences. It is absolutely essential, even on x86, to put memory fences in the correct spot. Even though x86 automatically has acquire/release consistency... the compiler may move your data ordering to the wrong location. Even with "volatile" semantics, your data may be committed to memory in the wrong order.
Fredor Pikus has an amusing example where you can have a properly coded lock but the compiler (may) mess you up: https://youtu.be/lVBvHbJsg5Y?t=811 https://youtu.be/lVBvHbJsg5Y?t=811
----------
EDIT: if you use locks (spinlocks, mutex, condition variables, etc. etc.), the author of the library would have put memory fences in the correct place for you. Only if you use synchronization "manually" (and... you probably are doing that if you are writing atomics), do you have to think about memory fences.
- rrss 7y ago> Topics like sequential consistency and memory barriers are critical pieces of the puzzle and can't be overlooked if you want to get the best out of your lock-free algorithms. I will cover them all in the next episode. Not every article has to be an exhaustive description of everything you need to know. Anywho, sequential consistency is the default for C++11 and C11 atomics, so you pretty much can use them without a complete understanding of memory consistency models.
- dragontamer 7y agoAh, you're right. They call them "barriers" instead of "fences", so I didn't pick up on that paragraph. Still, C11 and C++ atomics aren't widely implemented yet in the GPU world. OpenCL 1.2 doesn't have them (and OpenCL 2.0 is not commonly implemented), CUDA doesn't have them yet, AMD ROCm doesn't have them yet. And anyone with older compilers will probably be working with fence intrinsics, instead of "innate" barriers per atomic instruction.
- deleted 7y ago[deleted]
- stcredzero 7y agoOnly if you use synchronization "manually" (and... you probably are doing that if you are writing atomics), do you have to think about memory fences. I was thinking about adding atomic pointer references to a partially persistent (1) AABB tree, then allowing multiple actors in multiple threads each implementing a gameloop to query the AABB tree. Do I need to think about memory fences in that application? I've also been thinking about implementing the above system without atomic pointers. Instead, the system would have an update phase where all writes to the AABB tree happen at once, then all of the actors are allowed to run concurrently for one game loop tick. In both cases, I'm thinking of placing the AABB tree into shared memory, but my brief experience with using shared memory makes me wary of performance problems. (1) Persistent in this sense, of course: https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
- dragontamer 7y ago> I was thinking about adding atomic pointer references to a partially persistent (1) AABB tree, then allowing multiple actors in multiple threads each implementing a gameloop to query the AABB tree. Do I need to think about memory fences in that application? Probably? Let me give an attempt at what a memory-fence actually is, and why I think you may need to think about memory fences. Atomics solve one PART of the synchronization problem. The second problem, which is far more complex, is that the compiler, CPU, and Memory / Cache system reorders your reads-and-writes in a non-obvious way. These reorderings can lead to obscure bugs. These reorderings happen because of single-threaded optimization. Programmers expect the compiler, CPU, and L1 cache to reorder statements to go as fast as possible. Ever wonder what the -O2 and -O3 compiler flags do? They'll eliminate variables and change your code in subtle ways. Even if you run at -O0 optimizations, these conceptual reorderings exist at the CPU (store buffer) and L1 cache levels. So you cannot escape this unfortunate, complex reality. Therefore: it is the programmer's responsibility to define a "Happens-before" relationship through memory fences / memory barriers. A "happens-before" relationship will kill optimizations (be it a compiler-optimization, CPU store-buffer optimization, or L1 cache optimization) in just the right way to make your code correct. ------------ With that out of the way, lets go into your AABB tree question. Assume "node" is a node to a binary AABB tree, with "node->left" and "node->right" referring to its two children. Lets assume both "left" and "right" are atomic<> pointers. Now think of the code: AABB_Node tmp = malloc(); node->left->store(tmp); // This is a race condition! tmp.initialize(); The above code is wrong. You can't "publish" the data before it is initialized! "tmp" would contain garbage data (its "fresh" from the malloc). Therefore, you need to write the following code: AABB_Node tmp = malloc(); tmp.initialize(); node->left->store(tmp); Okay, now you "think" you've solved the multithreaded issue, but you have NOT. Because the compiler says "tmp is an unnecessary variable" and optimizes it away. So the compiler may decide to emit: node->left->store(malloc()); node->left->initialize(); // Compiler wants variable-elimination optimization Uh oh, the compiler "moved" the code around, which is logical in a single-threaded setting. But this reordering destroys your multithreaded logic. Your other threads may get the malloc() before the initialize. ------------ "Happens-before" is the key concept. What we want to say is: AABB_Node tmp = malloc(); tmp.initialize(); __happens before__ node->left->store(tmp); Good news: modern C++11 allows you to specify a "happens before" relationship through memory fences. node->left->store(tmp, memory_order_release); "Memory_order_release" is the minimum happens-before relationship we want. The C++11 standard states: "A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store." The compiler will emit the low-level code needed to ensure the happens-before relationship will work through lower-level memory fence mechanisms. GPUs will have to clear their L1 cache (due to incoherent memory), while CPUs will only have to wait for the store-buffer to be flushed and MESI messages to be passed around (ARM has the "dmb ish" statement for example) Regardless of the low-level details, the job of the programmer with memory fences remains the same. Specifying important "happens-before" relationships. ------------- In the GPU world, where C++11 atomics do not exist yet, the happens-before relationship is created with a threadfence instruction. In CUDA, you would do: AABB_Node tmp = malloc(); tmp.initialize(); __threadfence_block(); // Block-level synchronization node->left = tmp; __threadfence_block() is only a fence that works within a CUDA-workgroup (and is therefore far faster than __threadfence()). Effectively, you only wait for L1 cache (while __threadfence() waits for an L2 cache commit). ------------- I'll butcher the explanations a bit (real code doesn't work like this, but it may help you to understand things). EDIT: Oh gosh, I got these backwards again in my first draft. I'm pretty sure I put them in the correct order now. An "acquire-read" operation basically compiles from: foo(); node->left.load(memory_order_acquire); bar(); Becomes (approximately) foo(); register = node->left __happens before__ bar(); Different CPUs have different memory guarantees. x86 will have __happens before__ be a no-op in this case. An "release-store" operation compiles from: foo() node->left.store(register, memory_order_release); bar(); Becomes (approximately) foo(); __happens before__ node->left = register; bar(); The "strongest" operation is memory_order_seq_cst, which approximately translates into: foo(); __happens before__ node->left = register; __happens before__ bar(); But this kind of heavy-ordering is the slowest to implement in practice. Hopefully that explains a few things.