Generate efficient FSMs for slow modules

[rachitnigam]

When a module does not have an II=1, we should be able to generate smaller, counter-based FSMs. This is particularly important if we're interacting with modules of high-latency since we may need to a long time and the generated pipelined FSM can get quite large.

[rachitnigam]

Here is a sketch for slow FSMs that I came up with. The high-level idea is that for a module that can retrigger every $d$ cycles and has $n$ states, we can instantiate $n/d$ counters that count out to $d$ before asserting done and chaining them together. Overall, this uses $n/d \times log(d)$ bits instead of $n$ bits.

The overhead for this process is that each counter gets an $n/d$-bit adder so it's not obvious that we should always do this but it is also hard to come up with an obvious heuristic to decide when to allocate it.

In general, the cases that actually matter are probably completely iterative modules where delay = latency or fully pipelined modules.

/// A module that counts up to 3 and resets.
module count_3 (
    input wire clk,
    input wire reset,
    input logic go,

    output logic done,
    output wire s0,
    output wire s1,
    output wire s2
);
    logic [1:0] count;

    assign s0 = go & count == 0;
    assign s1 = count == 1;
    assign s2 = count == 2;

    always @(posedge clk) begin
        if (reset) begin
            count <= 0;
        end else if (count == 2) begin
            count <= 0;
        end else if (go || count != 0) begin
            count <= count + 1;
        end
    end

    always @(posedge clk) begin
        if (count == 2) begin
            done <= 1;
        end else begin
            done <= 0;
        end
    end
endmodule

/// An FSM with 12 states that can only be triggered every 3 clock cycles.
module FSM (
    input wire clk,
    input wire reset,
    input logic go,

    output wire done,
    // Expose all 12 states
    output wire s0,
    output wire s1,
    output wire s2,
    output wire s3,
    output wire s4,
    output wire s5,
    output wire s6,
    output wire s7,
    output wire s8,
    output wire s9,
    output wire s10,
    output wire s11
);

wire c0_done, c1_done, c2_done, c3_done;

// FSM is done when the last counter is done.
assign done = c3_done;

// Instantiate 4 count_3 modules.
count_3 c0 (
    .clk(clk),
    .reset(reset),
    .go(go),
    .done(c0_done),
    .s0(s0),
    .s1(s1),
    .s2(s2)
);
count_3 c1 (
    .clk(clk),
    .reset(reset),
    .go(c0_done),
    .done(c1_done),
    .s0(s3),
    .s1(s4),
    .s2(s5)
);

count_3 c2 (
    .clk(clk),
    .reset(reset),
    .go(c1_done),
    .done(c2_done),
    .s0(s6),
    .s1(s7),
    .s2(s8)
);
count_3 c3 (
    .clk(clk),
    .reset(reset),
    .go(c2_done),
    .done(c3_done),
    .s0(s9),
    .s1(s10),
    .s2(s11)
);
endmodule

[rachitnigam]

It might be cool to have "unchecked" modules in Filament because the above can easily be implemented in Filament but cannot be type checked.