Shared Memory Parallelism in Julia with Multi-Threading - Parallel Depth-First Scheduling

Explore shared memory parallelism in Julia through this 27-minute conference talk from the Cambridge Julia Meetup in May 2018. Dive into the challenges of nested parallelism and learn about parallel depth-first scheduling as a promising solution. Discover the implementation of PDF scheduling in Julia, including the parallel task runtime (partr) and its handling of priority queues and nested parallelism. Gain insights into why effective threading models are crucial for high-performance computing and how Julia aims to overcome limitations found in existing models like OpenMP and work-stealing algorithms. Follow along with detailed examples, including matrix multiplication, to understand the space complexity issues in parallel programming. Conclude with a Q&A session discussing Julia's suitability for implementing advanced parallel computing concepts.

Welcome!.
Why we need threads?.
Task parallelism.
Data parallelism.
Julia's experimental threading infrastructure added in 2015/2016.
Successes of aforementioned threading infrastructure.
What we've learned.
Problem is not adding threads to Julia, but making them useful at every level.
Nested parallelism: parallel code calling function from a library that is also parallel.
Example: multiplying two n x n matrices.
Example: running code sequentially.
Example: you need O(n^2) space.
Example: running code in parallel on 4 cores with OpenMP, OMP_NESTED = 1.
Example: such parallel code needs O(n^3) in space.
Another way: work-stealing.
Problem: work-stealing algorithm essentially run like a serial algorithm.
Parallel depth-first scheduling.
partr -- parallel task runtime.
partr implementation.
partr -- priority queues.
partr -- handling nested parallelism.
Possible problem: we do not synchronize at each spawn point.
Why all these things are important?.
Q&A: is Julia more suitable for implementation of partr than other languages?.