Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • harvard-cite-them-right
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Wait-Free Multi-Word Compare-and-Swap Using Greedy Helping and Grabbing
University of Borås, School of Business and IT. (CSL@BS)
2011 (English)In: International journal of parallel programming, ISSN 0885-7458, E-ISSN 1573-7640, Vol. 36, no 9, p. 694-716Article in journal (Refereed) Published
Abstract [en]

We present a new algorithm for implementing a multi-word compare-and-swap functionality supporting the Read and CASN operations. The algorithm is wait-free under reasonable assumptions on execution history and benefits from new techniques to resolve conflicts between operations by using greedy helping and grabbing. Although the deterministic scheme for enabling grabbing somewhat sacrifices fairness, the effects are insignificant in practice. Moreover, unlike most of the previous results, the CASN operation does not require the list of addresses to be sorted before the operation is invoked, and the Read operation can read the current value without applying helping when the word to be read is within an ongoing transaction. Experiments using micro-benchmarks varying important parameters in three dimensions have been performed on two multiprocessor platforms. The results show similar performance as the lock-free algorithm by Harris et al. for most scenarios, and significantly better performance on scenarios with very high contention. This is altogether extraordinary good performance considering that the new algorithm is wait-free.

Place, publisher, year, edition, pages
Springer Netherlands , 2011. Vol. 36, no 9, p. 694-716
Keywords [en]
wait-free, multi-thread, compare-and-swap, real-time, Parallel Programming
National Category
Computer and Information Sciences
Research subject
Bussiness and IT
Identifiers
URN: urn:nbn:se:hb:diva-3141DOI: 10.1007/s10766-011-0167-4Local ID: 2320/8617OAI: oai:DiVA.org:hb-3141DiVA, id: diva2:871237
Funder
Swedish Research Council, 80487001
Note

Sponsorship:

Part of this work was carried out under the HPC-EUROPA project (RII3-CT-2003-

506079), Infrastructure Action under the FP6 “Structuring the European Research Area” program. This work was also supported by the Swedish Research Council under grant number 80487001.

Available from: 2015-11-13 Created: 2015-11-13 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Sundell, Håkan

Search in DiVA

By author/editor
Sundell, Håkan
By organisation
School of Business and IT
In the same journal
International journal of parallel programming
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 179 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • harvard-cite-them-right
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf