Title

A Wait-Free Multi-Word Compare-and-Swap Operation

Authors

Authors

S. Feldman; P. LaBorde;D. Dechev

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Int. J. Parallel Program.

Keywords

Wait-free; Lock-free; Non-blocking; Concurrent; Multi-word; compare-and-swap; MCAS; CAS; LOCK-FREE; OBJECTS; METHODOLOGY; Computer Science, Theory & Methods

Abstract

The number of cores in future multi-core systems are expected to increase by 100 fold over the next decade. The fine-grained synchronization methods found in wait-free algorithm designs makes them desirable for these future systems. Unfortunately, such designs are often inhibited by the limitations of portable atomic hardware primitives. Typically these primitives can only operate on a single address at a time, while concurrent algorithms often need to operate on multiple addresses. To support such algorithms we present a practical wait-free Multi-word-compare-and-swap. The wait-free property ensures that each thread completes its operation in a finite number of steps, even if it is continuously interrupted. Our approach uses a progress assurance scheme that allows a blocked thread to announce that it is unable to make progress. This differs from traditional lock-free helping techniques where a thread will only help complete an operation that is in conflict with its own. Our design is practical in that it is built from only portable atomic operations, 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), and has a wait-free progress guarantee. When tested in a high contention scenario with 64 threads executing updates on a single multi-word object, our wait-free design performs on average 77.1 % more operations than other practical approaches. Over all tested scenarios, our design performs on average 8.3 % more operations.

Journal Title

International Journal of Parallel Programming

Volume

43

Issue/Number

4

Publication Date

1-1-2015

Document Type

Article

Language

English

First Page

572

Last Page

596

WOS Identifier

WOS:000352287300002

ISSN

0885-7458

Share

COinS