Shared memory parallelism in Julia | Kiran Pamnany | Cambridge Julia Meetup (May 2018)

Kiran Pamnany explains why traditional fork-join and work-stealing models fail to nest parallel code effectively and presents depth-first scheduling in Julia.

A fast, efficient scheduler for parallel programming Parallel programming is essential for high performance on current processor and system architectures. Many libraries include carefully tuned parallel implementations of their functionality, but using these in a parallel program requires effective nested parallelism. We show that existing threading models such as fork-join (OpenMP) and work-stealing (Cilk/TBB/Go) fail to nest parallel code effectively, making these highly tuned parallel libraries near useless to parallel programs; a state of affairs we do not wish to inflict on Julia. A decade-old idea, parallel depth-first scheduling, offers hope. We show the promise of this approach and report on our implementation of PDF scheduling in Julia. Speaker: Kiran Pamnany is a research scientist in Intel’s Parallel Computing Lab. His research interests include programming models, high performance computing and compilers. He is the author of Julia’s existing experimental threading runtime as well as Julia’s forthcoming parallel task runtime, and is one of the people responsible for Julia joining the petaflop club with Celeste. He has a PhD in computer science from Brown University. Time Stamps: Contents 00:00 Welcome! 00:28 Why we need threads? 01:37 Task parallelism 02:43 Data parallelism 03:35 Julia's experimental threading infrastructure added in 2015/2016 04:35 Successes of aforementioned threading infrastructure 05:35 What we've learned 06:25 Problem is not adding threads to Julia, but making them useful at every level 06:59 Nested parallelism: parallel code calling function from a library that is also parallel 08:18 Example: multiplying two n x n matrices 09:29 Example: running code sequentially 10:10 Example: you need O(n^2) space 10:27 Example: running code in parallel on 4 cores with OpenMP, OMP_NESTED = 1 11:26 Example: such parallel code needs O(n^3) in space 11:37 Another way: work-stealing 12:47 Problem: work-stealing algorithm essentially run like a serial algorithm 13:57 Parallel depth-first scheduling 15:52 partr -- parallel task runtime 17:15 partr implementation 18:30 partr -- priority queues 21:23 partr -- handling nested parallelism 23:22 Possible problem: we do not synchronize at each spawn point 24:13 Why all these things are important? 24:59 Q&A: is Julia more suitable for implementation of partr than other languages? S/O to github.com/KZiemian for the video timestamps! Want to help add timestamps to our YouTube videos to help with discoverability? Find out more here: github.com/JuliaCommunity/YouTubeVideoTimestamps Interested in improving the auto generated captions? Get involved here: github.com/JuliaCommunity/YouTubeVideoSubtitles