Spike: Prototype fix for issue #11428

[bradcray]

While thinking about issue #11428 a few weeks back, I began wondering if we've been overlooking a simple solution in which leader iterators would yield not just the local indices that a task should follow, but also the global indices that were being traversed. This seems like it would permit followers to do things like do size checks, update global cursors, etc. It also might obviate the need to do the 0-based densifying of the local indices that we've been doing to date. This issue proposes creating a few sample leader/follower pairs that would demonstrate this approach and its utility in addressing some of our current leader-follower limitations.

[bradcray]

My first draft of this approach does successfully handle issue #11428, but I think I was being too optimistic about its ability to help with file / cursor update challenges because while it's possible to have one follower perform the update, it's not sufficient to make sure that it does so in a way that won't conflict with reads of that cursor by other followers running simultaneously. Hmm...

One other note is that while this solution results in a size mismatch error, it does so at some arbitrary point in the parallel execution such that other iterations may be running simultaneously. This is arguably better than silently ignoring the error, but is not as nice as having the message appear cleanly at the start (or end) of the zippering.

Both of these observations suggest that maybe going back to the original ideas regarding startup/teardown negotiations between the leader and follower expressions remains the better way to proceed (where the downside is that it requires more significant changes in the code base and definition of current leader/follower types).

[bradcray]

My next thought about how we might change the interface to support these styles of checks is the following: Imagine that every zippered iteration turned from:

forall (i,j,k) in (expr1, expr2, expr3) do
  body(i,j,k);

into something like:

// pass the leader expr into a preZip() call on each of the follower exprs
ref follow1 = expr1.preZip(expr1);
ref follow2 = expr2.preZip(expr1);
ref follow3 = expr3.preZip(expr1);

// do something similar to our current leader/follower template, but using the expressions returned
// by preZip() rather than the original expressions themselves, permitting them to store additional
// state.
forall followThis in expr1(iterKind.leader) {
  for (i,j,k) in zip(follow1.follower(followThis), follow2.follower(followThis), follow3.followThis)) do
    body(i,j,k);
}

// give each of the follower expressions the chance to tear themselves down once all tasks in
// the loop are complete
follow1.postZip(expr1);  // pass the leader expr into a postZip() call on the follower expressions
follow2.postZip(expr1);
follow3.postZip(expr1);

This would give each follower expression a chance to do arbitrary computation w.r.t. the leader before and after the zippered loop while also reducing the interface requirements for the follower expression itself (i.e., note that the original expression only needs to implement preZip() while it's the thing it returns that has to implement the follower and postZip() expressions where one option would be to return itself if no additional state was required).

[bradcray]

I prototyped the fix I was thinking of and it arguably fixed issue #11428, but not in a very pretty way. Specifically, since the size check occurred during an arbitrary point in the parallel iteration, the error message would come in the middle of a bunch of iterations and then halt. Next step will be to try prototyping the next approach described above.

For reference, here's the code I ended up with:

record MyRange {
  var r: range = 1..100;

  iter these() {
    for i in r do
      yield i;
  }

  iter these(param tag: iterKind) where tag == iterKind.leader {
    cobegin {
      yield (r, r.low..#r.size/2);
      yield (r, r.low+r.size/2..r.high);
    }
  }

  iter these(param tag: iterKind, followThis) where tag == iterKind.follower {
    const (whole, part) = followThis;
    if (whole.low == part.low) then
      if (r.size != whole.size) then
        halt("Mismatch in zippered iteration");
    for i in part do
      yield i;
  }
}

var r = new MyRange(r=1..100);
var r2 = new MyRange(r=1..101);

forall i in r do
  writeln(i);

forall (i,j) in zip(r, r) do
  writeln((i,j));