Intro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
summary
Relaxed (non-linearizable) priority structures trade strict FIFO for speed and still produce correct parallel shortest‑path results by tolerating extra reprocessing; practical toolkit: multi‑queue with random two‑choice extraction, per‑thread insertion batching, temporary locality and NUMA‑aware queue assignment, which cuts lock contention; a more involved design—steering multi‑queue with steal buffers and epochs—uses per‑thread d‑ary heaps, steal buffers, an epoch+stolen flag for safe concurrent steals and shows better throughput than classic multi‑queue and often beats lockless IBM/PMod schedulers while keeping work increase low.
AI-written summary · about
chapters (7)
- 0:00Relaxed data structures
- 4:21Parallel Dijkstra challenges
- 13:04Relaxed priority queues
- 26:32Multi-queue optimization with batching
- 37:28Steering multi-queue design
- 59:39Complexity and practicality
- 1:01:06Summary and Q&A
related talks
48m“Is Parallel Programming still hard? PART 2 of 2”
55m “High Performance C++ Concurrent Transactional Data Structures"
01h 18m“Work Stealing"
46mMulti-Priority Graph-Based Parallel Execution Using Taskflow
01h 08mBetter Code: Concurrency
01h 05mAn Interesting Lock-free Queue - Part 2 of N
01h 07mBuilding Robust Inter-Process Queues in C++
01h 08mThinking Outside the Synchronisation Quadrant