Different Definitions of Initiation Interval

[rachitnigam]

There are two possible definitions of initiation intervals of pipelines (apologies in advance for the unwieldy names):

1. Exact retriggerability
2. Forever retriggerability

Exact Retriggerability

If $P(t)$ represents the execution of a pipeline at time $t$, then $i$ is the initiation interval if and only if s.t. $P(t)$ and $P(t+i)$ do not conflict. There may $n$ s.t. $P(t)$ and $P(t+i+n)$ do conflict.

Forever Retriggerability

If $P(t)$ represents the execution of a pipeline at time $t$, then $i$ is the initiation interval if and only if $P(t)$ and $P(t+i)$ do not conflict and there is no $n$ such that $P(t)$ and $P(t+i+n)$ conflict. In other words, once a user waits for the $i$ cycles, it can choose to retrigger the pipeline anytime in the future.

Which one to pick?

Both definitions of initiation intervals (II) seem reasonable and there doesn't seem to be any a priori consensus on which one to pick. For example, in software pipelining, the initiation interval is considered to be "the number of cycles between the launch of successive loop iterations". This corresponds to our "exact retriggerability" definition. I suspect that HLS tools subscribe to this definition as well.

In hardware pipelines, it often seems to be "the number of cycles that must elapse before instruction issue to the same unit". This corresponds to our "forever retriggerability" definition.

Without much motivation, I'm going to pick two criteria for a good definition of II:

1. Enforceability: The definition can be tractably enforced by the type system
2. Composition: The definition does not have to change in response to every internal implementation detail

Enforceability

There are two places where the definition of initiation interval is used and checked:

1. Repeated invocations of the same instance
2. Implicit pipelining of an invocation

For (1), we have something like this:

M := new Mult; m0 := M<G>(...); m1 := M<G+10>(...);

We need to ensure that m0 and m1 do not conflict. In the exact case, we must show that after G occurs, G+10-G is exactly a constant factor of the initiation interval of Mult. For n invocations, we must do $O(n^2)$ such checks.

In the forever case, we must check that G+10-G if greater than or equal to the II of the pipeline. This gives us a little more flexibility in that we can reuse an instance any time after the II of the instance. On the other hand, we might have to wait for fewer cycles in the exact case.

For (2), we need to ensure the event used to trigger an invocation, triggers in accordance to the instance's II. In the exact case, we would have to ensure that G triggers some constant factor of the II of Mult. In the forever case, we have to ensure that G triggers less often than the II of Mult. Again, forever gives us more flexibility but may require the pipeline to wait for longer.

Composition

Questions about composition are more focused on interfaces:

component Double<G>(
    @interface[G, G+100] go_G: 1,
    ...
) -> (...) {
    M := new Mult; // II = 3
    m0 := M<G>(...); m1 := M<G+3>(...)
}

The interface for G waits a 100 hundred cycles even though the pipeline takes 6 cycles. In the exact case, we'd have to have the interface line up exactly with the II of G, along with other constraints.

The more interesting case of the brittleness of the exact definition is when we use an II where there is some $n$ even though $P(t)$ and $P(t+i)$ do not conflict, $P(t)$ and $P(t+i+n)$ do conflict. In this case, a small change to the pipeline may cause the entire interface to change, creating cascading effects up the pipeline.