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
Dynamic Adaptations of Synchronization Granularity in Concurrent Data Structures
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, Division of Computer Systems.
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 [en]
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: urn:nbn:se:uu:diva-354026ISBN: 978-91-513-0367-3 (print)OAI: oai:DiVA.org:uu-354026DiVA, id: diva2:1220366
Public defence
2018-09-14, room 2446, ITC, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Projects
UPMARCAvailable from: 2018-08-17 Created: 2018-06-18 Last updated: 2019-02-25
List of papers
1. A contention adapting approach to concurrent ordered sets
Open this publication in new window or tab >>A contention adapting approach to concurrent ordered sets
2018 (English)In: Journal of Parallel and Distributed Computing, ISSN 0743-7315, E-ISSN 1096-0848, Vol. 115, p. 1-19Article in journal (Refereed) Published
Abstract [en]

With multicores being ubiquitous, concurrent data structures are increasingly important. This article proposes a novel approach to concurrent data structure design where the data structure dynamically adapts its synchronization granularity based on the detected contention and the amount of data that operations are accessing. This approach not only has the potential to reduce overheads associated with synchronization in uncontended scenarios, but can also be beneficial when the amount of data that operations are accessing atomically is unknown. Using this adaptive approach we create a contention adapting search tree (CA tree) that can be used to implement concurrent ordered sets and maps with support for range queries and bulk operations. We provide detailed proof sketches for the linearizability as well as deadlock and livelock freedom of CA tree operations. We experimentally compare CA trees to state-of-the-art concurrent data structures and show that CA trees beat the best of the data structures that we compare against by over 50% in scenarios that contain basic set operations and range queries, outperform them by more than 1200% in scenarios that also contain range updates, and offer performance and scalability that is better than many of them on workloads that only contain basic set operations.

Place, publisher, year, edition, pages
ACADEMIC PRESS INC ELSEVIER SCIENCE, 2018
Keywords
Concurrent data structures, Ordered sets, Linearizability, Range queries
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-351559 (URN)10.1016/j.jpdc.2017.11.007 (DOI)000427809200001 ()
Available from: 2018-05-30 Created: 2018-05-30 Last updated: 2018-06-18Bibliographically approved
2. More scalable ordered set for ETS using adaptation
Open this publication in new window or tab >>More scalable ordered set for ETS using adaptation
2014 (English)In: Proc. 13th ACM SIGPLAN Workshop on Erlang, New York: ACM Press, 2014, p. 3-11Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2014
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-234579 (URN)10.1145/2633448.2633455 (DOI)978-1-4503-3038-1 (ISBN)
Conference
Erlang 2014
Projects
RELEASEUPMARC
Available from: 2014-09-03 Created: 2014-10-21 Last updated: 2018-06-18Bibliographically approved
3. Lock-free Contention Adapting Search Trees
Open this publication in new window or tab >>Lock-free Contention Adapting Search Trees
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
National Category
Computer and Information Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-354022 (URN)10.1145/3210377.3210413 (DOI)978-1-4503-5799-9 (ISBN)
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
4. Delegation locking libraries for improved performance of multithreaded programs
Open this publication in new window or tab >>Delegation locking libraries for improved performance of multithreaded programs
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
Series
Lecture Notes in Computer Science ; 8632
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-234577 (URN)10.1007/978-3-319-09873-9_48 (DOI)978-3-319-09872-2 (ISBN)
Conference
20th International European Conference on Parallel Processing, Porto, Portugal, August 25-29, 2014
Projects
UPMARCRELEASE
Available from: 2014-08-29 Created: 2014-10-21 Last updated: 2018-06-18Bibliographically approved
5. The Contention Avoiding Concurrent Priority Queue
Open this publication in new window or tab >>The Contention Avoiding Concurrent Priority Queue
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
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10136
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-346764 (URN)10.1007/978-3-319-52709-3_23 (DOI)000413069500023 ()978-3-319-52708-6 (ISBN)
Conference
LCPC 2016, September 27–30, Rochester, NY
Available from: 2017-01-24 Created: 2018-03-26 Last updated: 2018-06-18Bibliographically approved

Open Access in DiVA

fulltext(809 kB)120 downloads
File information
File name FULLTEXT01.pdfFile size 809 kBChecksum SHA-512
5d569b4ea65641fb5d6bf00e96dc157979111e4f38ed3958cbabb30ef98c9368c2714d7ca03eed13aa4d43e05e6ab26361a42da504591fe599164cbdf1034c53
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Winblad, Kjell

Search in DiVA

By author/editor
Winblad, Kjell
By organisation
Computing ScienceDivision of Computer Systems
Computer SciencesOther Computer and Information ScienceSoftware Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 120 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

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