Talk type: Talk

Intro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms

  • Talk in English
Presentation pdf

This talk is focused on data structures with relaxed (non-linearizable) semantics, applying them for task scheduling in parallel algorithms.

This small series of "Introduction to Concurrent Programming" talks cover a wide range of classic algorithms and techniques spiced with necessary theory. Starting with the state-of-the-art stack and queue algorithms in the first talk, we apply the gained knowledge to build fast and scalable queues that leverage the unconditional Fetch-And-Add primitive and the modern flat-combining technique in the second part.In the third part, we discuss data structures with relaxed (non-linearizable) semantics, applying them for task scheduling in parallel algorithms. Each part goes with a set of practical assignments to implement the discussed data structures and sharpen your skills in concurrent programming. While this series does not cover all the popular aspects of concurrent programming, it is an excellent start to getting into the world of concurrency.

Each talk goes with the corresponding task assignments: https://github.com/ndkoval/Hydra2022

  • #multi-queue
  • #scheduling
  • #stealing-multi-queue

Speakers

Invited experts

Schedule