Work stealing is the method of choice for load balancing in task parallel programming languages and frameworks. Yet despite considerable effort invested in optimizing work stealing task queues, existing algorithms issue a costly  memory fence  when removing a task, and these fences are believed to be necessary for correctness.   This paper refutes this belief, demonstrating work stealing algorithms in which  a worker does not issue a memory fence  for microarchitectures with a  bounded  total store ordering (TSO) memory model. Bounded TSO is a novel restriction of TSO~-- capturing mainstream x86 and SPARC TSO processors -- that bounds the number of stores a load can be reordered with.   Our algorithms eliminate the memory fence penalty, improving the running time of a suite of parallel benchmarks on modern x86 multicore processors by 7%-11% on average (and up to 23%), compared to the Cilk and Chase-Lev work stealing queues.
['Adam Morrison', 'Yehuda Afek']
Fence-free work stealing on bounded TSO processors