This paper is very interesting, it talks about (lock free) work stealing algorithms with private deques, this means that idle processors need to wait for a busy processor to communicate with them in order to steal a task. This is different to work stealing algorithms with concurrent deques, were idle processors are able to immediately acquire work by stealing it from the deque of one of the busy processors.
Interestingly, for several workloads private deques work just as well as concurrent deques!
toothless
What's one example of an implementation of a concurrent, lock-free deque?
I know that a deque (with limited size) can be represented as an array with head and tail pointers that circle around the array. But that still requires operations of the form array[head++] = value, etc. Are there built-in atomic operations of that form?
This paper is very interesting, it talks about (lock free) work stealing algorithms with private deques, this means that idle processors need to wait for a busy processor to communicate with them in order to steal a task. This is different to work stealing algorithms with concurrent deques, were idle processors are able to immediately acquire work by stealing it from the deque of one of the busy processors.
Interestingly, for several workloads private deques work just as well as concurrent deques!
What's one example of an implementation of a concurrent, lock-free deque?
I know that a deque (with limited size) can be represented as an array with head and tail pointers that circle around the array. But that still requires operations of the form array[head++] = value, etc. Are there built-in atomic operations of that form?