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

    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