Find First Set Bit: Three RTL Architectures

The Three Designs

Fmax = 1 / (logic levels x 20 ps). Wire delay and setup time excluded. Yosys + ASAP7-approximate 7nm.

• Sequential FSM: Largest by cell count (322), worst latency (up to 66 cycles), but the only design whose switching activity per clock cycle is bounded to a single shift and compare. Right for infrequent, non-time-critical control paths where dynamic power matters more than latency.
• Combinational binary tree: Fewest cells (168), fewest FFs (8), single-cycle result. The deepest critical path of the three at 20 logic levels, but a 3x improvement over a naive casez encoder. Right when area and zero-latency combinational output are the priority.
• Pipeline: Highest Fmax (~8.3 GHz), shallowest critical path (6 levels), one result per cycle after a 6-cycle fill. Right for streaming throughput workloads. Stage count is a first-class parameter.

The sections below go through each architecture in detail.

Which Architecture for Your Constraint?

Architecture 1: Sequential FSM + Shift Register

Design intent: Minimum dynamic switching activity for infrequent, non-time-critical control paths.

By cell count this is the largest of the three at 322 cells. The 64-bit shift register alone accounts for most of that. The advantage is not static area. It is dynamic power. Each cycle, only a shift register and a comparator are switching. The combinational tree switches all 168 cells on every clock edge regardless of how often the result is needed. For a block that runs once every few hundred cycles in a larger SoC, that difference in average switching activity matters. The 66-cycle worst-case latency is irrelevant if the calling context never issues back-to-back requests. The architectural decision is not the implementation. It is knowing when that trade-off is acceptable.

A three-state FSM (IDLE -> RUNNING -> DONE) walks through the input one bit per cycle, shifting right and checking bit 0. When a set bit is found, the cycle count becomes the result. When all bits are exhausted, no_set is asserted.

RUNNING: begin
    if (shift_reg[0]) begin                  // found the lowest set bit
        result <= counter;
        no_set <= 1'b0;
        state  <= DONE;
    end else if (counter == CNT_MAX) begin   // all bits checked, none set
        result <= '0;
        no_set <= 1'b1;
        state  <= DONE;
    end else begin                           // keep searching
        shift_reg <= shift_reg >> 1;
        counter   <= counter + 1'b1;
    end
end

The critical path is deliberately shallow: counter FF, 6-bit comparator, FSM state FF. Seven gate levels. This is a direct consequence of keeping the combinational cone small by design, not an accident.

One early-draft mistake worth flagging: an intermediate version staged result and no_set through holding registers (result_r, no_set_r) that forwarded values once DONE pulsed valid_out. That cost 7 flip-flops for zero functional gain; the outputs are held stable in DONE regardless. Eliminating those registers dropped the design from 88 to 81 FFs.

Real numbers (W=64):

