6 ms·

The Legion Parallel Programming System

97 points by espeed 7y ago

deleted 7y ago
[deleted]
eslaught 7y ago
Hi HN, 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. :-) [1]: http://regent-lang.org/ http://regent-lang.org/
- zitterbewegung 7y ago
  Can you give a non trivial example of using the software ? I would put that on the front page of your website .
  - eslaught 7y ago
    I agree we should put more effort into the front page (including a good amount of soul searching to figure out what we even want to be there). 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-software-direct-numerical-simulation-turbulent-combustion-complex-multicomponent-chemistry https://www.osti.gov/biblio/1410202-s3d-legion-exascale-soft... [2]: http://theory.stanford.edu/~aiken/publications/papers/sysml19a.pdf http://theory.stanford.edu/~aiken/publications/papers/sysml1... (github: https://github.com/flexflow/FlexFlow https://github.com/flexflow/FlexFlow) [3]: https://legion.stanford.edu/pdfs/vldb2018.pdf https://legion.stanford.edu/pdfs/vldb2018.pdf (github: https://github.com/LuxGraph/Lux https://github.com/LuxGraph/Lux)
- greglindahl 7y ago
  Is this Legion project related to the late 1990s Legion, which involved distributed computing for HPC and was funded by the same funding agencies and had collaborations with the same HPC organizations?
  - _kst_ 7y ago
    It appears not to be. The earlier Legion was developed at the University of Virginia. I see no reference to it on the web page or in the sources on GitHub. https://en.wikipedia.org/wiki/Legion_(software) https://en.wikipedia.org/wiki/Legion_(software)
  - eslaught 7y ago
    It's probably unrelated, but do you have a link/citation to 1990s Legion? 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 http://graphics.stanford.edu/papers/sequoia/sequoia_sc06.pdf
    - seanmcdirmid 7y ago
      It’s probably this work: https://pdfs.semanticscholar.org/416b/391e374dd3a2b656b8d13ce6a54b3d069f15.pdf https://pdfs.semanticscholar.org/416b/391e374dd3a2b656b8d13c... It’s more systems/HPC community, and a couple of decades old, so I don’t think the name reuse will cause much confusion.
- xemdetia 7y ago
  What tutorial/paper/github repo/demo do you think shows the heart of why this is the best thing? I'm just not sure what this does better than some of the other strategies that are out there that are hadoop/HDFS based, S3/lambda based, from the privs/resources style k8s/cgroups/containers, or from the task based parallelisms that you can see in Apache Airflow, Jenkins, and other job runners.
  - eslaught 7y ago
    If you have a tolerance for video, I'd recommend the bootcamp [1]. Otherwise the tutorial [2]. 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/ https://legion.stanford.edu/bootcamp2017/ (updated source code here: https://github.com/elliottslaughter/regent-tutorial https://github.com/elliottslaughter/regent-tutorial) [2]: https://legion.stanford.edu/tutorial/ 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/ http://regent-lang.org/tutorial/)
- dragontamer 7y ago
  So based on my quickie checks... is this a task-based dynamic scheduling (as opposed to static thread-based scheduling) that extends out to CUDA / OpenMP / other backends? 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 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 https://legion.stanford.edu/tutorial/tasks_and_futures.html Well, I have nothing to contribute. Good stuff.
  - eslaught 7y ago
    It's shorter in Regent :-) https://github.com/StanfordLegion/jupyter-regent/blob/master/notebooks/Introducing%20Regent.ipynb 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.
- galaxyLogic 7y ago
  So Legion comes from Standford. "Partisan" comes from Carnegie-Mellon. Any thoughts on differences in your approaches? https://www.usenix.org/conference/atc19/presentation/meiklejohn https://www.usenix.org/conference/atc19/presentation/meiklej...
  - eslaught 7y ago
    A couple of tentative comments from skimming the paper; I haven't seen Partisan before so take this for what it's worth. 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).
    - galaxyLogic 7y ago
      Thanks for the reply. Excellent
- codekilla 7y ago
  Can you compare to Chapel?
  - eslaught 7y ago
    Chapel is a bit difficult to compare to since the language is so broad. It provides something of a kitchen sink in terms of features: everything from network atomics up through forall-style parallel loops that automatically distribute their iterations across the machine. The upshot of this is that you'll never run into a point where you just flat out can't do something. On the other hand, it's not necessarily obvious how to do what you want (and do it efficiently). 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! [1]: https://news.ycombinator.com/item?id=20503368 https://news.ycombinator.com/item?id=20503368
fdserr 7y ago
where’s the EFFin sources?
- eslaught 7y ago
  https://github.com/StanfordLegion/legion https://github.com/StanfordLegion/legion
tracnar 7y ago
Interesting! 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?
- eslaught 7y ago
  Here's a free idea for anyone who's interested: I want to see a CSS for program optimization. You label your code with whatever semantics labels you want. By default they do nothing, but you can load "code profiles" to instruct the compiler how to optimize the code based on whatever machine/application specific properties you care about. This way you can add optimization hints to the code without littering them throughout the code base.
  - all2 7y ago
    Take a look at Halide, a DSL for graphics / matrix calculations.
dang 7y ago
Related from 2015: https://news.ycombinator.com/item?id=10764268 https://news.ycombinator.com/item?id=10764268
dotnwat 7y ago
The first time Legion really clicked for me--and when I could place it in context--was reading the first few chapters of the Legion thesis [0]. [0]: https://legion.stanford.edu/pdfs/bauer_thesis.pdf https://legion.stanford.edu/pdfs/bauer_thesis.pdf

