Optimistic Concurrency Control

Specific Domains Julia at Scale
1

I am considering implementing a parallel (multi-threaded) algorithm using optimistic concurrency control. i.e. you allow race conditions to happen but ensure the correctness is not affected.

I was hoping to find information on race-conditions.

For example

s = 100
a = 0
@threads for i in 1:2 
   a += s
end

Is it guaranteed that the final value of a will be s or 2*s?

More specific info: This is what I’m looking to implement
https://kulslide.com/download/avoiding-locks-and-atomic-instructions-in-shared-memory-parallel-bfs-using-optimistic-parallelization-_59fd803ad64ab2f105a35e8f_pdf

2

No. What you are creating is a data race that is undefined behavior (in LLVM and C (i.e. runtime) level so there’s little we can do).

Without reading the paper you link, I believe what you want to use is relaxed atomics. In short, race on data is undefined behavior (UB) but race on atomics are not so the only possible race you can allow that doesn’t introduce UB is to use atomics. For the current language standard and for all relevant architectures, the way to use atomics without introducing atomic instructions and with minimum performance impact is to use relaxed atomics. It also fits the title of the paper very well since,

  1. it doesn’t use atomic instruction
  2. it DOES disable certain compiler optimizations, which has to be the case since those optimizations can easily make your code invalid with concurrent access.

Julia currently doesn’t support relaxed atomics directly. However, you can implement them fairly easily with llvmcall. You should be able to replace the value of a with a Ref(1) and use llvmcall to implement atomic load and store with relaxed ordering on it. You can check the implementation of Atomic together with LLVM Language Reference Manual — LLVM 18.0.0git documentation to figure out how you can do that.

1 Like
3

Do note that reasonning about relaxed atomics (or basically any race that doesn’t give you ordering guarantee) can be extremely difficult, something I would certainly not do myself out of few well defined local context. For further reading, search “out of thin air value”.