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
Delegation locking libraries for improved performance of multithreaded programs
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.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
2014 (English)In: Euro-Par 2014: Parallel Processing, Springer Berlin/Heidelberg, 2014, Vol. 8632, p. 572-583Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2014. Vol. 8632, p. 572-583
Series
Lecture Notes in Computer Science ; 8632
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-234577DOI: 10.1007/978-3-319-09873-9_48ISBN: 978-3-319-09872-2 (print)OAI: oai:DiVA.org:uu-234577DiVA, id: diva2:757133
Conference
20th International European Conference on Parallel Processing, Porto, Portugal, August 25-29, 2014
Projects
UPMARCRELEASEAvailable from: 2014-08-29 Created: 2014-10-21 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

Klaftenegger, DavidSagonas, KonstantinosWinblad, Kjell

Search in DiVA

By author/editor
Klaftenegger, DavidSagonas, 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: 509 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