leader/follower improvements aka leader/follower 2.0

[mppf]

As a Chapel user, I'd like to be able to easily implement leader/follower iterators for my types and combine leader/follower iterators from different types.

This epic tracks leader-follower areas of improvement. (Hopefully over time these are split into their own issues to discuss solutions but I'm just putting them here to save time).

What are known issues with leader/follower?

Main Issues

• follower doesn't know the shape of the entire iteration space.
  • one way to do this would be with a pre/post coordination between a leader and its followers. Another might be with additional arguments. The pre/post coordination might include declaring or checking for compatability with a particular rank.
  • This presents a challenge for iterators provided by Random, for example, because these would like to generate a different random number per element, but probably would want to generate the same random numbers for an domain {1..n} and a domain {2..n+1}. (and followThis arguments are always zero based today).
  • Additionally certain optimizations within follower iterators would benefit from knowing what is going to be iterated over.
  • GPU integration would also benefit from knowing the entire iteration space / task layout (see CHIP 22 - section "How to pass the Execution parameters (workgroup and grid size)").
  • forall (i,j) in zip(1..4, 1..5) { ... } does not result in an error today
• serial for loops that zip don't use leader/follower iterators right now (issue #13665). This prevents the loop bodies from including on statements. Correction: As of PR #13664, this is supported, but we still can't zip serial iterators that yield from within on-clauses with other serial iterators.
• the syntax for declaring the different iterators (serial, standalone, leader, follower) could be improved upon. The param tag field might seem awkward to users. Maybe the various iterators should be methods on a common type rather than iterators that share a name and argument types. #13256
• zippering between different types isn't really defined yet #11504

• can't zipper with an unbounded iterator, e.g. (#13239)

  iter unbounded() {
    for j in (1..) {
       yield j;
     }
   }
  
   for (i,j) in zip(1..100, unbounded()) {
     writeln(i,j);
   }

  • would like to be able to create iterators that are sensitive to or tolerant of shape mismatches
  • iterators aren't really first-class in a documented way (want to pass around, call hasNext, etc, even though the implementation does these things). Note that attempts to return an iterator currently create an array. #11435
  • Defining a leader/follower this method on a data structure doesn't make it promoteable
  • shape preservation (this is at least partly implemented now)
  • shape declaration #11524
  • Multidimensional zippered iteration (or promotion) kills performance

    13147

  • multidimensional array zippering creates single loops (over iterator objects) rather than nested loops (reflecting the multidimensional iteration)
  • it's difficult for the compiler to fuse leader/follower loops
    • perhaps a separate phase to create tasks would help here
  • see also comments below from leader/follower paper

Other related issues

• "shape" of an iterator / promoted expr / forall-expr a user-facing feature #10359
• allow promotion of iterators? #11879
• serial/parallel iterator forwarding feature #5255
• myIter().type to be myIter's yield type? #5578
  • Currently querying the yielded type requires running the iterator

[mppf]

@vasslitvinov, @daviditen FYI. I hope we can record thoughts about leader/follower design problems here and link to issues discussing solutions.

[mppf]

The leader/follower paper has some thoughts in its Future Work section:

One ... limitation is related to zippered iteration over multidimensional data structures. Because zippered serial iteration is implemented via methods on an object, the multidimensional control flow is pushed into the object’s single advance method,which is then zippered with all of the other objects’ methods in a 1D loop. This results in a suboptimal control structure compared to the loop nest a programmer would manually write for a multi dimensional zippered iteration. To that end, we anticipate extending the leader-follower interface to support distinct iterators for each dimension. Multidimensional loop nests would then be generated by zippering each dimension’s iterators separately.

A second concern relates to parallel loop startup overhead.Since each forall loop leader creates parallelism, tasks are created and destroyed for each forall loop. By breaking the leader iterator into two calls—one to create tasks, and the other to assign work to them—the compiler could fuse multiple forall loops, inserting appropriate synchronization to maintain correct semantics while reusing the same tasks.

In both of these scenarios, there will be a need to share state between the collection of iterators that define the leader and followers. To that end, we anticipate moving to more of an object-based framework for leader-follower iterators in which the various iterators would be defined as methods fulfilling an iterator interface. This would also solve some of the awkwardness of grouping iterators via overloading and the compiler-provided tag argument.

[bradcray]

It's not a publicly available document, but for those on the HPE team, 2014-04-21-leader-follower.txt has notes on this general topic as well. Let me know if you need a pointer to it.