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
A Lock-Free Algorithm for Concurrent Bags
University of Borås, School of Business and IT. (CSL@BS)
University of Borås, School of Business and IT. (CSL@BS)
2011 (English)Conference paper, Published paper (Refereed)
Abstract [en]

A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithm supports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrency efficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supported semantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handling concurrent modifications of linked lists using double marks, detection of total emptiness, and efficient memory management with hazard pointer handover. Experiments on a 24-way multi-core platform show significantly better performance for the new algorithm compared to previous algorithms of relevance.

Place, publisher, year, edition, pages
ACM , 2011.
Keywords [en]
concurrent, data structure, non-blocking, shared memory, Parallel Programming
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:hb:diva-6575DOI: 10.1145/1989493.1989550Local ID: 2320/8255ISBN: 978-1-4503-0743-7 (print)OAI: oai:DiVA.org:hb-6575DiVA, id: diva2:887271
Conference
The 23rd Annual Symposium on Parallelism in Algorithms and Architectures, San Jose, June 4-6, 2011
Available from: 2015-12-22 Created: 2015-12-22 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Sundell, HåkanGidenstam, Anders

Search in DiVA

By author/editor
Sundell, HåkanGidenstam, Anders
By organisation
School of Business and IT
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 79 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