[concurrency-interest] A Practical Wait-Free Multi-Word Compare-and-Swap Operation

Kimo Crossman kimo at webnetic.net
Mon Nov 4 20:31:27 EST 2013

> http://www.mscs.mu.edu/~brylow/SPLASH-MARC-2013/Feldman.pdf
> A Practical Wait-Free Multi-Word Compare-and-Swap
> Operation
> Steven Feldman
> University of Central Florida
> Feldman at knights.ucf.edu
> Pierre LaBorde
> University of Central Florida
> Damian Dechev
> University of Central Florida
> dechev at eecs.ucf.edu
> Algorithms designed for current and future multi-core systems,
> which are expected to experience an increase of the
> number of cores by 100x over the next decade, must exhibit
> strong scaling. The guarantee of progress provided
> by wait-free algorithms and the fine-grained synchronization
> methods used in their designs, make them desirable for
> achieving this goal. However, the design and development
> of advanced wait-free algorithms is often inhibited by the
> limitations of portable atomic hardware operations. Typically
> these operations can manipulate a single address at
> a time, where many concurrent algorithms need to perform
> a series of operations on multiple addresses, requiring more
> advanced synchronization mechanisms such as a wait-free
> Multi-Word-Compare-and-Swap (MCAS).
> In this paper, we present the first practical MCAS design
> that is wait-free in all scenarios. This property holds even if
> interrupts consistently cause a thread to retry a portion of
> its operation. Our design is practical in that it is built from
> only portable atomic operations (e.g. atomic reads, atomic
> writes, compare-and-swap), it is efficient in its utilization of
> memory (i. e. requiring only a single bit to be reserved from
> each word, not requiring use of explicit memory barriers, and
> requiring only four words per address in the operation). Our
> performance evaluation reveals that on average our wait-free
> MCAS algorithm performs 8.3% faster than other practical
> approaches in all tested scenarios.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20131104/50568c57/attachment.html>

More information about the Concurrency-interest mailing list