Notes on lock-free programming

Community Teaching & Outreach
1

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
2

Thanks for sharing!

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

5 Likes
3

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

4 Likes
4

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
5

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.

6

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.

7

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