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
Lock-free Contention Adapting Search Trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.ORCID iD: 0000-0001-9657-0179
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2018 (English)In: The 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, New York, NY, USA, 2018, Vol. 30Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York, NY, USA, 2018. Vol. 30
National Category
Computer and Information Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-354022DOI: 10.1145/3210377.3210413ISBN: 978-1-4503-5799-9 (print)OAI: oai:DiVA.org:uu-354022DiVA, id: diva2:1220293
Conference
The 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, July 16–18, 2018, Vienna, Austria
Funder
Swedish Research Council
Note

In press

Available from: 2018-06-18 Created: 2018-06-18 Last updated: 2018-06-27Bibliographically approved
In thesis
1. Dynamic Adaptations of Synchronization Granularity in Concurrent Data Structures
Open this publication in new window or tab >>Dynamic Adaptations of Synchronization Granularity in Concurrent Data Structures
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The multicore revolution means that programmers have many cores at their disposal in everything from phones to large server systems. Concurrent data structures are needed to make good use of all the cores. Designing a concurrent data structure that performs well across many different scenarios is a difficult task. The reason for this is that the best synchronization granularity and data organization vary between scenarios. Furthermore, the number of parallel threads and the types of operations that are accessing a data structure may even change over time.

This dissertation tackles the problem mentioned above by proposing concurrent data structures that dynamically adapt their synchronization granularity and organization based on usage statistics collected at run-time. Two of these data structures (one lock-free and one lock-based) implement concurrent sets with support for range queries and other multi-item operations. These data structures adapt their synchronization granularity based on detected contention and the number of items that are involved in multi-item operations such as range queries. This dissertation also proposes a concurrent priority queue that dynamically changes its precision based on detected contention.

Experimental evaluations of the proposed data structures indicate that they outperform non-adaptive data structures over a wide range of scenarios because they adapt their synchronization based on usage statistics. Possible practical consequences of the work described in this dissertation are faster parallel programs and a reduced need to manually tune the synchronization granularities of concurrent data structures.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2018. p. 92
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1684
Keywords
concurrent data structures, contention adapting, range queries, lock-freedom, adaptivity, linearizability, ordered sets, maps, key-value stores, concurrent priority queues, relaxed concurrent data structures, locks, delegation locking
National Category
Computer Sciences Other Computer and Information Science Software Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-354026 (URN)978-91-513-0367-3 (ISBN)
Public defence
2018-09-14, room 2446, ITC, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2018-08-17 Created: 2018-06-18 Last updated: 2018-08-28

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Winblad, KjellSagonas, KonstantinosJonsson, Bengt

Search in DiVA

By author/editor
Winblad, KjellSagonas, KonstantinosJonsson, Bengt
By organisation
Computing ScienceComputer Systems
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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