Skip to Main content Skip to Navigation

Synchronization Costs in Parallel Programs and Concurrent Data Structures

Vitalii Aksenov 1, 2, 3, 4
3 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
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.
Complete list of metadata

Cited literature [155 references]  Display  Hide  Download
Contributor : Vitalii Aksenov Connect in order to contact the contributor
Submitted on : Thursday, October 4, 2018 - 1:54:36 PM
Last modification on : Tuesday, January 11, 2022 - 11:16:04 AM
Long-term archiving on: : Saturday, January 5, 2019 - 2:01:03 PM


Files produced by the author(s)


  • HAL Id : tel-01887505, version 1


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⟩



Les métriques sont temporairement indisponibles