Support non-flattened circuits?

[benediamond]

Many (even combinational) circuits have efficient descriptions, but become impracticable when they have to be "flattened" or unrolled. This is discussed in detail in e.g. [KMsB13] and [SHSSK15].

The Bristol Format circuits which this library accepts have to be totally flattened. While this makes things easier for the developer (you), it significantly limits the circuits / functions on which the protocol can operate efficiently in practice. Moreover, the Bristol format makes it difficult to use modern hardware synthesis tools. Indeed, the only tool I could find which specifically targets this format is CBMC-GC-2, which is a bit buggy and performs poorly (huge memory consumption even on medium-sized circuits).

As a longer-term goal, I wonder if it would be possible to shift to a more modern / efficient circuit representation. For example, we could target the format output by yosys after running the sequence of commands

proc; opt; techmap; opt; abc; opt; write_verilog out.v

I recognize this would be a very large project, but I think it would significantly enhance the practical power of EMP-Toolkit, and could be worthwhile. I'd be happy to contribute.

[benediamond]

By way of example, consider the following trivial verilog circuit.

module adder (
   input [15 : 0] a, b,
   output [15 : 0] out
   );

   assign out = a + b;
endmodule

module naive_multiply ( // multiplies in by N modulo 2^16.
    input [15 : 0] in,
    output [15 : 0] result
    );

    localparam N = 7;

    wire [16 * N - 1 : 0] temp;
    assign temp[15 : 0] = in[15 : 0];
    genvar i; generate
        for (i = 1; i < N; i = i + 1) begin
            adder add(in, temp[i * 16 - 1 : (i - 1) * 16], temp[(i + 1) * 16 - 1 : i * 16]);
        end
    endgenerate

    assign result[15 : 0] = temp[16 * N - 1 : 16 * (N - 1)];
endmodule

If you import this into yosys, you can see that calling flatten before calling write_verilog out.v causes the resulting output file to increase essentially N-fold in size, where N is the localparam in naive_multiply. This becomes a big issue for non-trivial circuits. Let me know if I can provide more info. Thanks again for reading.

[wangxiao1254]

This has always been a goal but it is not really very easy from an engineering perspective. Essentially, we want this repo to use our main EMP interfaces. We cannot support it for now but we may find a way around it at a point!