HN Theater @HNTheaterMonth

Does the Rust Rayon library have the issue the speaker was describing, where parallel inner loops mostly get executed serially once an outer loop is parallelized? (I assume it does, from its Cilk heritage?) Are there workarounds for when that is a problem?

Edit: Dumb mistake on my part. I was looking at the video linked in the top comment (https://www.youtube.com/watch?v=YdiZa0Y3F3c) and then I came back to this thread and thought it was the topic.

⬐ GolDDranks

What speaker you are talking about? The linked post is to Julia 1.3 release notes that doesn't mention Rayon at all?

⬐ oconnor663

Oops, dumb mistake on my part. I was referring to the video linked in the top comment: https://www.youtube.com/watch?v=YdiZa0Y3F3c

By far the most interesting part of this release is the new multi-threading features, I recommend reading https://julialang.org/blog/2019/07/multithreading for an overview, and watching https://www.youtube.com/watch?v=YdiZa0Y3F3c for a talk about some unique stuff that's being worked on with Julia's multi-threading (though the depth-first scheduling is not in 1.3 afaik).

Consider a machine with N cores running a program which spawns N parallel tasks, each of which in turn spawns N parallel tasks. Which subtasks do the cores work on initially? If it's the first subtask of each top-level task, that's breadth-first scheduling. If it's all N subtasks of the first top-level task, that's depth-first scheduling. The latter is better for high-performance computing because it tends to be the lower level libraries that are really carefully tuned to make optimal use of the machine (think BLAS/FTT/parallel sum/prefix sum). Previously it was unknown how to implement this kind of scheduling efficiently. See this talk by Kiran Pamnany for more details:

https://www.youtube.com/watch?v=YdiZa0Y3F3c

⬐ dwohnitmok

Ah I see what you mean! I really hate to pile on with the Haskell observation but the 1995 paper by Blelloch that is mentioned in that talk is exactly the heart of GHC's data parallelism as well (under the name nested data parallelism).

See slide 8 here: https://www.microsoft.com/en-us/research/wp-content/uploads/...

Later versions of Blelloch's language are referred to in other parallel Haskell papers.

FWIW I think this is nonetheless fantastic news for Julia! It's certainly poised to do great work in areas that I doubt will get any Haskell traction anytime soon (if ever) for good reasons.

EDIT: Interesting, I think Julia is taking a coarser grained approach here that breaks down a bit for irregularly balanced execution trees, but relies less on fusion (i.e. doesn't use fusion at all) which is nice. I'm curious to see how this particular implementation of the "depth first" idea goes!

EDIT EDIT: Actually I'm not sure how much fusion is necessary for GHC's approach... Time to investigate more closely. Also call out to anyone more familiar with Data Parallel Haskell to chime in. I'm getting out of my depth.

⬐ StefanKarpinski

I'm not surprised that Haskell supports this kind of parallelism, although I wasn't aware of it previously. After all, if you're going to the trouble of being that pure, why not be parallel?

checkout https://www.youtube.com/watch?v=YdiZa0Y3F3c which explains the new features of the task scheduler in a simple fashion.

Basically Julia is employing a new algorithm to schedule tasks, where traditional methods would get stuck/blocked. Essentially, if you run a job with parallel tasks and one of the threads finishes, it's extremely difficult to schedulate the free thread, since the data may still be used by the other threads that are busy; thus you need to have clever way to determine how to allocate computational resources. Julia is implementing results of a new paper on how to optimally do this.

This work has been a monumental collaborative effort and I think the eventual outcome will be pretty spectacular.

I gave a talk at an MIT Julia meetup a few months ago that the author of this PR also spoke at; I found his talk to be an insightful overview of this work: https://www.youtube.com/watch?v=YdiZa0Y3F3c