Implicit Pipelining with Dynamic Events

[rachitnigam]

(Moved from #27)

In Filament, components are implicitly pipelined. For example, in the following component can execute in a pipelined fashion:

component MultAdd<G>(
    @interface[G, G+1] go_G: 1
    @[G, G+1] left: 32,
    @[G, G+1] right: 32,
    @[G+1, G+2] acc: 32
) -> (
    @[G+1, G+2] out: 32
) {
    M := new Mult;
    A := new Add;
    m0 := M<G>(left, right);
    a0 := A<G+1>(m0.out, acc);
    out = a0.out;
}

Since the interface for G specifies that it may trigger every cycle, the Filament type checker must check that repeated re-execution is safe.

Safety is checked is assuming that G will trigger any time after its delay, in this case 1, and showing that no re-execution of the pipeline after G's delay would conflict with the current iteration.

Pipelining with Dynamic Events

Consider the following component signature:

component Dyn<G, L>(
    @interface[G, G+3] go_G: 1,
    @interface[L, L+1] go_L: 1, ...
) -> ( ... ) where L >= G+3 { ... }

The interface specifies two events G and L and provides an ordering constraint between them, L >= G+3. The ordering constraint requires that any called of the component ensures that L arrives at least 3 cycles after G does.

In order to ensure safe pipelining, we have to reason about the retriggering behavior of both G and L and ensure that their delay do not violate the constraint on the interface. As provided, the interface is incorrect; here is an trace of events that is accepted by the interface but violate the constraint:

1. Cycle 0: $G_0$ triggers
2. Cycle 3: $G_1$ triggers, $L_0$ triggers
3. Cycle 4: $L_1$ triggers

Note that this trace is accepted by the delay specifications for $G$ and $L$ since $G_1 - G_0 = 3$ and $L_1 - L_0 = 1$. However, it violates the constraint on the interface since $L_1 \ngeq G_1 + 3$.

Restricting Interfaces

The key problem is that the delay specification for G and L do not constraint the event in such a way that subsequent retriggers obey the constraints of the interface. Ideally, we could change the delay specification such that the constraint holds. We would like trace history to look something like:

G0 --> G0+3 --> L0 --> G1

This implies that the delay for G must be dependent on the event L occurring; G may not retrigger unless L has triggered:

@interface[G, L] go_G: 1

Next, we need to ensure that L1 obeys the interface constraint:

... --> L0 --> G1 --> G1+3 --> L1

which is the same as (where dG is the delay for G):

... --> L0 --> G0+dG --> G0+dG+3 --> L1

This means that the constraint on the delay for L looks something like:

L + dL >= G + dG + 3

This shows that the delay for L depends on the delay of G; however, the delay of G is itself dependent on L.

TLDR: The history of L and G are interdependent; in order to figure out when the next L should occur, we need to know when the last G occurred. In other words, the @interface for both events need to be able to talk about the trace of the other event directly so that the constraint can be obeyed.

The Problem

The problem here is the constraint between G and L. By specifying it, we relate the traces of events in some manner, and we need the delay specifications to encode this information. Since interfaces only talk about delays, there is no way to relate histories of multiple events.

At this point we have two solutions:

1. Extend the delay specifications to handle more general histories
2. Disallow constraints over events in the language

I do not think (1) is worth doing. This is because even if we can make it work, this way of relating dynamic events together does not correspond well with dynamic pipelines. I think the right way of doing this probably requires some mechanism of specifying type-level "back pressure"; the retrigger of G and L is not dependent on the two events but rather the availability of the resources. The resources should be able to apply back pressure to the rest of the circuit to stall events from arriving. Doing all of this is definitely out of scope for the first paper.

This means that the proposed solution is disallowing ordering constraints in the language.

The Fix

The proposed fix is to disallow constraints on user-level components but to allow them on primitives. For example, the register primitive is still allowed to specify the constraint:

component Latch<G, L>(
    @interface[G, L] go_G: 1,
    @[G, G+1] in: 32,
) -> (
    @[S, L] out: 32
) where L > G+1;

User-level components do not have ordering constraints, there is no way to construct a dynamic use of the Latch:

component Main<G, L>(@[G, G+1] in: 32) -> (...) {
    L := new Latch;
    l0 := L<G, L>(in); // <- no way to prove L > G+1
}

This program will not type-check since the component cannot specify L > G+1.

However, uses of such Latch that use the same event are still valid:

l0 := L<G, G+3>(in) // G+3 > G+1

Furthermore, it might still be possible to use max expression to express a limited form of dynamism in the language.