On “correct and efficient work-stealing for weak memory models”

#106 · ✸ 77 · 💬 7 · 2 months ago · wingolog.org · ingve
This is useful when implementing per-CPU schedulers or work queues; each CPU pushes on any items that it has to its own deque, and pops them also, but when it runs out of work, it goes to see if it can steal work from other CPUs. The 2013 paper Correct and Efficient Work-Stealing for Weak Memory Models by Nhat Min Lê et al updates the Chase-Lev paper by relaxing the concurrency primitives from the original big-hammer sequential-consistency operations used in the Chase-Lev paper to an appropriate mix of C11 relaxed, acquire/release, and sequentially-consistent operations. Each worker thread would keep a local unsynchronized work queue, which when it grew too large would donate half of its work to a per-worker Chase-Lev deque. Then if it ran out of work, it would go through all the workers, seeing if it could steal some work. My use of the deque was thus limited to only the push and steal primitives, but not take. Take is like steal, except that it takes values from the producer end of the deque, and it can't run concurrently with push. Well I thought, you know, before a worker thread goes to steal from some other thread, it might as well see if it can do a cheap take on its own deque to see if it could take back some work that it had previously offloaded there.
On “correct and efficient work-stealing for weak memory models”



Archive | Send Feedback | WebAssembly Version (beta)