Hugging Face's logo

Snapkitty
/
bit-string-accelerator

snapkitty
october-2026-drop
systemverilog
rtl
fpga
asic
formal-verification
hardware
Model card Files
xet
 Community
bit-string-accelerator / pcie /rtl /bitacc_engine.sv
SNAPKITTYWEST's picture
SNAPKITTYWEST
October 2026 main drop: mirror from GitHub
0ba037b verified
Raw History Blame Contribute Delete
36.7 kB
// Parallel bit-operation engine.
//
// A stream of operation descriptors is executed by LANES lanes, each owning
// one bank of the bit store. Word w lives in lane w % LANES at local address
// w / LANES. Results leave in descriptor order through a reorder buffer, and
// equal those of executing the stream one operation at a time (checked against
// the reference core rtl/bit_accelerator.sv by pcie/tb/tb_engine.sv).
//
// Single-bit operations (op 0-4, as in the reference core):
// effective bit a = (base << 3) + offset (mod 2^64)
// word = a >> 6, bit index = a[5:0]
// error = word >= WORDS (no write)
// 0 GET, 1 TEST: bit; 2 SET, 3 CLEAR, 4 TOGGLE: write, return the new bit
// All operations on one word run in one lane, in arrival order. Operations on
// different words commute, so lanes can complete out of order.
//
// Range operations (op 8-15). Each is a barrier: it starts when every earlier
// operation has completed, runs on all lanes at once, and later operations
// start after it. The bit store is therefore always in the state that
// sequential execution gives.
// bit ranges, bits [a, a + len):
// 8 COUNT value = number of set bits
// 9 FIND1 value = index of the first set bit; bit = found
// 10 FIND0 value = index of the first clear bit; bit = found
// 11 SETR, 12 CLEARR, 13 FLIPR: set/clear/invert every bit;
// value = number of set bits before the operation
// 15 MATCH pattern = word src, mask = word src+1. Position s in [a, a+len)
// matches if every mask bit j has s + j < a + len and
// bit(s + j) == pattern[j]. fn 0: value = number of matches;
// fn 1: value = first matching position, bit = found.
// Needs WITH_MATCH = 1; otherwise opcode 15 is an error.
// error = a + len > WORDS * 64; MATCH also: fn > 1 || src + 2 > WORDS
// word regions, words dst = a .. a+len-1 and src = src .. src+len-1:
// 14 BULK dst[k] = fn(dst[k], src[k]) for every k, unless dry;
// fn 0 COPY, 1 AND, 2 OR, 3 XOR, 4 ANDN (dst & ~src);
// value = number of set bits in the results
// error = fn > 4 || dst + len > WORDS || src + len > WORDS
// || the regions overlap without being identical (no write)
// For range operations without a find result, bit = (value != 0). len = 0
// is valid (value 0, not found). Undefined opcodes (5-7) are errors. An
// error result has bit = 0 and value = 0.
//
// A range operation processes LANES words per step. Bit ranges step through
// groups of LANES consecutive words (one per lane, same local address). BULK
// pairs dst[k] with src[k], which may live in different lanes: lane i reads
// src element k = j*LANES + ((i - src) mod LANES) at local address
// j + (src + ((i - src) mod LANES)) / LANES, and dst lane m receives it from
// lane (m - delta) mod LANES, delta = (dst - src) mod LANES. formal/lane_map.mlw
// proves these index identities. Each BULK step is a src read, a dst read and
// a write: LANES words per 2 cycles. MATCH steps like a bit range; lane i
// checks the 64 positions of the word before its own (word w - 1), with the
// window {word w, word w - 1}; lane 0 takes word w - 1 from the last lane of
// the previous step. With MATCH_LANES < LANES, each group of LANES words is
// matched in LANES / MATCH_LANES sub-steps (the group is read again in each;
// MATCH does not write): unit u takes word sub * MATCH_LANES + u. That is
// MATCH_LANES * 64 positions per cycle.
//
// Timing: every block-RAM port is driven by a register (through the port
// mux), the descriptor's 64-bit sums are registered before they are compared,
// and popcount, lowest-set-bit and the cross-lane sums are balanced trees.
// Range pipeline: S0 issue -> S1 address register (bank read) -> S2 data
// (rdata, masks registered) -> S3 compute from registered data (write and
// result word registered) -> S4 write, popcount -> S5 reduce.
//
// The host port reads and writes whole words while the engine is idle
// (host_ready is low while any operation is in flight).
module bitacc_engine #(
parameter int LANES = 4, // power of two, >= 2
parameter int WORDS_PER_LANE = 512, // power of two, >= 2
parameter int ROB_DEPTH = 32, // power of two; max operations in flight
parameter int FIFO_DEPTH = 16, // per-lane queue; power of two
parameter bit WITH_MATCH = 1'b1, // MATCH unit
parameter int MATCH_LANES = LANES // matcher units (power of two, 1 .. LANES; ~4,000 LUTs each on XC7)
)(
input logic clk,
input logic reset,
// descriptors in
input logic cmd_valid,
output logic cmd_ready,
input logic [3:0] cmd_op,
input logic [63:0] cmd_base,
input logic [63:0] cmd_offset,
input logic [31:0] cmd_len, // range length: bits, or words for BULK
input logic [23:0] cmd_src, // BULK source word, MATCH pattern word
input logic [2:0] cmd_fn, // BULK function, MATCH result kind
input logic cmd_dry, // BULK: count only, no write
// results out, in descriptor order
output logic res_valid,
input logic res_ready,
output logic res_error,
output logic res_bit,
output logic [55:0] res_value,
// host word access (only while idle)
input logic host_valid,
output logic host_ready,
input logic host_write,
input logic [$clog2(LANES*WORDS_PER_LANE)-1:0] host_word,
input logic [63:0] host_wdata,
output logic host_rvalid,
output logic [63:0] host_rdata,
output logic idle
);
localparam int LW = $clog2(LANES);
localparam int AW = $clog2(WORDS_PER_LANE);
localparam int GW = AW + 1; // step counter (MATCH reads one step past the end)
localparam int WW = LW + AW; // global word index width
localparam int BW = WW + 6; // global bit index width
localparam int CW = BW + 1; // bit count width (0 .. WORDS*64)
localparam int SW = $clog2(ROB_DEPTH);
localparam int FW = $clog2(FIFO_DEPTH);
localparam int MK = LANES / MATCH_LANES; // MATCH sub-steps per group
localparam int SBW = MK > 1 ? $clog2(MK) : 1;
localparam logic [3:0] OP_SET = 4'd2, OP_CLEAR = 4'd3, OP_TOGGLE = 4'd4;
localparam logic [3:0] OP_COUNT = 4'd8, OP_FIND1 = 4'd9, OP_FIND0 = 4'd10,
OP_SETR = 4'd11, OP_CLEARR = 4'd12, OP_FLIPR = 4'd13,
OP_BULK = 4'd14, OP_MATCH = 4'd15;
localparam logic [2:0] FN_COPY = 3'd0, FN_AND = 3'd1, FN_OR = 3'd2, FN_XOR = 3'd3, FN_ANDN = 3'd4;
localparam logic [64:0] STORE_WORDS = 65'(LANES * WORDS_PER_LANE);
localparam logic [64:0] STORE_BITS = STORE_WORDS << 6;
// Balanced trees (a loop that accumulates bit by bit synthesizes a 64-deep chain).
function automatic logic [6:0] popcount64(input logic [63:0] x);
logic [6:0] s [64];
for (int i = 0; i < 64; i++) s[i] = 7'(x[i]);
for (int w = 32; w >= 1; w = w / 2)
for (int i = 0; i < w; i++) s[i] = s[2*i] + s[2*i+1];
popcount64 = s[0];
endfunction
function automatic logic [5:0] ctz64(input logic [63:0] x); // index of the lowest set bit
logic [7:0] any;
logic [2:0] pos [8];
logic [2:0] grp;
for (int k = 0; k < 8; k++) begin
any[k] = |x[8*k +: 8];
pos[k] = '0;
for (int b = 7; b >= 0; b--) if (x[8*k + b]) pos[k] = 3'(b);
end
grp = '0;
for (int k = 7; k >= 0; k--) if (any[k]) grp = 3'(k);
ctz64 = {grp, pos[grp]};
endfunction
function automatic logic [5:0] msb64(input logic [63:0] x); // index of the highest set bit (0 if none)
logic [7:0] any;
logic [2:0] pos [8];
logic [2:0] grp;
for (int k = 0; k < 8; k++) begin
any[k] = |x[8*k +: 8];
pos[k] = '0;
for (int b = 0; b < 8; b++) if (x[8*k + b]) pos[k] = 3'(b);
end
grp = '0;
for (int k = 0; k < 8; k++) if (any[k]) grp = 3'(k);
msb64 = {grp, pos[grp]};
endfunction
// ---------------------------------------------------------------- stage P: accept
// A 2-entry skid buffer: cmd_ready is a register (computed from next-state
// counts), so no combinational path runs from the dispatch logic back to the
// descriptor source. The 64-bit sums are registered here and compared in D.
logic p_valid, p_take;
logic [1:0] p_cnt; // entries held (0..2); entry 0 is the head
logic p_rdy;
logic [SW-1:0] pe_seq [2];
logic [3:0] pe_op [2];
logic [2:0] pe_fn [2];
logic pe_dry [2];
logic [63:0] pe_eff [2];
logic [31:0] pe_len [2];
logic [23:0] pe_src [2];
logic [64:0] pe_end [2]; // a + len: bit range end, or dst region end
logic [32:0] pe_send [2]; // src + len: src region end
logic [SW:0] inflight; // descriptors accepted and not yet emitted
logic [SW:0] inflight_next;
logic [SW-1:0] next_seq;
logic d_valid, d_take;
logic accept, emit;
logic [1:0] p_cnt_next;
logic p_wp, p_rp; // write and read slots of the circular 2-entry buffer
logic [63:0] c_eff; // effective bit address, mod 2^64
assign c_eff = (cmd_base << 3) + cmd_offset;
assign cmd_ready = p_rdy;
assign accept = cmd_valid && p_rdy;
assign p_valid = p_cnt != 2'd0;
assign p_take = p_valid && (!d_valid || d_take);
assign p_cnt_next = p_cnt + 2'(accept) - 2'(p_take);
// inflight counts the descriptors held in stages P and D too.
assign inflight_next = inflight + (SW+1)'(accept) - (SW+1)'(emit);
// the head entry, as stage D sees it (taking it only moves p_rp, so the
// dispatch decision drives no wide enable here)
logic [SW-1:0] p_seq;
logic [3:0] p_op;
logic [2:0] p_fn;
logic p_dry;
logic [63:0] p_eff;
logic [31:0] p_len;
logic [23:0] p_src;
logic [64:0] p_end;
logic [32:0] p_send;
assign p_seq = pe_seq[p_rp]; assign p_op = pe_op[p_rp]; assign p_fn = pe_fn[p_rp]; assign p_dry = pe_dry[p_rp];
assign p_eff = pe_eff[p_rp]; assign p_len = pe_len[p_rp]; assign p_src = pe_src[p_rp];
assign p_end = pe_end[p_rp]; assign p_send = pe_send[p_rp];
always_ff @(posedge clk) begin
if (reset) begin
p_cnt <= '0; p_rdy <= 1'b0; next_seq <= '0; p_wp <= 1'b0; p_rp <= 1'b0;
for (int i = 0; i < 2; i++) begin
pe_seq[i] <= '0; pe_op[i] <= '0; pe_fn[i] <= '0; pe_dry[i] <= 1'b0; pe_eff[i] <= '0;
pe_len[i] <= '0; pe_src[i] <= '0; pe_end[i] <= '0; pe_send[i] <= '0;
end
end else begin
p_cnt <= p_cnt_next;
p_rdy <= p_cnt_next < 2'd2 && inflight_next < (SW+1)'(ROB_DEPTH);
if (p_take) p_rp <= !p_rp;
if (accept) begin
pe_seq[p_wp] <= next_seq;
pe_op[p_wp] <= cmd_op;
pe_fn[p_wp] <= cmd_fn;
pe_dry[p_wp] <= cmd_dry;
pe_eff[p_wp] <= c_eff;
pe_len[p_wp] <= cmd_len;
pe_src[p_wp] <= cmd_src;
pe_end[p_wp] <= {1'b0, c_eff} + 65'(cmd_len);
pe_send[p_wp] <= 33'(cmd_src) + 33'(cmd_len);
p_wp <= !p_wp;
next_seq <= next_seq + 1'b1;
end
end
end
// ---------------------------------------------------------------- stage D: decode
logic [64:0] a_x, src_x, send_x;
logic c_range, c_err;
assign a_x = {1'b0, p_eff};
assign src_x = 65'(p_src);
assign send_x = 65'(p_send);
assign c_range = p_op >= OP_COUNT;
always_comb begin
if (p_op <= OP_TOGGLE) c_err = (p_eff >> (WW + 6)) != '0;
else if (p_op < OP_COUNT) c_err = 1'b1; // 5-7
else if (p_op < OP_BULK) c_err = p_end > STORE_BITS;
else if (p_op == OP_BULK) c_err = p_fn > FN_ANDN || p_end > STORE_WORDS || send_x > STORE_WORDS
|| (p_len != '0 && a_x != src_x && a_x < send_x && src_x < p_end);
else c_err = !WITH_MATCH || p_fn > 3'd1 || p_end > STORE_BITS
|| src_x + 65'd2 > STORE_WORDS;
end
logic [SW-1:0] d_seq;
logic d_err, d_range;
logic [3:0] d_op;
logic [LW-1:0] d_lane;
logic [AW-1:0] d_local;
logic [5:0] d_bit;
logic [2:0] d_fn;
logic d_dry, d_empty;
logic [BW-1:0] d_lo, d_hi; // first and last bit (bit ranges); d_lo[WW-1:0] = dst (BULK)
logic [WW-1:0] d_src;
logic [WW:0] d_n; // BULK word count (<= WORDS when valid)
always_ff @(posedge clk) begin
if (reset) begin
d_valid <= 1'b0;
d_seq <= '0; d_err <= 1'b0; d_range <= 1'b0; d_op <= '0; d_lane <= '0; d_local <= '0; d_bit <= '0;
d_fn <= '0; d_dry <= 1'b0; d_empty <= 1'b0; d_lo <= '0; d_hi <= '0; d_src <= '0; d_n <= '0;
end else begin
if (d_take) d_valid <= 1'b0;
if (p_take) begin
d_valid <= 1'b1;
d_seq <= p_seq;
d_err <= c_err;
d_range <= c_range;
d_op <= p_op;
d_lane <= p_eff[6 +: LW];
d_local <= p_eff[6 + LW +: AW];
d_bit <= p_eff[5:0];
d_fn <= p_fn;
d_dry <= p_dry;
d_empty <= p_len == '0;
d_lo <= p_eff[BW-1:0];
d_hi <= BW'(p_end - 65'd1);
d_src <= src_x[WW-1:0];
d_n <= (WW+1)'(p_len);
end
end
end
// ---------------------------------------------------------------- dispatch
logic [LANES-1:0] q_full, q_empty;
logic [LANES-1:0] q_push, q_pop;
logic [SW-1:0] q_seq [LANES];
logic [AW-1:0] q_local [LANES];
logic [5:0] q_bit [LANES];
logic [2:0] q_op [LANES];
logic [LANES-1:0] l_busy;
logic r_busy, r_start;
logic [SW:0] ops_out; // single-bit operations dispatched and not completed
logic [LANES-1:0] l_done;
// Errors bypass the lanes and go straight to the reorder buffer. A range
// operation waits until every dispatched single-bit operation has completed
// (ops_out is a register; it reaches 0 the cycle after the last completion
// pulse, after that operation's write); nothing dispatches while it runs.
assign r_start = d_valid && !d_err && d_range && !r_busy && ops_out == '0;
assign d_take = d_valid && (d_err || r_start || (!d_range && !r_busy && !q_full[d_lane]));
always_comb begin
q_push = '0;
if (d_valid && !d_err && !d_range && !r_busy && !q_full[d_lane]) q_push[d_lane] = 1'b1;
end
always_ff @(posedge clk) begin
if (reset) ops_out <= '0;
else begin
logic [SW:0] done_n;
done_n = '0;
for (int i = 0; i < LANES; i++) done_n = done_n + (SW+1)'(l_done[i]);
ops_out <= ops_out + (SW+1)'(|q_push) - done_n;
end
end
// ---------------------------------------------------------------- range unit: control
// R_IDLE -> R_INIT (derived constants from registered parameters) -> R_ISSUE
// -> R_DRAIN -> R_IDLE; MATCH loads its pattern first:
// R_INIT -> R_PAT -> R_PWAIT -> R_PSET1 -> R_PSET2 -> R_PSET3 -> R_ISSUE.
typedef enum logic [3:0] {R_IDLE, R_INIT, R_PAT, R_PWAIT, R_PSET1, R_PSET2, R_PSET3,
R_ISSUE, R_DRAIN} rstate_t;
localparam logic [2:0] K_BITS = 3'd0, K_SRC = 3'd1, K_DST = 3'd2, K_PAT = 3'd3, K_MAT = 3'd4;
rstate_t r_state;
logic [SW-1:0] r_seq;
logic [3:0] r_op;
logic [2:0] r_fn;
logic r_dry, r_empty;
logic [BW-1:0] r_lo, r_hi; // first and last bit; MATCH: first and last position
logic [WW-1:0] r_src;
logic [WW:0] r_n;
logic [GW-1:0] r_g, r_glast; // step: group (bit ranges, MATCH) or j (BULK)
logic [SBW-1:0] r_sub; // MATCH sub-step within the group
logic r_phase; // BULK: 0 src read, 1 dst read
logic [63:0] r_lowm, r_highm; // bit masks of the first and last word of the range
logic [CW-1:0] r_acc;
logic r_found;
logic [BW-1:0] r_idx;
logic r_done;
logic r_find, r_bulk, r_match;
logic [63:0] r_pat, r_msk; // MATCH pattern and mask
logic [LW-1:0] r_pat_lane, r_msk_lane;
logic [5:0] m_top; // MATCH: highest mask bit (0 if the mask is 0)
logic m_neg; // MATCH: last position below 0
assign r_busy = r_state != R_IDLE;
assign r_bulk = r_op == OP_BULK;
assign r_match = r_op == OP_MATCH;
assign r_find = r_op == OP_FIND1 || r_op == OP_FIND0 || (r_match && r_fn[0]);
// S0 issue: one read per lane per cycle
logic s0_valid;
logic [2:0] s0_kind;
assign s0_valid = r_state == R_PAT || (r_state == R_ISSUE && !(r_find && r_found));
always_comb begin
if (r_state == R_PAT) s0_kind = K_PAT;
else if (r_bulk) s0_kind = r_phase ? K_DST : K_SRC;
else if (r_match) s0_kind = K_MAT;
else s0_kind = K_BITS;
end
// central pipeline registers
logic s1_valid, s2_valid, s3_valid, s4_valid, s5_valid, s6_valid;
logic [2:0] s1_kind, s2_kind, s3_kind;
logic [GW-1:0] s1_g, s2_g, s3_g, s4_g, s5_g;
logic [SBW-1:0] s1_sub, s2_sub, s3_sub, s4_sub, s5_sub;
logic [6:0] s5_cnt [LANES];
logic [LANES-1:0] s5_hit;
logic [5:0] s5_pos [LANES];
// S5 reduce across lanes, registered into S6
logic [LW+6:0] s5_sum, s6_sum; // set bits (or matches) in this step, all lanes
logic s5_any, s6_any;
logic [LW-1:0] s5_first; // lowest lane with a hit
logic [WW:0] s5_word; // word of that lane's result bits
logic [BW-1:0] s6_idx; // first hit of this step
always_comb begin
logic [LW+6:0] t [LANES];
for (int i = 0; i < LANES; i++) t[i] = (LW+7)'(s5_cnt[i]);
for (int lvl = 0; lvl < LW; lvl++)
for (int i = 0; i < LANES / 2; i++)
if (i < (LANES >> (lvl + 1))) t[i] = t[2*i] + t[2*i+1];
s5_sum = t[0];
s5_any = 1'b0; s5_first = '0;
for (int i = LANES - 1; i >= 0; i--) if (s5_hit[i]) begin s5_any = 1'b1; s5_first = LW'(i); end
// MATCH results of unit i belong to word g * LANES + sub * MATCH_LANES + i - 1
if (r_match)
s5_word = (WW+1)'({s5_g, LW'(0)}) + (WW+1)'(s5_sub) * (WW+1)'(MATCH_LANES)
+ (WW+1)'(s5_first) - (WW+1)'(1);
else
s5_word = {s5_g, s5_first};
end
always_ff @(posedge clk) begin
r_done <= 1'b0;
if (reset) begin
r_state <= R_IDLE; r_seq <= '0; r_op <= '0; r_fn <= '0; r_dry <= 1'b0; r_empty <= 1'b0;
r_lo <= '0; r_hi <= '0; r_src <= '0; r_n <= '0; r_g <= '0; r_glast <= '0;
r_phase <= 1'b0; r_lowm <= '0; r_highm <= '0; r_acc <= '0; r_found <= 1'b0; r_idx <= '0;
r_sub <= '0;
s1_sub <= '0; s2_sub <= '0; s3_sub <= '0; s4_sub <= '0; s5_sub <= '0;
r_pat_lane <= '0; r_msk_lane <= '0; m_top <= '0; m_neg <= 1'b0;
s1_valid <= 1'b0; s1_kind <= K_BITS; s1_g <= '0;
s2_valid <= 1'b0; s2_kind <= K_BITS; s2_g <= '0;
s3_valid <= 1'b0; s3_kind <= K_BITS; s3_g <= '0;
s4_valid <= 1'b0; s4_g <= '0; s5_valid <= 1'b0; s5_g <= '0;
s6_valid <= 1'b0; s6_sum <= '0; s6_any <= 1'b0; s6_idx <= '0;
end else begin
case (r_state)
R_IDLE: begin
// follow the decode register while idle, so starting needs no wide enable
r_seq <= d_seq; r_op <= d_op; r_fn <= d_fn; r_dry <= d_dry; r_empty <= d_empty;
r_lo <= d_lo; r_hi <= d_hi; r_src <= d_src; r_n <= d_n;
if (r_start) r_state <= R_INIT;
end
R_INIT: begin
r_g <= r_bulk ? '0 : GW'(r_lo[BW-1:6+LW]);
r_glast <= r_bulk ? GW'((r_n - 1'b1) >> LW) : GW'(r_hi[BW-1:6+LW]);
r_lowm <= ~64'd0 << r_lo[5:0];
r_highm <= ~64'd0 >> (6'd63 - r_hi[5:0]);
r_pat_lane <= r_src[LW-1:0];
r_msk_lane <= r_src[LW-1:0] + 1'b1;
r_phase <= 1'b0; r_sub <= '0;
r_acc <= '0; r_found <= 1'b0; r_idx <= '0;
r_state <= r_empty ? R_DRAIN : (r_match ? R_PAT : R_ISSUE);
end
R_PAT: r_state <= R_PWAIT;
R_PWAIT: if (!s1_valid && !s2_valid && !s3_valid) r_state <= R_PSET1; // pattern captured
R_PSET1: begin
m_top <= r_msk == '0 ? 6'd0 : msb64(r_msk);
r_state <= R_PSET2;
end
R_PSET2: begin
// positions [r_lo, r_hi - m_top]
{m_neg, r_hi} <= {1'b0, r_hi} - (BW+1)'(m_top);
r_state <= R_PSET3;
end
R_PSET3: begin
// steps from the group of word r_lo to the group of word
// (last position / 64) + 1, whose lane 0 computes the last word
r_highm <= ~64'd0 >> (6'd63 - r_hi[5:0]);
r_glast <= GW'(((WW+1)'(r_hi[BW-1:6]) + 1'b1) >> LW);
r_state <= (m_neg || r_hi < r_lo) ? R_DRAIN : R_ISSUE;
end
R_ISSUE: begin
if (r_bulk) begin
r_phase <= !r_phase;
if (r_phase) begin
if (r_g == r_glast) r_state <= R_DRAIN;
r_g <= r_g + 1'b1;
end
end else if (r_match && MK > 1) begin
if (r_sub == SBW'(MK - 1)) begin
if (r_g == r_glast || (r_find && r_found)) r_state <= R_DRAIN;
r_g <= r_g + 1'b1;
r_sub <= '0;
end else begin
if (r_find && r_found) r_state <= R_DRAIN;
r_sub <= r_sub + 1'b1;
end
end else begin
if (r_g == r_glast || (r_find && r_found)) r_state <= R_DRAIN;
r_g <= r_g + 1'b1;
end
end
R_DRAIN: if (!s1_valid && !s2_valid && !s3_valid && !s4_valid && !s5_valid && !s6_valid) begin
r_state <= R_IDLE;
r_done <= 1'b1;
end
default: r_state <= R_IDLE;
endcase
s1_valid <= s0_valid; s1_kind <= s0_kind; s1_g <= r_g; s1_sub <= r_sub;
s2_valid <= s1_valid; s2_kind <= s1_kind; s2_g <= s1_g; s2_sub <= s1_sub;
s3_valid <= s2_valid; s3_kind <= s2_kind; s3_g <= s2_g; s3_sub <= s2_sub;
s4_sub <= s3_sub; s5_sub <= s4_sub;
s4_valid <= s3_valid && (s3_kind == K_BITS || s3_kind == K_DST || s3_kind == K_MAT); s4_g <= s3_g;
s5_valid <= s4_valid; s5_g <= s4_g;
s6_valid <= s5_valid;
s6_sum <= s5_sum;
s6_any <= s5_any;
s6_idx <= {s5_word[WW-1:0], s5_pos[s5_first]};
if (s6_valid) begin
r_acc <= r_acc + CW'(s6_sum);
if (r_find && !r_found && s6_any) begin
r_found <= 1'b1;
r_idx <= s6_idx;
end
end
end
end
// ---------------------------------------------------------------- lanes
logic [SW-1:0] l_seq [LANES];
logic l_bit [LANES];
logic [63:0] rq [LANES]; // S3: registered bank data
logic [63:0] lane_rdata [LANES];
// host access: global word -> lane, local address
logic [LW-1:0] h_lane;
logic [AW-1:0] h_local;
assign h_lane = host_word[LW-1:0];
assign h_local = host_word[WW-1:LW];
logic h_pending;
logic [LW-1:0] h_lane_q;
// MATCH pattern capture (S3 of the K_PAT step)
always_ff @(posedge clk) begin
if (reset) begin
r_pat <= '0; r_msk <= '0;
end else begin
if (WITH_MATCH && s3_valid && s3_kind == K_PAT) begin
r_pat <= rq[r_pat_lane];
r_msk <= rq[r_msk_lane];
end
end
end
genvar g;
generate
for (g = 0; g < LANES; g++) begin : lane
// queue
logic [SW+AW+6+3-1:0] fifo [FIFO_DEPTH];
logic [FW:0] wp, rp;
logic full_q; // registered from the next-state pointers
assign q_full[g] = full_q;
assign q_empty[g] = (wp == rp);
always_ff @(posedge clk) begin
if (reset) begin
wp <= '0; rp <= '0; full_q <= 1'b0;
end else begin
full_q <= ((wp + (FW+1)'(q_push[g])) - (rp + (FW+1)'(q_pop[g]))) == (FW+1)'(FIFO_DEPTH);
if (q_push[g]) begin
fifo[wp[FW-1:0]] <= {d_seq, d_local, d_bit, d_op[2:0]};
wp <= wp + 1'b1;
end
if (q_pop[g]) rp <= rp + 1'b1;
end
end
assign {q_seq[g], q_local[g], q_bit[g], q_op[g]} = fifo[rp[FW-1:0]];
// bank: one write port, one synchronous read port (block RAM)
logic [63:0] bank [WORDS_PER_LANE];
logic we;
logic [AW-1:0] raddr, waddr;
logic [63:0] wdata, rdata;
always_ff @(posedge clk) begin
if (we) bank[waddr] <= wdata;
rdata <= bank[raddr];
end
// ---------------- single-bit execute: READ (address presented) -> MODIFY (data back, write)
logic st_mod;
logic [SW-1:0] x_seq;
logic [AW-1:0] x_local;
logic [5:0] x_bit;
logic [2:0] x_op;
logic [63:0] onehot, newword;
logic oldbit, newbit, writes;
assign onehot = 64'd1 << x_bit;
assign oldbit = rdata[x_bit];
always_comb begin
case ({1'b0, x_op})
OP_SET: begin newword = rdata | onehot; newbit = 1'b1; writes = 1'b1; end
OP_CLEAR: begin newword = rdata & ~onehot; newbit = 1'b0; writes = 1'b1; end
OP_TOGGLE: begin newword = rdata ^ onehot; newbit = !oldbit; writes = 1'b1; end
default: begin newword = rdata; newbit = oldbit; writes = 1'b0; end
endcase
end
assign q_pop[g] = !q_empty[g] && !st_mod;
assign l_busy[g] = st_mod || !q_empty[g];
always_ff @(posedge clk) begin
l_done[g] <= 1'b0;
if (reset) begin
st_mod <= 1'b0;
x_seq <= '0; x_local <= '0; x_bit <= '0; x_op <= '0;
l_seq[g] <= '0; l_bit[g] <= 1'b0;
end else if (st_mod) begin
st_mod <= 1'b0;
l_done[g] <= 1'b1;
l_seq[g] <= x_seq;
l_bit[g] <= newbit;
end else if (q_pop[g]) begin
st_mod <= 1'b1;
x_seq <= q_seq[g];
x_local <= q_local[g];
x_bit <= q_bit[g];
x_op <= q_op[g];
end
end
// ---------------- range datapath
// Per-operation constants (see the header): BULK dst element offset q
// and the local base addresses of the src and dst regions; MATCH: the
// local address of this lane's pattern-or-mask word.
logic [LW-1:0] q_off, src_sel;
logic [AW-1:0] sa, da, pa;
always_ff @(posedge clk) begin
if (reset) begin
q_off <= '0; src_sel <= '0; sa <= '0; da <= '0; pa <= '0;
end else if (r_state == R_INIT) begin
q_off <= LW'(g) - r_lo[LW-1:0];
// the src lane this dst lane takes its word from: (g - delta) mod LANES
src_sel <= LW'(LW'(g) - LW'(r_lo[LW-1:0] - r_src[LW-1:0]));
sa <= AW'(((WW+1)'(r_src) + (WW+1)'(LW'(LW'(g) - r_src[LW-1:0]))) >> LW);
da <= AW'(((WW+1)'(r_lo[WW-1:0]) + (WW+1)'(LW'(LW'(g) - r_lo[LW-1:0]))) >> LW);
// word src (pattern) or src + 1 (mask), whichever lives in this lane
pa <= AW'(((WW+1)'(r_src) + (WW+1)'(LW'(g) != r_src[LW-1:0])) >> LW);
end
end
// S1: registered read address
logic [AW-1:0] s1_raddr;
always_ff @(posedge clk) begin
if (reset) s1_raddr <= '0;
else case (s0_kind)
K_SRC: s1_raddr <= r_g[AW-1:0] + sa;
K_DST: s1_raddr <= r_g[AW-1:0] + da;
K_PAT: s1_raddr <= pa;
default: s1_raddr <= r_g[AW-1:0];
endcase
end
// S1 -> S2: where this lane's word lies in the range, from s1_g;
// S2 -> S3: its bit mask. Also the BULK element bound and write addresses.
logic [WW:0] wv; // word this lane's mask refers to
logic [WW:0] lo_w, hi_w;
logic s1_kvalid;
// MATCH: unit g checks the positions of word g*LANES + sub*MATCH_LANES + g - 1
assign wv = (s1_kind == K_MAT)
? (WW+1)'({s1_g, LW'(0)}) + (WW+1)'(s1_sub) * (WW+1)'(MATCH_LANES)
+ (WW+1)'(g) - (WW+1)'(1)
: {s1_g, LW'(g)};
assign lo_w = (WW+1)'(r_lo[BW-1:6]);
assign hi_w = (WW+1)'(r_hi[BW-1:6]);
assign s1_kvalid = ((WW+1)'({s1_g[AW-1:0], LW'(0)}) + (WW+1)'(q_off)) < r_n;
logic s2_in, s2_first, s2_last;
logic [63:0] s3_mask;
logic s2_kvalid, s3_kvalid;
logic [AW-1:0] s2_waddr, s3_waddr;
always_ff @(posedge clk) begin
if (reset) begin
s2_in <= 1'b0; s2_first <= 1'b0; s2_last <= 1'b0; s2_kvalid <= 1'b0; s2_waddr <= '0;
s3_mask <= '0; s3_kvalid <= 1'b0; s3_waddr <= '0; rq[g] <= '0;
end else begin
s2_in <= wv >= lo_w && wv <= hi_w;
s2_first <= wv == lo_w;
s2_last <= wv == hi_w;
s2_kvalid <= s1_kvalid;
s2_waddr <= s1_kind == K_DST ? s1_g[AW-1:0] + da : s1_g[AW-1:0];
s3_mask <= s2_in ? ((s2_first ? r_lowm : ~64'd0) & (s2_last ? r_highm : ~64'd0)) : 64'd0;
s3_kvalid <= s2_kvalid;
s3_waddr <= s2_waddr;
rq[g] <= rdata; // S2 -> S3: bank data registered
end
end
// Per-lane copies of the step's control (kept apart, so that no single
// control net fans out to every lane's 64-bit muxes). l_op/l_fn/l_dry
// follow r_op/r_fn/r_dry one cycle later, long before S3 uses them.
(* keep *) logic [2:0] l3_kind;
(* keep *) logic l3_valid;
(* keep *) logic [3:0] l_op;
(* keep *) logic [2:0] l_fn;
(* keep *) logic l_dry;
(* keep *) always_ff @(posedge clk) begin
if (reset) begin
l3_kind <= K_BITS; l3_valid <= 1'b0; l_op <= '0; l_fn <= '0; l_dry <= 1'b0;
end else begin
l3_kind <= s2_kind; l3_valid <= s2_valid; l_op <= r_op; l_fn <= r_fn; l_dry <= r_dry;
end
end
// S3 compute, from registered data
logic [63:0] src_q; // BULK: this dst lane's src word of the current step
logic [63:0] sel, fillword, srcw, bulkword, mvec;
assign sel = (l_op == OP_FIND0 ? ~rq[g] : rq[g]) & s3_mask;
always_comb begin
case (l_op)
OP_SETR: fillword = rq[g] | s3_mask;
OP_CLEARR: fillword = rq[g] & ~s3_mask;
default: fillword = rq[g] ^ s3_mask; // FLIPR
endcase
end
assign srcw = src_q;
always_comb begin
case (l_fn)
FN_COPY: bulkword = srcw;
FN_AND: bulkword = rq[g] & srcw;
FN_OR: bulkword = rq[g] | srcw;
FN_XOR: bulkword = rq[g] ^ srcw;
default: bulkword = rq[g] & ~srcw; // ANDN
endcase
end
if (WITH_MATCH && g < MATCH_LANES) begin : matcher
// positions p of word w - 1: window bits p .. p+63 of {word w, word w - 1},
// w = this sub-step's word idx of the group. Both are registered here at
// S2. For idx 0, word w - 1 is the last lane's word of the previous
// group (sub-steps issue on consecutive cycles), still in rq[LANES - 1].
logic [LW-1:0] idx;
logic [63:0] m_hi, m_lo;
logic [127:0] win;
// (s2_sub is 0 when MATCH_LANES == LANES, where LW'(MATCH_LANES) wraps to 0)
assign idx = LW'(LW'(s2_sub) * LW'(MATCH_LANES) + LW'(g));
always_ff @(posedge clk) begin
if (reset) begin
m_hi <= '0; m_lo <= '0;
end else begin
m_hi <= lane_rdata[idx];
m_lo <= (idx == '0) ? rq[LANES-1] : lane_rdata[LW'(idx - 1'b1)];
end
end
assign win = {m_hi, m_lo};
// this unit's copy of the pattern and mask (loaded in R_PSET1, before any
// MATCH step), so their bits do not fan out across all units
(* keep *) logic [63:0] u_pat, u_msk;
(* keep *) always_ff @(posedge clk) begin
if (reset) begin
u_pat <= '0; u_msk <= '0;
end else if (r_state == R_PSET1) begin
u_pat <= r_pat; u_msk <= r_msk;
end
end
always_comb
for (int p = 0; p < 64; p++) mvec[p] = ~|((win[p +: 64] ^ u_pat) & u_msk);
end else begin : no_matcher
assign mvec = '0;
end
// S3 -> S4: registered bank write and result word
logic w_we;
logic [AW-1:0] w_waddr;
logic [63:0] w_wdata, s4_word;
always_ff @(posedge clk) begin
if (reset) begin
w_we <= 1'b0; w_waddr <= '0; w_wdata <= '0; s4_word <= '0; src_q <= '0;
end else begin
w_we <= 1'b0;
w_waddr <= s3_waddr;
// the cross-lane rotation ends in this register
if (l3_valid && l3_kind == K_SRC) src_q <= rq[src_sel];
case (l3_kind)
K_DST: begin
w_we <= l3_valid && s3_kvalid && !l_dry;
w_wdata <= bulkword;
s4_word <= s3_kvalid ? bulkword : 64'd0;
end
K_MAT: s4_word <= (g < MATCH_LANES) ? (mvec & s3_mask) : 64'd0;
default: begin
w_we <= l3_valid && l3_kind == K_BITS && s3_mask != '0
&& (l_op == OP_SETR || l_op == OP_CLEARR || l_op == OP_FLIPR);
w_wdata <= fillword;
s4_word <= sel;
end
endcase
if (s4_valid) begin
s5_cnt[g] <= popcount64(s4_word);
s5_hit[g] <= s4_word != '0;
s5_pos[g] <= ctz64(s4_word);
end
end
end
// ---------------- bank port: range unit, else lane, else host (engine idle)
logic [AW-1:0] q_addr;
logic q_idle;
assign q_addr = q_local[g];
assign q_idle = q_empty[g];
always_comb begin
raddr = q_addr; we = 1'b0; waddr = x_local; wdata = newword;
if (r_busy) begin
raddr = s1_raddr; we = w_we; waddr = w_waddr; wdata = w_wdata;
end else if (st_mod) begin
we = writes;
end else if (q_idle && host_valid && host_ready && h_lane == LW'(g)) begin
raddr = h_local; waddr = h_local; we = host_write; wdata = host_wdata;
end
end
end
endgenerate
// ---------------------------------------------------------------- reorder buffer
logic [ROB_DEPTH-1:0] rob_full, rob_err, rob_bit, rob_rng;
logic [55:0] rob_val [ROB_DEPTH]; // written only by the range unit
logic [SW-1:0] head;
logic r_bitout;
logic [55:0] r_valout;
assign r_bitout = r_find ? r_found : (r_acc != '0);
assign r_valout = r_find ? (r_found ? 56'(r_idx) : 56'd0) : 56'(r_acc);
assign res_valid = rob_full[head];
assign res_error = rob_err[head];
assign res_bit = rob_bit[head];
assign res_value = rob_rng[head] ? rob_val[head] : 56'd0;
assign emit = res_valid && res_ready;
always_ff @(posedge clk) begin
if (r_done) rob_val[r_seq] <= r_valout;
end
always_ff @(posedge clk) begin
if (reset) begin
rob_full <= '0; rob_err <= '0; rob_bit <= '0; rob_rng <= '0; head <= '0; inflight <= '0;
end else begin
if (emit) begin
rob_full[head] <= 1'b0;
head <= head + 1'b1;
end
if (d_take && d_err) begin
rob_full[d_seq] <= 1'b1; rob_err[d_seq] <= 1'b1; rob_bit[d_seq] <= 1'b0; rob_rng[d_seq] <= 1'b0;
end
for (int i = 0; i < LANES; i++) begin
if (l_done[i]) begin
rob_full[l_seq[i]] <= 1'b1; rob_err[l_seq[i]] <= 1'b0; rob_bit[l_seq[i]] <= l_bit[i];
rob_rng[l_seq[i]] <= 1'b0;
end
end
if (r_done) begin
rob_full[r_seq] <= 1'b1; rob_err[r_seq] <= 1'b0; rob_bit[r_seq] <= r_bitout; rob_rng[r_seq] <= 1'b1;
end
inflight <= inflight_next;
end
end
// ---------------------------------------------------------------- host port
assign idle = (inflight == '0) && !p_valid && !d_valid && (l_busy == '0) && !r_busy && !h_pending;
assign host_ready = idle;
// A read's data is in the bank's output register in the cycle after the
// handshake, which is exactly when h_pending is high.
assign host_rvalid = h_pending;
always_ff @(posedge clk) begin
if (reset) begin
h_pending <= 1'b0; h_lane_q <= '0;
end else begin
h_pending <= host_valid && host_ready && !host_write;
if (host_valid && host_ready) h_lane_q <= h_lane;
end
end
generate
for (g = 0; g < LANES; g++) begin : rd
assign lane_rdata[g] = lane[g].rdata;
end
endgenerate
assign host_rdata = lane_rdata[h_lane_q];
logic unused_ok;
assign unused_ok = &{1'b0, src_x[64:WW], p_end[64:BW], s5_word[WW], r_pat}; // MATCH regs unused when WITH_MATCH = 0
endmodule