Guarantees for Static Timing

[rachitnigam]

By default, Calyx works with a latency-insensitive model of computation and leaves it to the compiler to discover latency information. The compiler can then exploit this information to generate more efficient and performant programs. Long-term, we should treat this as Calyx's "killer feature" and orient the design of the language and the compiler towards it.

To this end, we should work on making latency sensitivity a first-class concept in the language. There are various upgrades to the language that we should consider such as upgrading static to a keyword and defining static groups and static components, all of them begin with a stronger guarantee of how static programs are scheduled.

seq

For the following program:

seq { @static(K) one; @static(L) two; @static(M) three }

The compiler must guarantee that the execution takes exactly K + L + M cycles and that two starts executing on cycle K+1 and three starts executing on cycle K+L+1.

par

A par program must ensure that all its children start executing in the same cycle:

par { @static(K) one; @static(L) two; @static(M) three; }

The compiler must ensure that one, two, and three all start executing in the same cycle and that the program takes exactly max(K, L, M) cycles.

Note: We have not defined whether the threads in par need to start executing in the same cycle as the par program itself. Is there any reason to retain this flexibility?

if

The if program must ensure that the then and else branches start executing in the same cycle:

if port { @static(K) then; } else { @static(L) else; }

The program takes max(K, L) cycles and either branch is guaranteed to start in the same when the if program starts.

Note: We do not define the semantics of if-with.

while

while port { @static(K) body; }

The scheduling guarantee of while extends to repeated executions. If the body takes K cycles, then the next iteration must start on cycle K+1 and the program takes n*K cycles where n is the number of iterations.

Note: We do not define the semantics of while-with.

[sampsyo]

Nice! Having these defined for the "static subset" of Calyx seems like a really good idea. Perhaps this should become a docs page once we resolve the unknowns?

Here are a few scattered thoughts on the questions within:

We have not defined whether the threads in par need to start executing in the same cycle as the par program itself. Is there any reason to retain this flexibility?

I'm not 100% sure what this would mean… since the entire program takes exactly max(K, L, M) cycles already, it seems like there is no "room" for there to be any extra cycles owned by the par but not by any of its children. So I think the existing constraints imply that all of one, two, three, and the par itself begin on exactly the same cycle. (I would hazard an argument that having this flexibility for non-static par is nice but is not something we want for static par.)

The program takes max(K, L) cycles and either branch is guaranteed to start in the same when the if program starts.

