If one ignores the conflicts when accessing the dequeue in Work-Stealing algorithms, does it matter (and in what ways) if one steals from the top or bottom (or anywhere randomly) of the dequeue? Does it matter (and in what ways) if one steals one or more items ?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I did some experiments about this myself a while back so I hope I can still give some insight. This approach is called "Idempotent Work Stealing" and was defined (to the best of my knowledge) here. It means that you can get items more than once but at least once. There are then three operations defined $put()$, $take()$, and $steal()$. The idea is that $put()$ and $take()$ are free of synchronisation only $take()$ uses atomics. When a thread has finished its queue (or stack) it uses $steal()$ on some other threads stack.
-
$\begingroup$ The paper is nice. It shows by experiment that you may do FIFO or LIFO, or Double-Ended without much different in performance. Unfortunately, there isn't any insight in the theoretical aspect. And it's not about getting more than one items -- it's getting a single item many times. $\endgroup$– w00dMar 15, 2018 at 18:36