97 points by espeed 7y ago

deleted 7y ago

[deleted]

Hi HN, 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. :-) [1]: http://regent-lang.org/ http://regent-lang.org/

zitterbewegung 7y ago
Can you give a non trivial example of using the software ? I would put that on the front page of your website .
- eslaught 7y ago
  I agree we should put more effort into the front page (including a good amount of soul searching to figure out what we even want to be there). 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-software-direct-numerical-simulation-turbulent-combustion-complex-multicomponent-chemistry https://www.osti.gov/biblio/1410202-s3d-legion-exascale-soft... [2]: http://theory.stanford.edu/~aiken/publications/papers/sysml19a.pdf http://theory.stanford.edu/~aiken/publications/papers/sysml1... (github: https://github.com/flexflow/FlexFlow https://github.com/flexflow/FlexFlow) [3]: https://legion.stanford.edu/pdfs/vldb2018.pdf https://legion.stanford.edu/pdfs/vldb2018.pdf (github: https://github.com/LuxGraph/Lux https://github.com/LuxGraph/Lux)
greglindahl 7y ago
Is this Legion project related to the late 1990s Legion, which involved distributed computing for HPC and was funded by the same funding agencies and had collaborations with the same HPC organizations?
- _kst_ 7y ago
  It appears not to be. The earlier Legion was developed at the University of Virginia. I see no reference to it on the web page or in the sources on GitHub. https://en.wikipedia.org/wiki/Legion_(software) https://en.wikipedia.org/wiki/Legion_(software)
- eslaught 7y ago
  It's probably unrelated, but do you have a link/citation to 1990s Legion? 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 http://graphics.stanford.edu/papers/sequoia/sequoia_sc06.pdf
  - seanmcdirmid 7y ago
    It’s probably this work: https://pdfs.semanticscholar.org/416b/391e374dd3a2b656b8d13ce6a54b3d069f15.pdf https://pdfs.semanticscholar.org/416b/391e374dd3a2b656b8d13c... It’s more systems/HPC community, and a couple of decades old, so I don’t think the name reuse will cause much confusion.
xemdetia 7y ago
What tutorial/paper/github repo/demo do you think shows the heart of why this is the best thing? I'm just not sure what this does better than some of the other strategies that are out there that are hadoop/HDFS based, S3/lambda based, from the privs/resources style k8s/cgroups/containers, or from the task based parallelisms that you can see in Apache Airflow, Jenkins, and other job runners.
- eslaught 7y ago
  If you have a tolerance for video, I'd recommend the bootcamp [1]. Otherwise the tutorial [2]. 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/ https://legion.stanford.edu/bootcamp2017/ (updated source code here: https://github.com/elliottslaughter/regent-tutorial https://github.com/elliottslaughter/regent-tutorial) [2]: https://legion.stanford.edu/tutorial/ 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/ http://regent-lang.org/tutorial/)
dragontamer 7y ago
So based on my quickie checks... is this a task-based dynamic scheduling (as opposed to static thread-based scheduling) that extends out to CUDA / OpenMP / other backends? 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 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 https://legion.stanford.edu/tutorial/tasks_and_futures.html Well, I have nothing to contribute. Good stuff.
- eslaught 7y ago
  It's shorter in Regent :-) https://github.com/StanfordLegion/jupyter-regent/blob/master/notebooks/Introducing%20Regent.ipynb 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.
galaxyLogic 7y ago
So Legion comes from Standford. "Partisan" comes from Carnegie-Mellon. Any thoughts on differences in your approaches? https://www.usenix.org/conference/atc19/presentation/meiklejohn https://www.usenix.org/conference/atc19/presentation/meiklej...
- eslaught 7y ago
  A couple of tentative comments from skimming the paper; I haven't seen Partisan before so take this for what it's worth. 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).
  - galaxyLogic 7y ago
    Thanks for the reply. Excellent
codekilla 7y ago
Can you compare to Chapel?
- eslaught 7y ago
  Chapel is a bit difficult to compare to since the language is so broad. It provides something of a kitchen sink in terms of features: everything from network atomics up through forall-style parallel loops that automatically distribute their iterations across the machine. The upshot of this is that you'll never run into a point where you just flat out can't do something. On the other hand, it's not necessarily obvious how to do what you want (and do it efficiently). 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! [1]: https://news.ycombinator.com/item?id=20503368 https://news.ycombinator.com/item?id=20503368

fdserr 7y ago

where’s the EFFin sources?

eslaught 7y ago
https://github.com/StanfordLegion/legion https://github.com/StanfordLegion/legion

tracnar 7y ago

Interesting! 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?

eslaught 7y ago
Here's a free idea for anyone who's interested: I want to see a CSS for program optimization. You label your code with whatever semantics labels you want. By default they do nothing, but you can load "code profiles" to instruct the compiler how to optimize the code based on whatever machine/application specific properties you care about. This way you can add optimization hints to the code without littering them throughout the code base.
- all2 7y ago
  Take a look at Halide, a DSL for graphics / matrix calculations.

dang 7y ago

Related from 2015: https://news.ycombinator.com/item?id=10764268 https://news.ycombinator.com/item?id=10764268

dotnwat 7y ago

The first time Legion really clicked for me--and when I could place it in context--was reading the first few chapters of the Legion thesis [0]. [0]: https://legion.stanford.edu/pdfs/bauer_thesis.pdf https://legion.stanford.edu/pdfs/bauer_thesis.pdf