either, the par block that is ready to be done

[anshumanmohan]

Consider the case where you need:

par { group_finite; group_infinite; }

where the former group finishes in some reasonable time but the latter runs forever or is perhaps dependent in some way on the former. The code above is clearly a bad idea; the par block will run forever because it will wait for both of its children to be done.

The present solution involves writing an ugly RTL-like group. This group:

• Asserts group_finite.go.
• Asserts group_infinite.go.
• Ties its own done signal to group_finite.done.

A related issue is that, in moving to low-level RTL land, we lose nice high-level constructs like invoke. We must hand-write desugared code that really should have been created for us by the compiler.

We could do with a new high-level construct, provisionally (and badly) named either, which is a lot like par. The difference is that it is done when either of its children is done.

[sampsyo]

For a tiny bit more context, @anshumanmohan and I chatted about this today and I mentioned it because the need for something like this also came up earlier, with @nathanielnrn, in the context of #1733.

[rachitnigam]

Hm, that's an interesting idea! FWIW, in other dynamically scheduled ILs, this the similar to the difference between a "lazy fork" and an "eager fork". The former forwards tokens as soon a particular child is done while the latter waits for all children to be done.

We should think carefully about the semantics of this. What happens to the go signal to the threads that weren't done? Are they immediately de-asserted? How will someone write programs where this behavior is allowed and things can be left in potentially undefined intermediate states. Also, @hackedy might have thoughts on this since he's been thinking about semantics more carefully.

[sampsyo]

Indeed, the way this would have to work is that the "loser" (the thread that runs longer) gets aborted early, by having its go deasserted at that point. So this would only be feasible if that kind of early termination could be tolerated.

In both cases where this has come up, the situation has been that one of the two threads wants to be an infinite loop: a "daemon thread" in software terms. In those situations, early termination is exactly what you want. But it's an open question whether this possibility can be tolerated by all components.

To state the obvious: while no current Calyx control statements do this early termination, it is of course currently possible to do it "structurally" (i.e., by manually assigning to a component's or group's go). AFAIK we have never made a specific rule about whether doing so is allowed.

[rachitnigam]

To state the obvious: while no current Calyx control statements do this early termination, it is of course currently possible to do it "structurally" (i.e., by manually assigning to a component's or group's go). AFAIK we have never made a specific rule about whether doing so is allowed.

Right! But all control operators very much have "run to completion" semantics which are useful when frontends generate code. Specifically, what kind of frontend generated could would tolerate early abortion? If one of the threads invokes a component, that component (and all subcomponents it instantiates) better be tolerant to being aborted. With ref cells, this gets even more component because they could be running sibling components as well.

[hackedy]

Instead of having something like either I think Calyx would be better off allowing par threads to communicate directly, without using termination as a side channel and without disturbing the run-to-completion semantics of go-done. Any problem you want to solve with either you can solve with genuine synchronization, whether it's registers with locks or unidirectional message passing or whatever. Maybe relevant are some of the comments in this slack thread from last month. https://cucapra.slack.com/archives/CLLM75W4R/p1696456536778209

I am primed to dislike either because I used an either-like construct in #1726 to construct some confusing programs. Imagine you have a stopwatch that runs forever, incrementing a register so long as its go is asserted, and you also have a program_under_test that will terminate. The program

either { stopwatch; program_under_test }

implemented clumsily in terms of groups in #1726 gives you a way to (only empirically, not semantically!) observe the timing of program_under_test. In the semantics, this apparent difference ought to be resolved by treating it as a case of nondeterminism getting resolved in two different ways, but it still seems a little gross to me.

[rachitnigam]

Since synchronization was mentioned, link to the experimental @sync operator implemented by @paili0628 last summer: https://docs.calyxir.org/lang/sync.html

[sampsyo]

I like @hackedy's example here; the "stopwatch" thread makes it very clear that it would be hard/impossible to give semantics to either in the general case. This effect might seem less bad in static land, where you can statically determine exactly when the loser gets "cut off," but in static land, our calling convention doesn't actually have a way to early-terminate an executing component (since go is only high for 1 cycle, not L). It's obviously less useful in static land anyway, because our motivating example here is an unbounded while loop.

I also like the alternative of actual synchronization. To spell it out, the alternative would look impressionistically like this:

par {
  while !stop_flag {
    do_some_stuff;
    @sync check_stop_flag;
  };
  seq {
    finite_thing;
    @sync set_stop_flag;
  }
}

That is, the two par arms are mostly independent, but they share a 1-bit flag register that instructs the while when to exit. When finite_thing finishes (which is when the either version would kill the other thread), it sets this flag. The while loop finishes its current iteration and then exits. Of course, the coordination on the flag requires synchronization, in the vein of @sync… a broader topic that would be great to return to in the future.

[sampsyo]

We had a super useful synchronous conversation about this today! A major outcome was that we liked the explicitly synchronized version of the solution to the problem, at least for the situation where the "loser" is a while loop like the above example. This situation admits a straightforward way to introduce synchronization on the shutdown flag.

We also talked about a different situation, though, which is where the "loser" is (by necessity) a single group—for example, one that needs to "block" some signal from the external world, like an AXI port. It is less obvious how to make the explicit synchronization happen there; certainly, it won't work to just use @sync as currently implemented because this synchronization can only happen before/after groups, not during their execution. In other words, while we see the path clearly for controlly Calyx, we need a way to synchronize with some structural Calyx.

This seems to inform a need for the future design of a more complete synchronization facility in Calyx: we'd like something like @sync to expose a controlly interface on one "end" and a structural interface on the other end. The impressionistic Calyx code I brought up looks like this:

par {
  blocking_stuff;
  seq {
    finite_thing;
    @sync set_stop_flag;
  };
}

That is, there is just one point where it makes sense to put @sync, on the group that sets the termination flag. We also want blocking_stuff to observe this flag, safely, without races. Very roughly speaking, it would be great if the @sync somehow referred to a structural sync_reg that the other group can observe. Let's call that synchronized register sr; we would write the long-running group like this:

group blocking_stuff {
  ...
  blocking_stuff[done] = <signal from outside world> | sr.out;
}

In this setting, sr would look like a std_reg, but with the added superpower that it is legal to "race" on it (i.e., access it even when the other thread writes it), and that reading it adds a cross-thread edge to the happens-before graph for the execution.

This more sophisticated synchronization thing is obviously a much bigger topic that is a project unto itself, but I think we all agreed we prefer that prospect over either as proposed.

[anshumanmohan]

Thank you Adrian for the summary of our meeting! I'm closing this thread.