3 ms·

Julia has has the equivalent of async/await forever, except without needing to annotate anything with keywords—that’s just how I/O works. If you call a blocking

Julia has has the equivalent of async/await forever, except without needing to annotate anything with keywords—that’s just how I/O works. If you call a blocking function, it yields back into the scheduler. In Julia (as of 1.3), tasks are mapped onto multiple threads which run at the same time (in parallel) and threads that are idle can steal work efficiently. This is similar (as was said) to Cilk, TBB and Go. It is not the same as async/await in C#, which is concurrent but not parallel. What is 100% new and does not exist in any other system is that the task scheduling is depth first (rather than breadth first), which is a much better order for doing compute-heavy workloads. This ability is new and was the culmination of an Intel research project, applied to Julia.

dwohnitmok 7y ago
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.
- StefanKarpinski 7y ago
  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 https://www.youtube.com/watch?v=YdiZa0Y3F3c
  - dwohnitmok 7y ago
    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/2007/01/NdpSlides.pdf 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 7y ago
      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?
manigandham 7y ago
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.
- StefanKarpinski 7y ago
  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-doesnt-create-any-additional-threads-then-how-does-it-make-appl https://stackoverflow.com/questions/37419572/if-async-await-... https://blog.stephencleary.com/2013/11/there-is-no-thread.html https://blog.stephencleary.com/2013/11/there-is-no-thread.ht... https://blogs.msdn.microsoft.com/benwilli/2015/09/10/tasks-are-still-not-threads-and-async-is-not-parallel/ https://blogs.msdn.microsoft.com/benwilli/2015/09/10/tasks-a...
  - manigandham 7y ago
    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.
gpderetta 7y ago
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.
- leiroigh 7y ago
  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.
  - gpderetta 7y ago
    Can you expand on this or point me to a paper discussing this?
    - ddragon 7y ago
      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/ConstructiveCacheSharing_spaa07.pdf https://www.cs.cmu.edu/%7Echensm/papers/ConstructiveCacheSha...
      - gpderetta 7y ago
        Can't manage to download the file though my flimsy mobile connection, but I'm starting to understand the difference.

dwohnitmok 7y ago

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.

StefanKarpinski 7y ago
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 https://www.youtube.com/watch?v=YdiZa0Y3F3c
- dwohnitmok 7y ago
  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/2007/01/NdpSlides.pdf 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 7y ago
    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?

manigandham 7y ago

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.

StefanKarpinski 7y ago
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-doesnt-create-any-additional-threads-then-how-does-it-make-appl https://stackoverflow.com/questions/37419572/if-async-await-... https://blog.stephencleary.com/2013/11/there-is-no-thread.html https://blog.stephencleary.com/2013/11/there-is-no-thread.ht... https://blogs.msdn.microsoft.com/benwilli/2015/09/10/tasks-are-still-not-threads-and-async-is-not-parallel/ https://blogs.msdn.microsoft.com/benwilli/2015/09/10/tasks-a...
- manigandham 7y ago
  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.

gpderetta 7y ago

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.

leiroigh 7y ago
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.
- gpderetta 7y ago
  Can you expand on this or point me to a paper discussing this?
  - ddragon 7y ago
    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/ConstructiveCacheSharing_spaa07.pdf https://www.cs.cmu.edu/%7Echensm/papers/ConstructiveCacheSha...
    - gpderetta 7y ago
      Can't manage to download the file though my flimsy mobile connection, but I'm starting to understand the difference.