uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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
Contention adapting search trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Natl Tech Univ Athens, Sch ECE, GR-10682 Athens, Greece. (Programming Languages)ORCID iD: 0000-0001-9657-0179
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (Programming Languages)
2015 (English)In: Proc. 14th International Symposium on Parallel and Distributed Computing, IEEE conference proceedings, 2015, 215-224 p.Conference paper, Published paper (Refereed)
Abstract [en]

With multicores being ubiquitous, concurrent data structures are becoming increasingly important. This paper proposes a novel approach to concurrent data structure design where the data structure collects statistics about contention and adapts dynamically according to this statistics. We use this approach to create a contention adapting binary search tree (CA tree) that can be used to implement concurrent ordered sets and maps. Our experimental evaluation shows that CA trees scale similar to recently proposed algorithms on a big multicore machine on various scenarios with a larger set size, and outperform the same data structures in more contended scenarios and in sequential performance. We also show that CA trees are well suited for optimization with hardware lock elision. In short, we propose a practically useful and easy to implement and show correct concurrent search tree that naturally adapts to the level of contention.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2015. 215-224 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-272365DOI: 10.1109/ISPDC.2015.32ISI: 000380396000027ISBN: 9781467371476 (print)OAI: oai:DiVA.org:uu-272365DiVA: diva2:893836
Conference
ISPDC 2015, June 29 – July 1, Limassol, Cyprus
Projects
UPMARCRELEASE
Funder
Swedish Research Council
Available from: 2015-07-01 Created: 2016-01-13 Last updated: 2016-08-24Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Sagonas, KonstantinosWinblad, Kjell

Search in DiVA

By author/editor
Sagonas, KonstantinosWinblad, Kjell
By organisation
Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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