Generalizing Sharing

[rachitnigam]

The Calyx compiler currently has two passes to "share" resources in some capacity:

1. resource-sharing: Responsible for sharing combinational primitives
2. minimize-regs: Responsible for sharing registers

The goal of this is to implement a new pass that generalize the above passes and allows us to share arbitrary Calyx components. The key idea is that we apply the live range analysis used by minimize-regs to compute live ranges for components and share them when possible.

Eliminating resource-sharing

The first step is getting rid of the resource sharing passing by observing that its a specialized case of minimize-regs. The latter has to compute the live ranges of registers because they are stateful and can be read after a write. In contrast, combinational primitives cannot be read outside the group using them; in other words, their live range starts and ends with the same group. We should use this insight to generalize minimize-regs to share combinational components.

Sharing Components

minimize-regs is able to share registers because they have a special interface w.r.t. state---every write completely overwrites all internal state. This means that when sharing registers using their live range, we can be guaranteed that a write makes registers indistinguishable:

x = 1
z = x
y = 2
w = y

into:

x = 1
z = x
x = 2  // completely overwrites all state
w = x

On the other hand, components are similar to java classes---they carry additional state that can be modified at every invocation. In order to share resources, we need to be guaranteed that a "write" to a component completely eliminates all state.

Defining Shareability

One open question is what makes a component safely shareable. For example, our multiplier primitive std_mult_pipe is shareable because even though it has internal state, each invocation wipes it out. This leads to two questions:

1. What is the minimum set of constraints that makes a component shareable?
2. Can we write a compiler pass to conservatively determine when components are shareable?

Interface for Shareable Components

A starting point is using an annotation of mark a component as shareable. Once we have convinced ourselves that we have a good answer for (1) in the previous section, we can use the share annotation to represent components.

[sampsyo]

Awesome; this should be fun.

About step 1 (eliminating resource-sharing): will this require any kind of additional metadata to know what we can share, or is that already all in place to support resource-sharing itself? (Would we want to put whatever annotation this involves on std_reg as well to avoid any special-casing that makes this register-specific?)

Relatedly, on "defining shareability": to state the obvious, this "shareable" criterion must at least encompass (a) combinational logic and (b) registers. But of course it will generalize that category according to some criteria TBD. While it's not a foregone conclusion, one possible way this could look is:

• There is a @share attribute that can be attached to component definitions (not instantiations), as mentioned in the last paragraph above. We put @share on std_reg, std_add, and friends that we already know are shareable.
• We write a simple/conservative @share-inference pass that guesses when it's safe to add @share to a component, probably based partially on whether all of its subcomponents are also @share or something like that. Much like our current passes that infer static timing, this pass needs to be conservative in this sense: "If the component is not safe to share, the pass must not add the attribute. If the component is safe to share, the pass may add the attribute." It is probably uncomputable to determine whether a component is safe to share with perfect precision.

[rachitnigam]

Resource sharing already uses the share attribute to express that certain components are shareable. I'm not sure if the second idea about a shareability pass quite works because you can implement a component that remembers the number of times it is invoked using just a register but it is not safe to share this component if this value is ever read. The minimize-regs pass will also fail to share registers in a version of the program where such components are completely inlined unless there is a reset group that eliminate the state in a register.

[sampsyo]

That all makes sense… by proposing a @share inference pass, I was just trying to operationalize this proposal of yours:

Can we write a compiler pass to conservatively determine when components are shareable?

i.e., let's do exactly that, and concretely what it does is introduce @share annotations conservatively. I was just guessing that this probably has to do with whether all subcomponents are shareable, but you're certainly right that there must be other criteria besides.