// wai-quantum fabric: the gate datapath for an FPGA.
//
// A transcription of `lanes::exact_row` and `lanes::apply_words` into logic.
// Amplitudes are pairs of 32-bit fixed-point values (30 fractional bits), held
// in a dual-port RAM, one 64-bit lane per address: {imaginary, real}.
//
// Each 32x32 product is built from four 16-bit partial products, the size of
// an FPGA's multiplier blocks: with a = ah*2^16 + al (ah signed, al unsigned)
// and b likewise,
//
// a*b = ah*bh*2^32 + (ah*bl + al*bh)*2^16 + al*bl
//
// exact in 64 bits, as is fx(a, b) = (a*b + 2^29) >>> 30 and each row's sum
// of four such products. The lane keeps each sum's low 32 bits; a sum outside
// 32 bits records the gate's op-log index in `report`, the lowest winning.
//
// One pair per two cycles: the first reads both amplitudes of the pair, the
// second writes both results. A gate visits every pair in order; nothing
// depends on timing beyond that order, and each pair's two addresses are its
// own.
`default_nettype none
// The exact product and the exact fixed-point product.
module wq_fx_mul (
input wire signed [31:0] a,
input wire signed [31:0] b,
output wire signed [63:0] prod,
output wire signed [63:0] fx
);
wire signed [15:0] ah = a[31:16];
wire [15:0] al = a[15:0];
wire signed [15:0] bh = b[31:16];
wire [15:0] bl = b[15:0];
wire signed [31:0] hh = ah * bh;
wire signed [32:0] hl = ah * $signed({1'b0, bl});
wire signed [32:0] lh = $signed({1'b0, al}) * bh;
wire [31:0] ll = al * bl;
assign prod = ($signed({{32{hh[31]}}, hh}) <<< 32)
+ ($signed({{31{hl[32]}}, hl}) <<< 16)
+ ($signed({{31{lh[32]}}, lh}) <<< 16)
+ $signed({32'd0, ll});
assign fx = (prod + 64'sd536870912) >>> 30;
endmodule
// One gate on one pair: row 0 is (m0 + i*m1)*a0 + (m2 + i*m3)*a1, row 1 is
// (m4 + i*m5)*a0 + (m6 + i*m7)*a1.
module wq_pair (
input wire signed [31:0] m0, m1, m2, m3, m4, m5, m6, m7,
input wire signed [31:0] a0r, a0i, a1r, a1i,
output wire [31:0] o0r, o0i, o1r, o1i,
output wire out_of_range
);
wire signed [63:0] p0r0, p0i0, p1r0, p1i0, p2r1, p2i1, p3r1, p3i1;
wire signed [63:0] p4r0, p4i0, p5r0, p5i0, p6r1, p6i1, p7r1, p7i1;
wire signed [63:0] unused [0:15];
wq_fx_mul u0 (.a(m0), .b(a0r), .prod(unused[0]), .fx(p0r0));
wq_fx_mul u1 (.a(m0), .b(a0i), .prod(unused[1]), .fx(p0i0));
wq_fx_mul u2 (.a(m1), .b(a0r), .prod(unused[2]), .fx(p1r0));
wq_fx_mul u3 (.a(m1), .b(a0i), .prod(unused[3]), .fx(p1i0));
wq_fx_mul u4 (.a(m2), .b(a1r), .prod(unused[4]), .fx(p2r1));
wq_fx_mul u5 (.a(m2), .b(a1i), .prod(unused[5]), .fx(p2i1));
wq_fx_mul u6 (.a(m3), .b(a1r), .prod(unused[6]), .fx(p3r1));
wq_fx_mul u7 (.a(m3), .b(a1i), .prod(unused[7]), .fx(p3i1));
wq_fx_mul u8 (.a(m4), .b(a0r), .prod(unused[8]), .fx(p4r0));
wq_fx_mul u9 (.a(m4), .b(a0i), .prod(unused[9]), .fx(p4i0));
wq_fx_mul u10 (.a(m5), .b(a0r), .prod(unused[10]), .fx(p5r0));
wq_fx_mul u11 (.a(m5), .b(a0i), .prod(unused[11]), .fx(p5i0));
wq_fx_mul u12 (.a(m6), .b(a1r), .prod(unused[12]), .fx(p6r1));
wq_fx_mul u13 (.a(m6), .b(a1i), .prod(unused[13]), .fx(p6i1));
wq_fx_mul u14 (.a(m7), .b(a1r), .prod(unused[14]), .fx(p7r1));
wq_fx_mul u15 (.a(m7), .b(a1i), .prod(unused[15]), .fx(p7i1));
wire signed [63:0] s0r = p0r0 - p1i0 + p2r1 - p3i1;
wire signed [63:0] s0i = p0i0 + p1r0 + p2i1 + p3r1;
wire signed [63:0] s1r = p4r0 - p5i0 + p6r1 - p7i1;
wire signed [63:0] s1i = p4i0 + p5r0 + p6i1 + p7r1;
// A sum fits 32 bits when its top 33 bits all equal its sign.
function fits32(input [63:0] v);
fits32 = (v[63:31] == {33{1'b0}}) || (v[63:31] == {33{1'b1}});
endfunction
assign out_of_range = !(fits32(s0r) && fits32(s0i) && fits32(s1r) && fits32(s1i));
assign o0r = s0r[31:0];
assign o0i = s0i[31:0];
assign o1r = s1r[31:0];
assign o1i = s1i[31:0];
endmodule
// The datapath: the state RAM, its host port, the probe, and the gate engine.
module wq_lanes64 #(
parameter AW = 20
) (
input wire clk,
// The host port: write or read one lane of the state while idle.
input wire host_we,
input wire [AW-1:0] host_addr,
input wire [63:0] host_wdata,
output wire [63:0] host_rdata,
// The probe: the exact product and fixed-point product of one pair.
input wire [31:0] probe_a,
input wire [31:0] probe_b,
output wire [63:0] probe_prod,
output wire [63:0] probe_fx,
// One gate: its words, the state's pair count, and its op-log index.
input wire start,
input wire [31:0] m0, m1, m2, m3, m4, m5, m6, m7,
input wire [31:0] tbit,
input wire [31:0] ctrl,
input wire [31:0] index,
input wire [AW:0] pairs,
input wire report_reset,
output reg busy,
output reg [31:0] report
);
reg [63:0] mem [0:(1 << AW) - 1];
assign host_rdata = mem[host_addr];
wq_fx_mul probe (.a(probe_a), .b(probe_b), .prod(probe_prod), .fx(probe_fx));
reg [AW:0] p;
reg phase;
reg [63:0] lane_i, lane_j;
reg [AW-1:0] addr_i, addr_j;
reg take;
// The p-th index whose target bit is clear: p with a zero inserted at the
// target's position.
wire [AW:0] tmask = tbit[AW:0] - 1'b1;
wire [AW:0] low = p & tmask;
wire [AW:0] i_ix = ((p - low) << 1) | low;
wire [AW:0] j_ix = i_ix | tbit[AW:0];
wire selected = ((i_ix & ctrl[AW:0]) == ctrl[AW:0]);
wire [31:0] o0r, o0i, o1r, o1i;
wire oor;
wq_pair pair (
.m0(m0), .m1(m1), .m2(m2), .m3(m3), .m4(m4), .m5(m5), .m6(m6), .m7(m7),
.a0r(lane_i[31:0]), .a0i(lane_i[63:32]), .a1r(lane_j[31:0]), .a1i(lane_j[63:32]),
.o0r(o0r), .o0i(o0i), .o1r(o1r), .o1i(o1i), .out_of_range(oor)
);
always @(posedge clk) begin
if (report_reset) begin
report <= 32'hFFFF_FFFF;
end
if (!busy) begin
if (host_we) begin
mem[host_addr] <= host_wdata;
end
if (start) begin
busy <= (pairs != 0);
p <= 0;
phase <= 1'b0;
end
end else if (phase == 1'b0) begin
// Read the pair's two lanes.
addr_i <= i_ix[AW-1:0];
addr_j <= j_ix[AW-1:0];
lane_i <= mem[i_ix[AW-1:0]];
lane_j <= mem[j_ix[AW-1:0]];
take <= selected;
phase <= 1'b1;
end else begin
// Write both results, and report a sum outside 32 bits.
if (take) begin
mem[addr_i] <= {o0i, o0r};
mem[addr_j] <= {o1i, o1r};
if (oor && index < report) begin
report <= index;
end
end
phase <= 1'b0;
if (p + 1 == pairs) begin
busy <= 1'b0;
end
p <= p + 1;
end
end
initial begin
busy = 1'b0;
report = 32'hFFFF_FFFF;
end
endmodule
`default_nettype wire