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
The Contention Avoiding Concurrent Priority Queue
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.
2017 (English)In: Languages and Compilers for Parallel Computing, Springer, 2017, p. 314-330Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2017. p. 314-330
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10136
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-346764DOI: 10.1007/978-3-319-52709-3_23ISI: 000413069500023ISBN: 978-3-319-52708-6 (print)OAI: oai:DiVA.org:uu-346764DiVA, id: diva2:1193309
Conference
LCPC 2016, September 27–30, Rochester, NY
Available from: 2017-01-24 Created: 2018-03-26 Last updated: 2018-06-18Bibliographically 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
Projects
UPMARC
Available from: 2018-08-17 Created: 2018-06-18 Last updated: 2019-02-25

Open Access in DiVA

No full text in DiVA

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 Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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