Precise go/done interface

[rachitnigam]

At many points, we have informally stated the go/done interface as "go must be kept high for the duration of the execution of the component and done is set to high in the cycle after the component is finished executing."

Stated formally, we can ask: Given a component with latency L, does the go signal stay active for L cycles or L+1 cycles?

The implementation of this interface in the compiler provides two potentially* contradicting answers to this:

Structurally Invoking Components

The canonical "correct" way of structurally invoking a component is:

// Assuming has_run = 0 initially 
has_run.in = comp.done;
has_run.write_en = comp.done;
comp.go = !has_run.out;

In this program, the go signal is set to 1 for L + 1 cycles. The following sequence of events happen:

1. Cycle 0: comp.go is set to high since has_run.out = 0.
2. Cycle L: comp.done becomes high and has_run.out and has_run.write_en are set to 1.
3. Cycle L + 1: has_run.out becomes 1 and comp.go is set to 0.

Latency-Sensitive Compilation

A static annotation of a group provides the latency L of the group or the component. We use this information to transition the controller FSM without waiting for the done signal in the group.

fsm.in = fsm.out + 1; // every cycle
comp.go = fsm.out >= 0 && fsm.out < 2; // assume comp takes 2 cycles

In this program, comp.go is kept high for exactly L cycles.

Potentially Conflicting

These implementation are only potentially conflicting: it might be reasonable to say that the go signal can be 0 or 1 in the cycle when the done signal is high. After all, this extra cycle represents the coordination required for latency-insensitive compilation.

However, we need to be precise about one thing: when does setting the go signal start a "new" invocation

[sampsyo]

Thanks for writing this up, @rachitnigam; it certainly is odd! I don't exactly know how to proceed, but I thought I'd just add a tad more color to the problem as it stands (if I understand correctly):

As a base assumption, this would be a nice property to have: The go/done interface looks the same to from the perspective of a given group, regardless of its invoking context. In other words, a group knows what its "job" is when interacting with the outside world—and this job doesn't change for different settings the group might appear in.

In practice, Calyx currently only has two ways that it creates "invoking contexts" for groups: latency-insensitive FSMs (from CompileControl) and latency-sensitive FSMs (from Sensitive). @rachitnigam's argument above tries to show that a go/done interface actually behaves differently in these two settings. The consequence is that we either need a flexible definition of the go/done interface that will capture both settings, or we need to rectify the two so they behave exactly the same (and hence a simpler, less flexible go/done definition will suffice).

Concretely, the latency-sensitive case is pretty straightforward; go is high for exactly the latency of the component. The latency-insensitive case looks "off-by-one" from this perspective. We need to decide whether we like it that way, and hence we will nail down a definition that encompasses both behaviors, or we think it's feasible to rectify the two—probably by shaving off one cycle from the latency-insensitive case somehow.

[rachitnigam]

The current resolution for this is generating latency-insensitive FSM transitions like this when compiling seq:

one[go] = f.out == 0;
two[go] = f.out == 1 || one[done];