Are we sure we want the whole thing to take max(K, L) cycles? Or should it take either K or L cycles, depending on the condition? (This would of course mean that the if itself does not have a unique static latency. That's probably useful in some circumstances, but it seems like we would at least want an option for the other behavior, i.e., making the if itself dynamic even when the children are static. This would make an if more like a while that runs either 0 or 1 times.)

[rachitnigam]

You could make if take the smaller of the two latencies but that moves you into the real of dynamic scheduling; if you can't rely on the FSM to transition after a predictable number of cycles, the surrounding context needs to handle it using some form of non-static signaling.

Also yeah, agreed about the par stuff.

[rachitnigam]

I thought about this more and realized that even if you could make the two branches execute faster/slower, you might not want to do that so that users can have a predictable model of when successors to the if are scheduled. This is important if, for example, you want to synchronize across threads.

[sampsyo]

IMO that's part of the same essential trade-off here: predictability (both for human understanding and for efficient synchronization) is a consequence of static scheduling. So it seems like there is a trade-off in how to compile if: one option gives you static scheduling but perhaps needless delays, and the other gives you dynamic scheduling but no wasted time in the presence of imbalance. Given that this is a trade-off with no clear one-size-fits-all winner, maybe it makes sense to support both options somehow (via an attribute)?

[rachitnigam]

Note that the way we've defined the semantics for par means that the threads are allowed to synchronize by assuming specific timing behavior in other threads. This means that there is no simple way to turn a @static par into a par anymore; you'd need to insert @sync by analyzing which writes flow into which reads before removing the @static.

This also indicates an inverse transformation from non-static par with @sync into @static par that does not use @sync anymore which is probably the more useful direction to go in and something @paili0628 might want to think about implementing.

[sampsyo]

Indeed, heartily agreed! Seems super interesting.

For posterity, and to eliminate confusion: I believe the phrase "there is simple way" should contain a "no".

[rachitnigam]

I'm starting to realize that precise timing guarantees might be fundamentally in tension with the isolated, compositional nature of groups. Consider this program:

@static(3) seq {
    @static one; @static two; @static 3;
}

This implements a seq that is expected to take exactly three cycles. We'll generate something like this to implement the schedule:

@static(3) group tdst {
    one[go] = st_fsm.out == 2'd0 ? 1'd1;
    two[go] = st_fsm.out == 2'd1 ? 1'd1;
    three[go] = st_fsm.out == 2'd2 ? 1'd1;
    fsm_incr.left = st_fsm.out;
    fsm_incr.right = 2'd1;
    st_fsm.in = st_fsm.out < 2'd3 ? fsm_incr.out;
    st_fsm.write_en = st_fsm.out < 2'd3 ? 1'd1;
    tdst[done] = st_fsm.out == 2'd3 ? 1'd1;
}

The FSM simply counts up to 3 and marks the group as done. Pretty great stuff. However, what happens if the group is re-executed? The FSM will be set to 3 after the first execution, and the group will immediately be marked as done. We can generate some resetting logic to fix this problem:

st_fsm.in = st_fsm.out == 2'd3 ? 2'd0;
st_fsm.write_en = st_fsm.out == 2'd3 ? 1'd1;

Now we're saying that the FSM is reset the cycle after it is set to 3 allowing us to re-execute the group. Let's see if this works:

@static(6) seq {
    @static(3) tdst;
    @static(3) tdst;
}

This program will generate an incorrect result. Here is the cycle-by-cycle account:

• Cycles 0-3: tdst executes normally
• Cycles 4: tdst is attempting a reset but we've started a new execution of tdst. Because of this, one doesn't run as expected
• Cycle 5: one runs, delayed by 1 cycle
• Cycle 6: two runs, delayed by 1 cycle. Execution terminated without running three.

Whoops.

The problem is that tdst's latency is actually 4 cycles since it needs one extra cycle to reset it's internal state. We can attempt to generate the following code to remedy:

@static(3) group tdst {
    ...
    three[go] = st_fsm.out == 2'd2 ? 1'd1;  // Still executes correctly during 2->0 transition
    st_fsm.in = st_fsm.out < 2'd2 ? fsm_incr.out;
    st_fsm.write_en = st_fsm.out < 2'd2 ? 1'd1;
    tdst[done] = ??
}
st_fsm.in = st_fsm.out == 2'd2 ? 2'd0;  // Attempt reset one cycle early
st_fsm.write_en = st_fsm.out == 2'd2 ? 1'd1;

The above group can correctly execute all of its internal groups since three[go] only cares about being in the state 2 which means instead of 2 -> 3 transition, we can attempt a 2 -> 0 transition. However, now we have no way to signal that the group is done; if we say tdst[done] = fsm.out == 2'd2, that'll mean that three[go] will never be true.

This means that we cannot compile this group in a non-static context. The problem is that static groups are a fundamentally different beast from normal groups. The reason they can be timing precise is because we guarantee that we are not going to look at their done signal and instead use their static attribute to schedule them. Adopting the syntax from the brief static operator proposal, the group we actually want to generate for tdst is:

static group tdst {
    one[go] = %0; two[go] = %1; three[go] = %2;
    tdst[done] = %3;
}

Implicit in this representation is the fact that %3 cannot be treated like any other group's done signal. It only has meaning in the context of specially designated static contexts.

Owing to our old adage "problems for groups are problems for components", the following program also doesn't work correctly if the FSM for foo is generated using the first methodology:

component foo(@static(2) @go go: 1) -> (@done done: 1) { ...}
component bar {
    cells { f = foo(); }
    wires {}
    control {
        @static(4) seq { @static(2) invoke f(); @static(2) invoke f(); }
    }
}

Possible Solutions

All of these problems stem from the idea that static is just a composable optimization. We can either have a composable optimization or precise timing guarantees, but not both. The following are some possible solutions to this problem:

1. Infer static for tdst groups to be +1 of the actual latency.
   1. This will require changes to how we infer timing for par blocks since threads in a par block need to be compiled into individual groups.
   2. Similarly, infer +1 timing for components with static control programs
2. Inside the tdst pass, figure out if a group is going to be used within a static context or not and generate one of the two style of group accordingly.
   1. We need to signal that when generating the latter style of groups, the done condition should not be used. Maybe we need something like std_undef to signal that the done signal is not defined.
   2. We'll still need to infer +1 timing for components unless we want to implement a whole program analysis (I don't want to).
