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

Content Provider	Springer Nature Link
Author	Feldman, Steven LaBorde, Pierre Dechev, Damian
Copyright Year	2014
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.
Starting Page	572
Ending Page	596
Page Count	25
File Format	PDF
ISSN	08857458
Journal	International Journal of Parallel Programming
Volume Number	43
Issue Number	4
e-ISSN	15737640
Language	English
Publisher	Springer US
Publisher Date	2014-03-16
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Wait-free Lock-free Non-blocking Concurrent Multi-word compare-and-swap MCAS CAS Theory of Computation Processor Architectures Software Engineering/Programming and Operating Systems
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Wait-Free Multi-Word Compare-and-Swap Using Greedy Helping and Grabbing

A Wait-Free Hash Map

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

An optimistic approach to lock-free FIFO queues

A Practical Multi-Word Compare-and-Swap Operation (2002)

A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs

Lock-free resizeable concurrent tries.

A Practical Multi-Word Compare-and-Swap Operation

A Practical Multi-Word Compare-and-Swap Operation (2002)

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

Similar Documents

Wait-Free Multi-Word Compare-and-Swap Using Greedy Helping and Grabbing

A Wait-Free Hash Map

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

An optimistic approach to lock-free FIFO queues

A Practical Multi-Word Compare-and-Swap Operation (2002)

A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs

Lock-free resizeable concurrent tries.

A Practical Multi-Word Compare-and-Swap Operation

A Practical Multi-Word Compare-and-Swap Operation (2002)

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