futures in Chapel

[mppf]

This issue is for tracking the feature request for 'futures' in Chapel.

Some work towards adding futures was completed around 2013. See slides summarizing that work here:

http://chapel.cray.com/presentations/SC13/03-futures-imam.pdf

Here is an email thread about that work:

https://sourceforge.net/p/chapel/mailman/message/30815892/

Here is the branch containing that work:

http://svn.code.sf.net/p/chapel/code/branches/collaborations/futures

(and here is a link to some earlier versions of prototype code: https://sourceforge.net/p/chapel/code/21386/tree/branches/collaborations/futures/test/release/examples/futures/ )

Here is a discussion on chapel-users about retiring 'single' and replacing it with 'future'. https://sourceforge.net/p/chapel/mailman/chapel-users/thread/alpine.LNX.2.00.1309131418050.327%40bradc-lnx.us.cray.com/#msg31409942

Here are the tasks that were outlined to complete 'futures' support in the language:

• [ ] make sure the old proposal / strategy is still reasonable and reasonably well supported
• [ ] add future types and implement begin expressions (ie compiler support for begin expressions) e.g. const f: future int = begin computeSomeNumber(); f.read();
  • [ ] implement future as a library using sync variables
  • [ ] add automatic coercions from future(T) to T. Compiler adds type inference support and generates calls to read. E.g. const x = begin foo() + begin bar().
• [ ] add some form of statement-block expressions. The goal here is to enable putting multiple statements inside of begin expressions. One possibility is to use a syntax like ({ a; b; c; }) which would enable examples like const x = future int = begin ({ var a = computeSomething();a; }).
• [ ] compiler/runtime optimizations. Avoid task creation for short-lived computations. Enable a data-driven task runtime to make use of futures information.

[bradcray]

Two quick notes that are quite likely mentioned in the threads Michael points to above, but which always stick in my mind on this topic:

• In the expression context, 'begin ' should be inferred by the compiler to be of type 'future T'. Michael's examples above imply this, but I wanted to make it concrete.

• I think there's a semantic/optimization question regarding the interpretation of:

  var x = begin foo() + begin bar() + begin baz();

  Naively, this seems to be saying "create three tasks to compute foo(), bar(), and baz() simultaneously and add their results when they're done." But given current Chapel semantics (and/or implementation), it is probably more correct to think of it as:

  var t: future int = begin foo() + begin bar() var x = t + begin baz();

  which suggests that only two tasks would be running at a time, not three. To get the original effect, you might need to write:

  var t = begin baz(); var x = begin foo() + begin bar() + t;

  or maybe:

  var x = begin (begin foo() + begin bar()) + begin baz();

  ?? I think this is acceptable, just counterintuitive. At the same time, I'm not crazy about going down the road of "Chapel doesn't guarantee the evaluation order of operators like +"...

[mppf]

Re. how many tasks are run with

var x = begin foo() + begin bar() + begin baz();

could the compiler to start all of the begin expressions in a statement before doing the rest? i.e. translate it to

var t1 = begin foo();
var t2 = begin bar();
var t3 = begin baz();
var x = t1 + t2 + t3;

You'd just apply the rule recursively for nested begins.

That seems like a workable strategy to me (but I might be missing some case).

[bradcray]

It arguably could, that'd just be very different evaluation semantics than the language currently defines/implements, so would require some careful thought and specification about what the precise rules are -- e.g., on what granularity are begin expressions hoisted, and where are they hoisted to, particularly in the case of complex expressions and statements?

[mppf]

I just realized that it's not clear how the Futures module could support "task intents" for futures (i.e. selecting between 'in' and 'ref' passing in to the task). I think a begin expression would handle that in an more obvious manner (or at all).

Another difference with the Futures module is that there, futures have input and output. I think the begin expression proposal has futures that return something but that don't take in input explicitly (ie they don't have arguments).

[bradcray]

While reviewing a new parallel pidigits implementation today based on this version: https://github.com/bradcray/chapel/blob/e35d629a399aaef7aa8ffd5eea23a6c9f34eb5ef/test/studies/shootout/pidigits/bradc/pidigits-blc.chpl we discussed that this would be an interesting case to write with futures where each place where the main() procedure sets a task free to compute, it would use a begin expression to kick off the future; and then each place where it waits for that task to complete, it would block on the future variable result instead. While it's not clear whether this version would be as competitive as a version like the one in the PR that keeps tasks running the whole time, it definitely seems like it would be a bit more elegant and, at the very least, something that should be expressible in Chapel.

[Tagging @ronawho , @jhh67 , @aconsroe-hpe , and @bmcdonald3 on this since they were at the meeting, and @e-kayrakli since he would've probably enjoyed being there]

[aconsroe-hpe]

I find these futures very interesting because it is more powerful than a cobegin. Some of the above pidigits could use cobegin instead of the dedicated tasks, but only where the parenthesis match so to speak (which is the whole point of cobegin, all tasks inside have the same start and end time). A future lets you express these overlapping tasks in a pretty nice way.

Another place that cobegin falls down for the above is that one of the tasks gets unblocked inside the for loop. I think a future could work in this case, but maybe you'd need to reassign the future?

var myfut: future int;
for i in 0..#100 {
  if i % 10 == 0 then myfut = begin computation(); // would it be an error to assign to an already full future?
  if i % 10 == 9 then writeln(myfut.get());
  // ...
}

Another optimization that the above pidigits can do is to spawn a long lived task that gets reused. I wonder if you could take a block of code with multiple futures and statically schedule the tasks. You may have to create more than one instance of a task (as is done with pidigits with two multiplier tasks). I think you end up in a situation where the tasks have to be non-reentrant. But maybe this is all moot if the tasking layer was good enough to handle this at runtime.

Its also appealing to think about taking some existing code, pepper in some begin futures, and get a fine grained parallel program out!

[ronawho]

Not sure what all it supports, but note that a package Futures module was added in 2017 -- https://chapel-lang.org/docs/modules/packages/Futures.html

[bradcray]

I wonder if you could take a block of code with multiple futures and statically schedule the tasks.

At a sniff, this sounds halting problem equivalent-ish to me in the general case, though it may be possible for simple cases.

[aconsroe-hpe]

I wonder if you could take a block of code with multiple futures and statically schedule the tasks.

At a sniff, this sounds halting problem equivalent-ish to me in the general case, though it may be possible for simple cases.

If it's a sniff, wouldn't it smell like the halting problem?

I see more of a practical connection with register allocation and live variable or reuse analysis. I think we want to know if every future is acted on as write-then-read so that the output location and task can safely be reused (and dedicated).

[bradcray]

I see more of a practical connection with register allocation and live variable or reuse analysis. I think we want to know if every future is acted on as write-then-read so that the output location and task can safely be reused (and dedicated).

The thing that seems challenging to me, based on the pidigits experience (like the begin + sync example here), is the interaction with conditionals and looping—needing to know which tasks are started and stopped where in order to statically schedule them. But you may be right (and arguably, that rewrite isn't close enough to a future-based version to serve as an indicator of anything).