The Legion Parallel Programming System
legion.stanford.edu
legion.stanford.edu
Didn't post this, but am one of the authors of Legion (more on the language side / Regent [1]). Feel free to ask me questions. I do think our front page does an especially bad job of explaining what we do, so I'm sure you'll have some. :-)
Which sounds pretty good to me. I'm writing a very basic version of future + task based scheduling for Chess AI, so I think this methodology is very powerful. I haven't dug very deeply into your work, but it seems like you guys have a good idea of what you're doing.
Seems like a cool project. Unfortunately, my home computer is AMD Vega64, so I won't be able to use Legion. But its still got a methodology that I personally think, is really cool.
---------
The silly example that "sold" me on task-based scheduling was Intel's "Stupid Fibonacci" example. I think you guys should put a similar example on your website: https://software.intel.com/en-us/node/506102
Stupid parallel Fibonacci is basically fizzbuzz, every programmer should understand it. And while its not very useful, you should be able to represent it in Legion in less than 10 lines of code.
EDIT: I see that your code actually has Fibonacci. Good :-) https://legion.stanford.edu/tutorial/tasks_and_futures.html
Well, I have nothing to contribute. Good stuff.
https://github.com/StanfordLegion/jupyter-regent/blob/master...
But anyway, the reason we don't really push fibonacci is because it (a) doesn't really expose the unique features of Legion/Regent and (b) if you write it naively, probably performs even worse than naive fibonnacci implementations on other parallel frameworks.
The real secret sauce in Legion is being able to load a mesh or whatever, partition it a couple different ways (e.g. for ghost cells vs the main computation) and then launch tasks without needing to think about what needs to be updated where to get the data to the right place or copying data down to the GPU and back.
We will add AMD GPU support eventually, since Frontier is going to be a GPU machine, but probably not on a time scale that makes any difference to you.
I'm not familiar with all of the systems you mentioned, but I'd think of it more as a Spark or Dask or MPI competitor and less as a job scheduler. We have tasks, the runtime automatically identifies dependencies between tasks based on what data they use, and the support for describing different partitionings of data is very expressive.
[1]: https://legion.stanford.edu/bootcamp2017/ (updated source code here: https://github.com/elliottslaughter/regent-tutorial)
[2]: https://legion.stanford.edu/tutorial/ (there's also a parallel version in Regent which I think is easier to read, but has less descriptive text: http://regent-lang.org/tutorial/)
Most of our users are in HPC doing simulations of PDEs (e.g. [1]), but we've also got a deep learning framework [2] and a graph processing engine [3].
[1]: https://www.osti.gov/biblio/1410202-s3d-legion-exascale-soft...
[2]: http://theory.stanford.edu/~aiken/publications/papers/sysml1... (github: https://github.com/flexflow/FlexFlow)
[3]: https://legion.stanford.edu/pdfs/vldb2018.pdf (github: https://github.com/LuxGraph/Lux)
We started around 2010-2011. The project immediately prior to this was called Sequoia[1] (published on 2006, probably started a couple years prior).
[1]: http://graphics.stanford.edu/papers/sequoia/sequoia_sc06.pdf
It’s more systems/HPC community, and a couple of decades old, so I don’t think the name reuse will cause much confusion.
Any thoughts on differences in your approaches?
https://www.usenix.org/conference/atc19/presentation/meiklej...
Partisan is an actor model runtime that appears to be (mostly?) compatible with Erlang. The main selling point of Partisan is optimizations which improve the performance of actors, which are impressive, but is orthogonal to many of the issues Legion attempts to address.
In particular Partisan seems to mostly take the actor model as is (in fact this seems to be a goal so that their runtime can handle existing Erlang applications). That means it's going to have all the usual pitfalls that can occur with actor based programming. There is a class of bugs that shared-nothing actors make impossible (i.e. concurrent access to shared state). But there is (in my view at least) a much larger class of concurrency bugs that conventional actor models do not attempt address at all. (I am sure you can find some actor model implementations that attempt to address this, but this effort does not appear to be one of them.)
In contrast, Legion's semantics are sequential. You cannot write a data race, deadlock, or any other sort of concurrency bug because the code behaves as if it were executing literally sequentially. Any parallelism that occurs in the execution is guaranteed by the runtime system to preserve the original sequential semantics of the program. Any access to distributed data is guaranteed to be local because the runtime will move it for you before the task starts executing.
To put it another way, in Legion you have to explicitly think about how to divide up your program (tasks) and data (regions/partitions), but once you do that the parallelism/distributed memory is implicit. In contrast, nearly all of the common explicitly parallel programming models make one or both of the first two implicit (though the user still has to think about it, because data structures have to be divided e.g. between actors), and require the user to explicitly do the last one (which is where concurrency bugs creep in).
One fundamental difference with Legion is that Chapel is explicitly parallel. As I noted in another comment, Legion has sequential semantics [1]. As far as I know there is no subset of Chapel that has sequential semantics while still retaining the ability to execute code in parallel. This means there are classes of bugs that Legion avoids that Chapel cannot.
On the other hand, Chapel lets users write code that is pretty high-level while still retaining the ability to do distributed execution. In particular, Chapel's forall loops can be combined with domain maps to get distributed-memory execution of code that, if not literally sequential, still looks pretty darn nice.
Domain maps in Chapel provide the ability to specify how data is distributed around the machine in a way which is decoupled from e.g. the forall loops over the data. There is a surprising amount of subtlety to this, and I admit I initially underestimated exactly how important domain maps are in Chapel. In particular, domain maps are permitted to make internal copies of remote data, which means that domain maps can be responsible for ghosting/halo exchanges. Because domain maps are user customizable, this essentially permits the user to put their low-level data movement code in the domain map, while keeping the rest of the code clean and high-level.
The closest analog to domain maps in Legion would be partitions. But in many ways they're completely different beasts. Partitions in Legion offer a similar amount of expressiveness, in the sense that the user can specify partitions to contain any subsets of the data. But in Legion, data movement in fully automatic. Legion does not permit, or require, the user to write custom data movement code of any kind, no matter how complicated the partition is. Also, partitions are not fixed to specific locations in the machine but can be dynamically rebalanced. Of course all of this is technically possible in Chapel, because domain maps are user-customizable, but none of it comes out of the box and as far as I know this sort of behavior is underexplored in Chapel in general.
As a final note I'll mention that the Chapel folks are really friendly. I've been doing some comparisons with Chapel recently and I found it relatively easy to get help on issues I was having, and that certainly has not been true of all the systems I've been using!
I've been thinking about a fully declarative language (logic-based like datalog/prolog or functional) with an orthogonal optimization layer. This seems to go in that direction, but still based on an imperative base and focused on parallelism. Are there other languages doing this logic/optimization split?