3. Longer term: Add support for static groups and require an explicit conversion to group before using them in a non-static context.

[andrewb1999]

I think you're probably right that we need this extra cycle when composing with dynamic groups, but I think this should only be necessary for an entire static island, not for each individual group. We should in theory be able to build an FSM for an entire static island and then have the extra cycle for done assertion for the whole island. Basically instead of having a separate counter for each group you have one counter for the whole static island.

[rachitnigam]

Right, this “static island” stuff is denoted by saying that you can compose “static groups” to your hearts content within static control operators but as soon as you reach a dynamic context, you need to lower them first

[rachitnigam]

Note that in the standard go-done interface, you can never run the same group/component in consecutive cycles because we require that go and done are never asserted at the same time. This means that even for a single cycle group/component, we'll have the timeline:

• Cycle 0: go is asserted
• Cycle 1: done is asserted
• Cycle 2: go is asserted again

Because of this known one cycle delay, the exact same resetting logic in tdcc is correct–resetting the FSM in the cycle when done is asserted is safe because we know that go is not going to be asserted at the same time

[sampsyo]

I think this is a super interesting observation! To record a couple of additional "twists" that we discussed synchronously:

In my view (and I think in everybody's), the main issue here is about control transitions between static land and dynamic land. In other words, it's about composition of control: how you take a smaller control program and "call" it to build up a larger control program. If we were building a purely static or purely dynamic IR, this would not be an issue.

In that light, consider all the different "orientations" for how one control statement could dispatch to another. In these scenarios, imagine that we have separately compiled a target control program (as a component), and we now want to invoke that from a freshly-compiled context control program (this separate-compilation setup is meant to force the issue into the most challenging setting, where we can't resort to whole-program cheats that may be useful opportunistically):

• Dynamic context -> dynamic target ("classic Calyx"): No problem; they negotiate through the standard go/done interface. A cycle is "wasted" after the target finishes, but this is normal and the ordinary dynamic-land cost of doing business.
• Static context -> static target: The target reports its latency, so the context's control logic just has to wait the requisite amount of time after activating the target. No cycle wasted; no problem. The static target does not need a done signal at all.
• Static context -> dynamic target: This should not be allowed!! The context can't have a statically-known latency if it invokes a variable-latency target.
• Dynamic context -> static target: This is where the problems discussed in this thread arise.

To rephrase @rachitnigam's central observation above: In a dynamic->static invocation, it seems like a bad idea to rely on the static component to supply its own done signal. In other words, it seems like a bad idea to have a single, pre-compiled piece of hardware do "double duty" as both a statically-timed component (one that can start going every $K$ cycles) and a dynamically-timed component (one that calls back on a done signal when it's finished). The reason is that the dynamic-timing done signal must be asserted on cycle $K+1$, so the hardware is not truly "freed up" after the $K$th cycle!

So the critical conclusion is this: Let's stop trying to make groups & components play this dual role simultaneously. Instead, let's compile components (and analogously groups) as either static or dynamic components, but not both at the same time. A static group, when compiled, has no done signal at all; a dynamic group, of course, must have one. As a result, the calling context needs to know whether it's calling a static or dynamic group—it is not allowed to just ignore this information and just assume that every compiled component is dynamically invokable (has a done signal).

There is an analogy here to calling conventions: we want to establish two calling conventions here, a static convention and a dynamic convention. When code needs to invoke a component, it needs to know which convention to use. To invoke a component using the dynamic convention, use go/done; to invoke a component with the static convention, you must know its latency, and you assert go and then wait that latency.

Now, for dynamic->static invocations, I see two options:

• It is always possible to wrap a static component in a dynamic interface. That wrapper would just consist of a counter that waits $K$ cycles and then asserts done.
• Alternatively, caller could be required to provide the counter itself, using essentially the same strategy as the wrapper but generating it as part of the TDCC FSM for the caller.

[rachitnigam]

Great summary! I think it captures the important point which is that composing static islands with strong timing guarantees requires rethinking some of the basic assumptions in our abstractions, namely that groups can move between static and non-static contexts compositionally