Decomposing a Problem for Parallel Execution
summary
Shows concrete implementations: star counting and the n‑body simulation parallelized with Cilk Plus and compared to TBB/OpenMP; per-thread reducers remove atomic increment contention while atomics and fine-grained mutexes cause cache ping‑pong; switching from triangular to full pair traversal sometimes beats locking on many cores; a recursive tiled, cache‑oblivious divide‑and‑conquer decomposition with coarsening (thresholds ~16–64) is built and saturates CPUs; spawn cost measures ~5–10× a function call and work‑stealing adds scheduler overhead.
AI-written summary · about
chapters (36)
- 0:00Introduction
- 0:45Outline
- 1:31Principles
- 2:06Parallelism
- 3:19Silk Plus
- 6:10Counting Stars
- 7:17Parallelization
- 9:02Atomic Variables
- 13:33Reduction Operations
- 19:37End Body Problem
- 23:13General Framework
- 24:50Calculate Force
- 26:30Parallelize
- 26:54Naive Floor
- 29:25Graph
- 30:11Going parallel
- 32:09Race
- 32:41Mutex
- 34:12Atomics
- 35:45Atomic float
- 36:48counterintuitive solution
- 39:04new solution
- 39:16general problem
- 41:44cache
- 42:13why is this a specialist issue
- 42:44how to solve
- 43:48tiling
- 44:29nbody
- 45:02triangular traversal
- 46:19recursive tiling
- 47:48recursive tiling algorithm
- 48:41cache oblivious
- 52:33Spawn scope
- 56:02Data structure
- 58:52Creativity
- 59:31Exceptions
related talks
48mConsiderations for choosing the parallel computing strategy
59mParallel Programming in Rust: Techniques for Blazing Speed
59mC++ on its way to exascale and beyond
44mStories from a parallel universe
01h 06mTrue parallelism, with no concept of threads
01h 06mUtilize your CPU power
01h 03mThe Landscape of Parallelism
52mBest Practices for Concurrency