Regent: A Language for Implicit Dataflow Parallelism | Hacker News Reader

Regent: A Language for Implicit Dataflow Parallelism

regent-lang.org

60 pointseslaught19 comments

This looks not unlike a project I worked on several years ago, called Radian (http://www.radian-lang.org/). That venture suffered from weak interoperability with system libraries, but more so from the lack of any niche community which could take it up as a solution. I wonder if you have any plans along those lines for Regent? It's hard to get a new general-purpose language off the ground, so semi-specializing on a particular class of uses can help bootstrap a community.

Definitely agree on both counts. One of the best things I did during development was to do an internship where I could be close to potential users. Porting an existing application was also a helpful forcing function, both for the feature set of the language as well as performance.

So far I've focused on HPC users. I think focusing on a niche carries some risk that the language might be too narrow (and this is particularly true of HPC). But one thing I like about HPC is that HPC users really know what they're talking about when it comes to performance.

Was curious to checkout http://www.radian-lang.org/

It gets me a server error. Is it still online ?

I'm not sure what's up with the website. I've pushed the most recent source tree up to github:

http://www.github.com/marssaxman/radian

Thanks for the note; I'll look into it. Not sure what's gone wrong.

Author here. I'm happy to answer any questions.

It looks like you've written your own language rather than make it an embedded DSL so you can really enforce what the tasks can read and write. That's admirable - I've done research with dataflow and I always did embedded DSLs (in Scala, Ruby, Haskell and Java) and it was always a bit of handwaving and arguing that people should avoid breaking the rules. Being able to enforce it must be great.

But did you find it was hard to implement enough of a language to run useful benchmarks?

The first version of the language definitely suffered from this. (The first compiler was source-to-source targeting C++, and integrating it with anything external was always a pain.) This version is actually more like an EDSL: the compiler targets Terra (http://terralang.org/), which does codegen to LLVM. The compiler is still completely under my control, so in theory I could make it "pure" and not allow the language to do anything unsafe. In practice, I've found that it's useful to be able to do things like call C functions---that way, you don't have to rewrite 100% of every code, just the parts that need to run in parallel.

In my experience, porting a ~5k line application is usually a week or two worth of work, and usually most of that is spent trying to understand what the original code is doing, rather than writing a lot of new code. Regent code is usually fairly compact compared to the sorts of things we benchmark against (C++ and MPI codes).

The question I would have is more: what is the value-added of your own compiler here? Could the same think be done with some C++ operator overloading, and a template library, and the runtime?

Regent actually sits on top of a C++ runtime library called Legion[1] that supports very similar abstractions (tasks, regions, dynamic discover of dependencies, etc.). Unlike most runtime libraries, Legion was intended from the beginning as both a compilation target, and as something users could write to directly. So we do actually have experience building it both ways.

The advantage that Regent has over a C++ library like Legion is that the language can embody the abstractions we want to provide. With C++, there is always an impedance mismatch between how we want people to think about programming, and what C++ forces us to do. C++ code is more verbose, and the C++ type system doesn't capture all the invariants that the programming model requires.

Regent code is also a lot more amenable to static analysis. In Legion, if the system needs to know some property of the program, the user needs to supply that information. (And we're forced to trust whatever the user says---there's no reasonable way to statically analyze arbitrary C++ to validate what they've given us. At best, we can check those properties at runtime, but that isn't always feasible either.) In Regent, many of these sorts of things can be analyzed automatically, reducing the number of moving parts users have to think about. This is only possible because we've thought very carefully about what abstractions we need in the language---the type system is already on the edge of what is decidable, so adding anything more would make analysis intractable.

To be sure, C++ has its advantages too. Some users will simply never accept a new language. So, that's why we're doing both. And for those who prefer to stick with C++, that's always going to be an option.

[1]: http://legion.stanford.edu/

Thanks for the answer. I'm familiar with the "Impedance mismatch" that EDSL have in C++. If done right, it can be very limited. For example, I like what they did with NT2 (for Matlab programmer): https://www.lri.fr/~falcou/nt2/tutorial/matlab/first_example... . But it is not always possible, depending on the paradigm.

I agree that static analyses and invariant enforcement/extraction is a good reason to have a new language (I think most of the time you have to "get around" with "convention" when using C++ EDSL).

It's great to see a hybrid approach. Modern compilers seem to be much easier to build but still hard to get widely used. A cursory look at the language reminded me of JavaScript. How are you doing your static analysis from this syntax? I'm working on a visualization project and particularly interested in visualizing the data flow aspects of imperative languages, so it'd be interesting to hear how you're typing data flows in reagent. Especially since it sounds like you're targeting ports from imperative languages.

Also, do you think the type system / syntax could be implemented in something like Julia by a combination of macros and types?

In your paper, the experiments compare the generated code against code hand-written against the same API. Those experiments demonstrate that your optimizing compiler generates code that matches what experts can write - a very good and necessary comparison.

But I'm also curious about the parallelization costs, and other costs incurred by the programming model. The best way to explore those costs are to compare against an optimized sequential version that solves the same problem. Do you have any experiments which do that?

What is the primary use-case/s of this language?

Understanding what it is useful for will probably help programmers apply it somewhere.

So far I've focused mostly on HPC use-cases---generally simulations on a variety of data structures: (multi-dimensional) arrays, graphs, meshes, etc. The more interesting cases are distributed pointer data structures, and our hope is that supporting these will help Regent generalize well to non-HPC use-cases as well.

Here are a couple representative examples of what we've done so far:

* A hydrodynamics simulation on a 2D unstructured mesh (a pointer data structure): https://github.com/StanfordLegion/legion/blob/master/languag...

* A simulation of an electric circuit (a graph): https://github.com/StanfordLegion/legion/blob/master/languag...

(We have smaller toy examples that work with linked lists, trees, matrices, etc.: https://github.com/StanfordLegion/legion/tree/master/languag...)

+1 for more varied examples

This looks very similar in spirit, more modern in implementation, to the hierarchical task graph work that came from the University of Illinois Urbana-Champaign, in particular under Professor Constantine Polychronopoulos, early 1990s. Seriously. Since Monica Lam at Stanford would know this, was this a basis for the work?

Neat stuff. Are data structures up to the programmer, or are there primitives for e.g. matrices?

Matrices are easy enough:

    var grid = ispace(int2d, { x = 4, y = 4 })
    var matrix = region(grid, float)

But beyond that, most things are left to the programmer. E.g., if you want to build a mesh data structure, it's up to you to decide exactly how to build it. (Do you build a graph with pointers? Do you make it an N-dimensional grid? etc.) But my impression talking to application programmers is that most of the time, they want to make those decisions themselves anyway. A standard library might be nice, but it's never going to fit all use cases. So the first job of any language design is to make sure the abstractions are general enough to describe what users want.

Reply on news.ycombinator.com