Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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)
2009 (English)Conference paper, Published paper (Refereed)
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 calling, 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
CSREA Press , 2009.
Keyword [en]
wait-free, multi-thread, compare-and-swap, real-time, Parallel Programming
National Category
Computer and Information Science Computer and Information Science
Identifiers
URN: urn:nbn:se:hb:diva-6306Local ID: 2320/5914ISBN: 9781601321213 (print)ISBN: 9781601321220 (print)OAI: oai:DiVA.org:hb-6306DiVA: diva2:886993
Conference
The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA
Available from: 2015-12-22 Created: 2015-12-22

Open Access in DiVA

fulltext(133 kB)149 downloads
File information
File name FULLTEXT01.pdfFile size 133 kBChecksum SHA-512
57f91107e8503bb07155d3b6849c9acda137f19f64865be6d04c341ceae7438fcf1f98a7c372db9b1547dc35be042bb9a90847550594d3fb89bc3414d323800a
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Sundell, Håkan
By organisation
School of Business and IT
Computer and Information ScienceComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 149 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 43 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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