Highly concurrent multi-word synchronization

The design of concurrent data structures is greatly facilitated by the availability of synchronization operations that atomically modify k arbitrary items, such as k -read–modify–write ( k rmw ). Aiming to increase concurrency in order to exploit the parallelism offered by today’s multi-core and multi-processing architectures, we propose a highly concurrent software implementation of k rmw, with only constant space overhead. Our algorithm ensures that two operations delay each other only if they are within distance O ( k ) in the conflict graph, induced by the operations’ data items. The algorithm uses double compare-and-swap (dcas). When dcas is not supported by the architecture, the algorithm of Attiya and Dagan (2001) [3] can be used to replace dcas with (unary) cas, with only a slight increase in the interference among operations.

Authors

• Hagit Attiya
• Eshcar Hillel

Keywords

• Multi-word synchronization
• Concurrent data structures
• Local nonblocking
• dcas