The 4.0-cycle average reflects the geometric distribution of real data: roughly half of all 64-bit values have bit 0 set and exit in 3 cycles, a quarter exit at 4 cycles, and so on. An MSB-only input (64'h8000_0000_0000_0000) takes the full 66 cycles: 63 shifts to bring bit 63 down to position 0, plus the IDLE and DONE state transitions. The distribution is heavy on the left, which is why the average is close to the minimum rather than the midpoint.

The sequential design is the only one of the three whose average-case latency is data-dependent, which is a relevant consideration when profiling a production workload.

Architecture 2: Combinational Parallel Binary Tree

Design intent: Single-cycle result, no state, no iteration, pure logic.

The first instinct for a combinational FFS is usually data & (~data + 1) to isolate the lowest set bit, then feed that into a one-hot-to-binary encoder. Or a casez priority encoder that directly maps each input pattern to an output index. Both look clean on paper. In silicon, both produce an O(N) gate chain: 64 logic levels for W=64. At 7nm (~18 ps/level), that is ~1.15 ns of combinational delay before any wire or setup margin. Under a 2 GHz clock target that is already a failing path. Push it through to P&R and the deep logic cone causes routing congestion around the output mux chains.

The right structure is a balanced binary mux tree, generated at elaboration time using generate/genvar. Each of the 6 stages halves the search window:

1. OR-reduce the lower half (does a set bit exist there?)
2. Select lower or upper half based on that result
3. Contribute one bit to the output index: 0 = went lower, 1 = went upper

assign lo_has_bit      = |stage_win[i][HALF-1:0];
assign next_win        = lo_has_bit ? stage_win[i][HALF-1:0]
                                    : stage_win[i][WSIZE-1:HALF];
assign stage_win[i+1]  = {{(W-HALF){1'b0}}, next_win};
assign result_bits[RIDX] = ~lo_has_bit;

This is where generate/genvar is not a code-reuse trick. It is how parallel hardware is constructed. A for loop in synthesizable RTL creates a sequential chain where each iteration depends on the previous, producing O(N) depth. generate runs at elaboration time, producing parallel hardware with fixed-width part-selects per iteration. There is no software analog to this distinction.

Six stages at 2 gate levels each gives a theoretical depth of 12 levels. Synthesis measured 20. The theory assumes each OR-reduce takes 1 gate level; the reality is that each stage’s OR-reduce takes log2(window width) levels. Stage 0 reduces 32 bits and adds 4 extra levels, stage 1 reduces 16 bits and adds 3, stage 2 adds 2, stages 3 and 4 add 1 each. Those compound to an 8-level gap between theory and measurement. Still a 3x improvement over a casez encoder.

A note on synthesis tool behavior: Under tight clock constraints, DC/FC will attempt to retime and restructure the OR-reduce trees. If your SDC does not properly constrain input arrival times and output required times on this block, the tool may optimize for a path you did not intend, inflating area to buy timing margin without flagging a violation. Constrain this block explicitly.

Real numbers (W=64):

The gap between theoretical (12 levels) and measured (20) is a useful calibration point. Synthesis sees the netlist, not your intent. Run the tools before committing to a clock target.

Architecture 3: 6-Stage Pipeline Binary Search

Design intent: One result per cycle throughput with a deterministic, timing-closure-friendly critical path.

The pipeline takes the same binary search from Architecture 2 and cuts it into 6 register stages, one per level of the binary search. Each stage does exactly 2 gate levels of work: an OR-reduce and a mux. The critical path per stage is 2 gate levels, roughly 40 ps at 7nm, well clear of any reasonable clock target.

Stage: | OR+mux |--FF--| OR+mux |--FF--| OR+mux |--FF--| ... |--> result
                        2 gate levels per stage

After a 6-cycle fill latency, one result emerges every clock cycle regardless of input:

Cycle:     1    2    3    4    5    6    7    8    9
Input:     A    B    C    .    .    .    .    .    .
valid_out: 0    0    0    0    0    0    1    1    1
result:    .    .    .    .    .    .    A    B    C

The binary tree underlying Architecture 2 is inherently register-friendly: stage boundaries are explicit, each stage is independently bounded at 2 gate levels, and valid/no_set propagate in-band alongside the data. Architecture 3 is the fully-pipelined form of that same tree. For integration into a larger datapath, this means the latency/throughput balance is a first-class parameter. Reducing from 6 to 3 stages doubles the per-stage critical path but halves the fill latency. That is the right call for bursty workloads that cannot absorb 6 cycles of startup cost. No logic restructuring required, only the stage count changes.

The implementation propagates four arrays through the pipeline: the narrowing search window (pipe_win), the accumulating result bits (pipe_res), the valid flag, and the no-set flag.

always_comb begin          // default-then-override: latch-free result accumulation
    nxt_res       = pipe_res[i];   // carry forward all prior bits
    nxt_res[RIDX] = ~lo_has_bit;   // this stage contributes one new bit
end

always_ff @(posedge clk) begin
    if (!rst_n) begin ... end
    else begin
        pipe_win[i+1] <= nxt_win_w;
        pipe_res[i+1] <= nxt_res;
        pipe_vld[i+1] <= pipe_vld[i];
        pipe_nst[i+1] <= pipe_nst[i];
    end
end

On the FF count: The theoretical register budget is 432 FFs: pipe_win at 64 bits x 6 stages (384), pipe_res at 6 bits x 6 stages (36), plus pipe_vld and pipe_nst at 1 bit x 6 stages each (12). Synthesis produced 90. Yosys/ABC eliminated the zero-padded upper bits of pipe_win at each stage since they carry no information forward; by stage 3, only 8 bits of the search window are live. The 432-to-90 reduction (79%) is routine constant propagation, but the magnitude is a useful reminder that theoretical and post-synthesis register counts are not the same number.

Real numbers (W=64):

Architect’s Notes

The All-Zeros Hazard

The most common downstream bug from an FFS unit: the block returns index 0 for an input of 64'h0000_0000_0000_0000. Index 0 is also a valid result when bit 0 is legitimately set. Without a qualifying no_set signal, the consumer cannot distinguish between the two cases. If a downstream scheduler or arbiter processes the result without checking no_set, the result is a silent functional bug that will not appear in simulation unless the testbench explicitly covers the all-zero input, and most randomly-generated test suites will not generate it at statistically meaningful frequency.

Every architecture here drives an explicit no_set flag synchronized to valid_out. In the sequential design it is a single output register. In the pipeline it propagates as pipe_nst through all 6 stages. Either way, the cost is negligible. Not driving it is a design error, not a design choice.

Simulation vs. Synthesis Mismatches

Two patterns to watch in priority encoder designs:

Behavioral loop variables. A for loop in an always_comb block with a loop variable not bounded by a static parameter can produce simulation mismatches against the synthesized netlist. The simulator unrolls it one way; the synthesis tool may infer a different structure. Always bind loop bounds to parameter or localparam values and verify the gate-level simulation matches the RTL simulation.

Reset coverage. If result is not explicitly driven to a known value on reset, synthesis may legally optimize away the reset path under the SDC. The RTL simulation sees X cleared by the initial block; the gate-level sim sees whatever the flip-flops power up to. The fix is a defined reset value on every registered output, not an initial block.

Scaling Beyond 64 Bits

The sequential design scales linearly: W+2 cycles worst case (one cycle for IDLE, W cycles through RUNNING, one cycle for DONE). For W=64 that is the 66-cycle maximum in the results table. The combinational tree scales in O(log N) stages but the OR-reduce fan-in compounds: at W=256 you have 8 binary tree levels, but the first OR-reduce spans 128 bits and adds log2(128) = 7 gate levels on top of that. The pipeline is the only architecture that scales predictably: exactly log2(W) register stages, each with 2 gate levels of logic, regardless of width. If the target is 256-bit FFS at 3+ GHz, the pipeline is the only architecture that can realistically get there.

Verification

The test suite is structured in three tiers, each designed to catch a different category of failure.

Tier 1: Directed tests (71 vectors, Icarus Verilog)

Hand-written to cover the specific boundary conditions that random testing misses or finds too slowly to be useful:

• 64'h0000_0000_0000_0000: the all-zeros input. Must assert no_set and must not return 0 as a valid index. This is the most common silent bug in FFS implementations and the first test written.
• 64'hFFFF_FFFF_FFFF_FFFF: all-ones. Result must always be 0, since bit 0 is always the LSB. Verifies the OR-reduce tree correctly identifies the lower half on every stage.
• Power-of-2 sweep, 64'h1 << n for n in [0..63]: 64 tests that together exercise every possible output value exactly once. This is the only way to guarantee the full 6-bit result encoding is correct across all 64 bit positions without running an exhaustive 64-bit sweep.
• Alternating patterns: 64'h5555_5555_5555_5555 (LSB at bit 0, result=0) and 64'hAAAA_AAAA_AAAA_AAAA (LSB at bit 1, result=1), interleaved set/clear bits that stress-test the lower-half OR-reduce decision at every stage of the binary tree.
• Additional edge cases covering back-to-back transactions, reset behavior, and known worked examples to reach 71 total.

Tier 2: Random vectors (10,000 vectors, Icarus Verilog)

Seeded pseudo-random 64-bit inputs for breadth coverage across arbitrary patterns. Combined with the directed tests, this gives 10,071 Icarus simulation vectors total.

Tier 3: Exhaustive sweep (65,536 + 1,000 vectors per design, Verilator)

The exhaustive 16-bit sweep tests every possible input at the W=16 parameterization. No coverage argument is needed; the input space is simply enumerated. This provides a mathematical completeness guarantee for the parameterized core logic at that width, and the same structural paths that handle W=16 handle W=64. The additional 1,000 random 64-bit vectors confirm the full-width design on top of that foundation.

All three designs were verified against a software golden model that computes the correct answer via a naive for-loop. The comparison is ground truth by definition, not by approximation.

Automation and Methodology

Benchmarking three architectures across multiple bit-widths by hand does not scale and does not reproduce. I wrote a Python wrapper that:

1. Parameterizes the RTL by sweeping W across [8, 16, 32, 64]
2. Generates a Yosys synthesis script per configuration from a template
3. Invokes synthesis, parses the log, and extracts cell count, FF count, and logic depth
4. Dumps results to a CSV for comparison across configurations

This turns a tedious manual process into a single make benchmark command with reproducible, version-controlled output.

make syntax    ✅  All 3 RTL files pass
make sim       ✅  10,071 vectors, 0 failures   (Icarus Verilog 12.0)
make verilator ✅  66,536 vectors x 3 designs, 0 failures   (Verilator 5.032)
make synth     ✅  Yosys 0.52 + ASAP7-approximate 7nm
make benchmark ✅  Area, Fmax, and logic depth extracted across W=[8,16,32,64]

What I Learned

Latency and Fmax are not the same thing. The pipeline has the shallowest critical path (6 levels, ~8.3 GHz). The sequential is close behind at 7 levels and ~7.1 GHz. Yet the sequential has the worst latency of the three at up to 66 cycles, while the pipeline delivers a result every cycle after fill. High Fmax means the clock can tick fast. It says nothing about how many ticks an answer takes. This trips up most people the first time they reason through it.

generate is not shorthand. It is how parallel hardware exists. A for-loop in RTL produces a chain. generate produces parallel structures. There is no software analog: you cannot write a for-loop that creates independent parallel hardware. This is the difference between RTL that synthesizes to what you intended and RTL that synthesizes to something O(N) slower.

Every flip-flop should be justified. I saved 7 FFs in the sequential design by eliminating staging registers that served no purpose. I accepted a 6-stage pipeline structure because each stage buys a shallower critical path and deterministic latency. The actual FF count is synthesis’s to decide, not mine. Area does not improve itself. You have to look at every register and ask: is this doing something?

Synthesis trimming is substantial and unpredictable. The pipeline had 432 theoretical FFs on paper; synthesis produced 90. The combinational design had a theoretical 12-level depth; synthesis measured 20. RTL-level estimates without running the tools are unreliable. Run the tools.

Directed tests catch what random tests miss. The all-zeros hazard, the most common FFS bug, would appear in a random 64-bit test suite at a rate of 1 in 2^64. It was the first directed test written and it would never have appeared naturally. A well-structured test suite is a design artifact, not an afterthought.

Why This Matters

Find First Set is not a textbook exercise. It is a timing-critical primitive that appears at the heart of some of the most latency-sensitive datapaths in modern silicon:

• Instruction schedulers scan a ready-bit vector every cycle to locate the next eligible instruction slot
• Network packet arbiters pick the highest-priority non-empty queue from a 64-bit occupancy mask
• GPU warp schedulers select the next eligible thread group from a ready-mask on every clock edge
• Cache radix-tree walkers traverse compressed address bitmaps one FFS per level
• Out-of-order execution engines use it to find a free ROB entry or physical register slot

At 16 bits, any implementation closes timing. At 64 bits above 2 GHz, it is a known critical path bottleneck. Scale to 256 or 512 bits in a high-performance compute block and a naive combinatorial implementation will single-handedly wreck your WNS budget before you reach P&R.

I built three independent SystemVerilog implementations from scratch, each representing a deliberate point in the area/latency/throughput design space. The goal was not to find one winner in the abstract. It was to understand the trade-off surface deeply enough to know which architecture is right for a given constraint set. All three were synthesized against an ASAP7-approximate 7nm library and verified across a structured three-tier test suite.

Tools

-> View on GitHub