Synchronization Costs in Parallel Programs and Concurrent Data Structures

Vitalii Aksenov 1, 2, 3, 4
Abstract : To use the computational power of modern computing machines, we have to deal with concurrent programs. Writing efficient concurrent programs is notoriously difficult, primarily due to the need of harnessing synchronization costs. In this thesis, we focus on synchronization costs in parallel programs and concurrent data structures. First, we present a novel granularity control technique for parallel programs designed for the dynamic multithreading environment. Then in the context of concurrent data structures, we consider the notion of concurrency-optimality and propose the first implementation of a concurrency-optimal binary search tree that, intuitively, accepts a concurrent schedule if and only if the schedule is correct. Also, we propose parallel combining, a technique that enables efficient implementations of concurrent data structures from their parallel batched counterparts. We validate the proposed techniques via experimental evaluations showing superior or comparable performance with respect to state-of-the-art algorithms. From a more formal perspective, we consider the phenomenon of helping in concurrent data structures. Intuitively, helping is observed when the order of some operation in a linearization is fixed by a step of another process. We show that no wait-free linearizable implementation of stack using read, write, compare&swap and fetch&add primitives can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al. Finally, we propose a simple way to analytically predict the throughput of data structures based on coarse-grained locking.
Liste complète des métadonnées

Cited literature [36 references]  Display  Hide  Download

https://hal.inria.fr/tel-01887505
Contributor : Vitalii Aksenov <>
Submitted on : Thursday, October 4, 2018 - 1:54:36 PM
Last modification on : Friday, January 4, 2019 - 5:33:38 PM
Document(s) archivé(s) le : Saturday, January 5, 2019 - 2:01:03 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01887505, version 1

Collections

Citation

Vitalii Aksenov. Synchronization Costs in Parallel Programs and Concurrent Data Structures. Distributed, Parallel, and Cluster Computing [cs.DC]. ITMO University; Paris Diderot University, 2018. English. ⟨tel-01887505⟩

Share

Metrics

Record views

366

Files downloads

170