Hum, isn't cilk-like work stealing depth first? Idle executors steal oldest ancestor and busy executors eagerly execute recursive calls while pushing parent in the local job stack?

Proof of optimality was in the early cilk papers in the '90s.

I'm sure the same algorithms made into Julia via Intel (which bought cilk in the early '00), but it is hardly new except in the 'everything old is new again'.

Also IIRC OpenMP supports (or at least allows) work stealing although at least GCC does not implement it yet.

It's all about better L3 utilization. Cilk is good for using L1 and L2, i.e. caches that are core-local, and suboptimal for using L3, i.e. caches that are shared between cores.

Can you expand on this or point me to a paper discussing this?

In the presentation posted here there was a paper citation that compared in terms of cache the model used (parallel depth first scheduling) over work stealing, but I didn't have time to read it yet.

https://www.cs.cmu.edu/%7Echensm/papers/ConstructiveCacheSha...

Can't manage to download the file though my flimsy mobile connection, but I'm starting to understand the difference.

What do you mean by depth first vs breadth first? Naively I would assume task scheduling necessarily to be depth first in some sense because you have to evaluate your tasks' dependencies first.

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

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.

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?

Isn't a blocking function, by definition, something that blocks and doesn't yield? How could the language know to automatically yield on something without annotations?

> "async/await in C#, which is concurrent but not parallel"

C# is multithreaded. Things can only be parallel if you have 2 separate paths of execution that don't depend on each other or any serial order, but you can also kick off millions of individual tasks in a single function and await them all too. These tasks are all scheduled onto threads in a managed threadpool that also share work and run at the same time. I fail to see how this is any different or less capable than the others you mentioned.

C# has threads but async/await does not use them. If you think that `async` in C# does the same thing as `@spawn` in Julia and `go` in Go, you are mistaken. It does not. There is also an `@async` macro in Julia that does what the `async` keyword in C# does (which, again, does not involve threads).

https://stackoverflow.com/questions/37419572/if-async-await-...

https://blog.stephencleary.com/2013/11/there-is-no-thread.ht...

https://blogs.msdn.microsoft.com/benwilli/2015/09/10/tasks-a...

I'm very familiar with C# and I'm not talking about threads, only that multi-threading is a basic requirement and C# has a threadpool running threads in parallel.

I said that C# also uses Tasks which are scheduled onto these threads, which is what you said Julia does, so it's the same. C# can also start new threads just as easily, or use channels like Go with the TPL/Dataflow, System.Threading.Channels, actor frameworks, Reactive Extensions, or just chaining tasks together. Other than the depth-first algorithm, it seems like C# has the same capabilities as Julia and the others, if not more, and is much more "mainstream".

Can you explain how blocking functions are automatically yielded without keywords though? I cant find any documentation on this that doesnt mention the @async macro.