Kahn Process Networks as Concurrent Data Structures: Lock Freedom, Parallelism, Relaxation in Shared Memory

Nhat Minh Lê 1
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : In this thesis, we are interested in Kahn process networks, a simple yet expressive model of concurrency, and its parallel implementation on modern shared-memory architectures. Kahn process networks expose concurrency to the programmer through an arrangement of sequential processes and single-producer single-consumer channels. The focus is on the implementation aspects. Of particular importance to our study are two parameters: lock freedom and relaxed memory. The development of fast and efficient lock-free algorithms ties into concerns of controlled resource consumption (important in embedded systems) and reliable performance on current and future platforms with unfair or skewed scheduling such as virtual machines and GPUs. Our work with relaxed memory models complements this more theoretical approach by offering a window into realistic shared-memory architectures. We present a new lock-free algorithm for a Kahn process network interpreter. It is disjoint-access parallel: we allow multiple threads to work on the same shared Kahn process network, fully utilizing the parallelism exhibited by independent processes. It is non-blocking in that it guarantees global progress in bounded memory, even in the presence of (possibly infinite) delays affecting the executing threads. To our knowledge, it is the first lock-free system of this size, and integrates various well-known non-blocking techniques and concepts (e.g., safe memory reclamation, multi-word updates, assistance) with ideas and optimizations specific to the Kahn network setting. We also discuss a blocking variant of this algorithm, targetted at high-performance computing, with en-couraging experimental results.
Complete list of metadatas

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/tel-01684181
Contributor : Albert Cohen <>
Submitted on : Monday, January 15, 2018 - 12:02:19 PM
Last modification on : Monday, January 28, 2019 - 9:03:31 AM
Long-term archiving on : Saturday, May 5, 2018 - 8:09:04 PM

File

nml-thesis.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01684181, version 1

Collections

Citation

Nhat Minh Lê. Kahn Process Networks as Concurrent Data Structures: Lock Freedom, Parallelism, Relaxation in Shared Memory. Programming Languages [cs.PL]. Ecole normale supérieure - ENS PARIS, 2016. English. ⟨tel-01684181⟩

Share

Metrics

Record views

146

Files downloads

86