Notes on lock-free programming

I used Julia as the language in my intro to parallel computing course this year, and it went quite well. Over the past year I’ve created some notes on Julia parallel computing topics, which may be of interest to the community. The latest are Notes on Lock-Free Programming with Atomics with Julia and Notes on Distributed Parallel Computing with Julia.

31 Likes

Thanks for sharing!

When can we expect a Julia-version of your Elements of Parallel Programming book?

5 Likes

My book is language-neutral, and uses pseudocode. I’ll have to start adding Julia implementations to the book’s github site.

4 Likes

I only skimmed the code, so I apologise if I missed something. But I find the line `atomic_min!(D[j], D[i][] + g.weights[j,i]) > D[j][]` in the parallel `relax` function very tricky because I suspect the following scenario is possible

``````lhs1 = atomic_min!(D[j], D[i1][] + g.weights[j,i1])  # thread 1 (no update)
lhs2 = atomic_min!(D[j], D[i2][] + g.weights[j,i2])  # thread 2 (updated)
rhs1 = D[j][]                                        # thread 1
lhs1 > rhs1                                          # thread 1
``````

That is to say, `>` evaluates to `true` in thread 1 since thread 2 updates `D[j]` in the middle.

My guess is that it’s still OK since all that matters is if `j` is in the list or not ? Maybe you discussed this in your book or consider it obvious for the readers at this stage, but I wonder if it makes sense to add a quick note for the correctness argument of the lock-free algorithm.

(I’d also suggest non-atomics approach for `subList` accumulation, but maybe that’s not the theme of this chapter.)

1 Like

You’re correct that this scenario doesn’t matter; what matters is that D[j] is updated atomically, and that j is inserted in a thread’s list once. Your comments make me think that I will expand the discussion to examine different thread orderings. As far as `subList` accumulation, that is already being done without atomics, however the atomic_cas is needed for updating `inList` to ensure all accesses are atomic.

Thanks for the confirmation. Yes, it’d be nice if non-trivial uses (e.g., not just incrementing a single counter) of atomics come with some discussion on its correctness.

IIUC, the `relax` algorithm is essentially `mapreduce(j -> Set([j]), union!, indices)` fused with filtering based on `atomic_min!(D[j], D[i][] + g.weights[j,i]) > D[j][]`. Since `reduce` can be done without atomics, there is no need to use `atomic_cas!` in principle. But the performance depends on how much contention the algorithm has on `InList[j]` and it’s conceivable that `atomic_cas!` is useful in algorithms like this.

I’ve updated the webpage to include a more detailed discussion of atomic_min and atomic_cas, and also to discuss the point you raised, @tkf, about the comparison `atomic_min!(D[j], D[i][] + g.weights[j,i]) > D[j][]` not being atomic.

1 Like