Support eureka pattern (break in forall loop)

[ben-albrecht]

Currently, a break within a forall loop (known as a eureka) will generate a compiler error. This issue is intended to track the challenges in supporting this functionality in Chapel.

[vasslitvinov]

The test program added in #12815 offers a way to implement this feature:

test/patterns/eureka/eureka.chpl

Namely, each task checks its locale-private variable once in a while and exists that task if appropriate.

The eurika-ing task broadcasts to the locale-private variables on all locales.

Upon encountering a break within a forall, the compiler could add an array of locale-private variables and the checking+broadcasting code, automatically.

The only challenge I see here is to determine how frequently each task should check its locale-private variable. It is the eurikaInterval param in the above eurika.chpl. Since the locale-private variable ought to be atomic, checking it on each iteration would add overhead if the loop body is small. Choosing a large value for eurikaInterval is not ideal when each iteration takes a long time already. We could probably have a compiler heuristic to determine how "small" the body is and derive the checking frequency from that.

[bradcray]

Coming back to this after some time away, I'm wondering what an implementation of a eureka would look like that leaned on no language changes, but on task-private variables and task intents. Would it be possible, as with @ronawho's aggregators work to do this in a way that was reasonably elegant and required no compiler support?

[mppf]

Arguably, throwing an Error from a forall is a kind of Eureka. Today, the implementation doesn't try to stop the other tasks executing the forall, but we could probably try to add some kind of relatively inexpensive check there, say every 1000 iterations or something like that. I think the main question I have about that approach is whether or not the programmer should be specifying how often / when to check to see if another task in the forall has thrown. The most flexible, performant, and easiest to implement designs would do that. Also, while forall is a great use case, I think we should be thinking of a language design that supports the same pattern within coforall and cobegin.

e.g.

coforall i in 1..n {
  for j in 1..m {
    if j % 10000 = 0 {
      throwIfSiblingTaskHasThrown();
    }
    doUsefulComputationThatCanThrow(i,j); // throws when there is a desire to exit the computation
  }
}

where here I am supposing that throwIfSiblingTaskHasThrown is something we could include in the standard library (although almost certainly with a different name).

[vasslitvinov]

What if we introduce a "eureka" task intent?

[vasslitvinov]

I have a proposal: #19691

[vasslitvinov]

Here are key design and implementation issues:

• Should this feature be presented as break statement, as a predefined datatype, or both? https://github.com/chapel-lang/chapel/pull/19691#issuecomment-1106708914
• At what points should the compiler insert implicit checking for an already-occurred eureka? Should such implicit checking be for the user to opt in? opt out?
• Should the task function return (#12815) or throw an exception (#19691) when it encounters or is notified about a eureka? The former option requires more compiler modifications.
• Should the notification flags be in an array with one flag per locale (#12815; this is simpler, yet an overkill for purely-local forall loops) or in a tree-like data structure that mirrors the structure of task creation (#19691; may create lots of task-private flags where a single locale-private flag would suffice). Or blend these two approaches to get the best of both worlds?