The four hard problems in FuTIL: groups, holes, visible signals, and time

[rachitnigam]

A brain-dump of various thoughts on groups, holes, and visible signals. I'm not yet sure how to fix these problems. Any solution of the form "Replace groups with components" needs to address some of these problems.

Groups

Motivation for Groups

The primary motivation for groups was to have an encapsulation for assignments that would compose nicely. Due to this, groups have the following properties:

• Groups are (mostly) opaque. We don't know/care about the assignments they perform. The opaqueness means that the compiler assumes (almost) nothing about them.
• Groups have a "calling convention". The only place groups relent on their opaqueness is the "go/done" interface which allows programs to pass control to/from them.
• Groups can "borrow" the hardware cells from their parents. This means that (1) different groups can re-use the same cells, and (2) there is no need for alias analysis (port on components can create aliases).

Group != Components

From their conception, groups have been considered separate from components. The specified distinction between the two is that a component has a control program and owns cells while a group does not.

I'm not convinced that this is distinction is meaningful:

Same expressive power

Consider this group:

group foo {
  x.in = 1; x.write_en = 1;
  y.in = 1; y.write_en = x.done ? 1;
}

vs the component

component foo(x_done: 1) -> (x_in: 32, x_write_en: 1, y_in: 32, y_write_en: 1) {
  wires { 
    group x { x_in = 1; x_write_en = 1 }
    group y { y_in = 1; y_write_en = 1 }
  }
  control { seq { x; y; } } 
}

(Instead of owning an "x" and "y" cell, the component sends signals to another component)

Group enables are already "function calls"

We've thrown around the idea for an "invoke" control operator for invoking complex components. However, a group enable is already an invoke that takes no arguments. The reason groups need a "calling convention" in the first place is because they already approximating a component.

---

Compilation Holes

Compilation holes are a mechanism for FuTIL groups to interact with the control program.

Motivation for Holes

The primary motivation for holes was the desire to aggressively inline guards of enables in FuTIL programs and eliminate any extra registers.
By and large, our implementation of holes fails to do this. This is not because we've designed holes badly but because we didn't correctly think about combinational cycles when designing the interface.
I posit that every hole can be replaced by a named wire with zero overhead.

Control-Structure Interface

We often throw around this statement:

Holes are an interface between control and structure.

This is only true because of the current uses of holes. The various other proposals to add "input" and "output" holes tells the real story: holes are just ports. This is especially true because they cannot do anything that ports can't already.

---

Visible signals

Groups provide no guarantees about what signals are visible after they execute. #207 and various other discussions about combinational groups seek to make some signals visible conditioned on done signals.

This break groups' fundamental encapsulation guarantee. By making all signals invisible, groups allows the compiler to ruthlessly change anything and everything about the group. However, if a signal is visible across a group boundary, the compiler needs to be careful.

For example, consider:

1. Group A computes add0 and guarantees that add0.out is valid for the one cycle when A[done] is high.
2. Group B relies on this behavior and uses the signal add0.out in its body because it knows that it will be valid.

In this case, if a compiler wants to change add0.out to add1.out, it has to track all the uses of add0.out that come from A (but not any other group because add0 can be used by multiple groups) and change them. This amounts to alias analysis.

---

Time

Hardware design is fundamentally different from software design because it involves an explicit notion of time. FuTIL's complexity on the edges come from this problem

Two Notions of Time

There are two kinds of hardware circuits: combinational and sequential. This means that for any signal, we have to answer the question: When is this signal used? Now (in the current cycle) or later (in a future cycle).
These two are the only interesting possibilities to me because once you register a signal, it becomes easier to use it in the future.

The question at the heart of all discussions about signal visibility, operation chaining optimizations, etc., are about the nature of time in FuTIL. While groups, components, and control programs all operate with the assumption that there are time steps,
there are privileged primitives like add that take no time to execute. This property of the primitives leaks into everything else (some groups take no time) and breaks various assumptions.

So the question is why have this privilege? Or rather, is there a way for us to always insert registers and use state and opportunistically eliminate it when we can?

[sgpthomas]

Let's explore the idea of requiring every group to commit it's results (and thus banning combinational groups). Imposing this requirement allows groups to always be composable, but also puts the burden of synthesizability on the frontend because they have to make sure that every group generated is small enough.

To mitigate this, we need to be able to remove registers and merge groups. Consider the following program:

component main() -> () {
  cells {}
  wires {
    group X {
      add.left = 32'd1;
      add.right = 32'd1;
      a.in = add.out;
      a.write_en = 1'b1;
      X[done] = a.done;
    }

    group Y {
      add2.left = a.out;
      add2.right = 32'd1;
      b.in = add2.out;
      b.write_en = 1'b1;
      Y[done] = b.done;
    }
  }
  control {
    seq { X; Y; }
  }
}

We want to merge the groups X and Y into a single group like so:

component main() -> () {
  cells {}
  wires {
    group single_add {
      add.left = 32'd1;
      add.right = 32'd1;
      add2.left = add.out;
      add2.right = 32'd1;
      b.in = add2.out;
      b.write_en = 1'b1;
      add1[done] = b.done;
    }
  }
  control {
    single_add;
  }
}

To be able to do this transformation, we need to prove a few things about the register a.

• Prove that removing the register a does not have observable effects on state.
  • to prove this I think it's enough to show that a is written only once in X and read once in Y. You can relax the requirement to allow a to be written to before X, but it can't be read after X.
• Prove that removing the reigster a does not have observable effects on ordering (control flow).
  • In particular if a.done is used as a guard in X in a place other than the [done] signal then you can't remove a.
  • I think it's enough to show that X[done] is high exactly when a.done is high.

If we have liveness information about registers alongside being able to prove how a register effects the internal control flow of a group then we can perform this optimization.

I think there are two questions from here to answer:

1. What are the situations that prevent this analysis from working?
2. Can we place restrictions on registers to simplify this analysis?

[rachitnigam]

There is nothing to be done for this issue. The intellectual heritage of this discussion was:

1. The creation of the invoke primitive.
2. Precise understanding of the encapsulation properties of groups
3. The necessary connection between primitives, components, and groups (Leading to the adage, "If you solve a problem for one, you'll have to solve it for the other two")

At the time of writing, there are ongoing discussions on interfaces that more precisely track the visibility of signals. The origins of that discussion can be traced back to this issue.