Verilog - Synthesize High Speed Leading Zero Count

Question

Using Verilog how do I synthesize the fastest leading zero count on a 64-bit number?

Initially I went with a CASEX(..), with a lot of 01xxxxx, 001xxxxx lines but I understand this synthesizes a barrel shifter which I'm not sure is quick.

My ask is this, what's the fastest way to get to output... what would the gates look like?

I finally came up with this solution but not sure if it will synthesize to something quicker than the above.

The answer to leading zeros in a 64 bit number is either the number of leading zeros in the first 32 bits (if any is a non-zero) or it's 32 + the number of leading zeros in the lower 32 bits. That gives you the answer to the 6th bit of the answer. You then need to find the number of leading zeros in the 32 bit number, so apply the same rules. I had to do an If/else to deal with all zeros.

VERILOG:

// Leading zero count of Sj
  if (Sj_int[63:0] == 64'b0)
   tmp_cnt = 64;
  else
   begin
    tmp_cnt[6] = 1'b0;
    tmp_cnt[5] = (Sj_int[63:31] == 32'b0);
    val32 = tmp_cnt[5] ? Sj_int[31:0] : Sj_int[63:32];
    tmp_cnt[4] = (val32[31:16] == 16'b0);
    val16 = tmp_cnt[4] ? val32[15:0] : val32[31:16];
    tmp_cnt[3] = (val16[15:8] == 8'b0);
    val8 = tmp_cnt[3] ? val16[7:0] : val16 [15:8];
    tmp_cnt[2] = (val8[7:4] == 4'b0);
    val4 = tmp_cnt[2] ? val8[3:0] : val8[7:4];
    tmp_cnt[1] = (val4[3:2] == 2'b0);
    tmp_cnt[0] = tmp_cnt[1] ? ~val4[1] : ~val4[3];
   end
   o_Si <= tmp_cnt[6:0];
 end

Answer 1

Leading zero encoders can be made with a nice balanced tree structure.

First, encode bits 2 by 2 :

• 00 => 10 : 2 leading zeros
• 01 => 01 : 1 leading zero
• 10 => 00 : 0 leading zero
• 11 => 00 : 0 leading zero

Then, assemble as pairs.

• If both sides start with 1xxx, the result is 10...0
• If the left side start with 0 the result is 0[left]
• If the left side starts with 1, the result is 01[right(msb-1:0)]

You only need multiplexers.

For example the 8 bits value : 00000111

• 2 by 2 : 00 00 01 11
• encoded : 10 10 01 00
• assemble : 100 001
• assemble : 0101 = 5 leading zeros.

In VHDL (I have no Verilog code at hand), you get that :

FUNCTION enc(CONSTANT a : unsigned(1 DOWNTO 0)) RETURN unsigned IS
BEGIN
  CASE a IS
    WHEN "00" => RETURN "10";
    WHEN "01" => RETURN "01";
    WHEN "10" => RETURN "00";
    WHEN OTHERS => RETURN "00";
  END CASE;
END FUNCTION enc;

FUNCTION clzi(
  CONSTANT n : IN natural;
  CONSTANT i : IN unsigned) RETURN unsigned IS
  VARIABLE v : unsigned(i'length-1 DOWNTO 0):=i;  
BEGIN
  IF v(n-1+n)='0' THEN
    RETURN (v(n-1+n) AND v(n-1)) & '0' & v(2*n-2 DOWNTO n);
  ELSE
    RETURN (v(n-1+n) AND v(n-1)) & NOT v(n-1) & v(n-2 DOWNTO 0);
  END IF;
END FUNCTION clzi;

FUNCTION clz64 (CONSTANT v : unsigned(0 TO 63)) RETURN unsigned IS
  VARIABLE e : unsigned(0 TO 63);     -- 64
  VARIABLE a : unsigned(0 TO 16*3-1); -- 48
  VARIABLE b : unsigned(0 TO 8*4-1);  -- 32
  VARIABLE c : unsigned(0 TO 4*5-1);  -- 20
  VARIABLE d : unsigned(0 TO 2*6-1);  -- 12
BEGIN
  FOR i IN 0 TO 31 LOOP e(i*2 TO i*2+1):=enc(v(i*2 TO i*2+1));  END LOOP;
  FOR i IN 0 TO 15 LOOP a(i*3 TO i*3+2):=clzi(2,e(i*4 TO i*4+3)); END   LOOP;
  FOR i IN 0 TO 7  LOOP b(i*4 TO i*4+3):=clzi(3,a(i*6 TO i*6+5)); END   LOOP;
 FOR i IN 0 TO 3  LOOP c(i*5 TO i*5+4):=clzi(4,b(i*8 TO i*8+7)); END LOOP;
 FOR i IN 0 TO 1  LOOP d(i*6 TO i*6+5):=clzi(5,c(i*10 TO i*10+9)); END LOOP;
 RETURN clzi(6,d(0 TO 11));
END FUNCTION clz64;

enc() does the encoding clzi() merges two vectors. clz64() is a sample implementation for a 64bits input.

Answer 2

I've just rewrote previous (and brilliant) solution on Verilog.

module enc
(
   input wire     [1:0]       d,
   output logic   [1:0]       q
);

   always_comb begin
      case (d[1:0])
         2'b00    :  q = 2'b10;
         2'b01    :  q = 2'b01;
         default  :  q = 2'b00;
      endcase
   end

endmodule // enc

module clzi #
(
   // external parameter
   parameter   N = 2,
   // internal parameters
   parameter   WI = 2 * N,
   parameter   WO = N + 1
)
(
   input wire     [WI-1:0]    d,
   output logic   [WO-1:0]    q
);

   always_comb begin
      if (d[N - 1 + N] == 1'b0) begin
         q[WO-1] = (d[N-1+N] & d[N-1]);
         q[WO-2] = 1'b0;
         q[WO-3:0] = d[(2*N)-2 : N];
      end else begin
         q[WO-1] = d[N-1+N] & d[N-1];
         q[WO-2] = ~d[N-1];
         q[WO-3:0] = d[N-2 : 0];
      end
   end

endmodule // clzi

Answer 3

You can use recursion to implement your binary-search type thing succinctly.

module count_lead_zero #(
    parameter W_IN = 64, // Must be power of 2, >=2
    parameter W_OUT = $clog2(W_IN) // Let this default
) (
    input wire  [W_IN-1:0] in,
    output wire [W_OUT-1:0] out
);

generate
if (W_IN == 2) begin: base
    assign out = !in[1];
end else begin: recurse
    wire [W_OUT-2:0] half_count;
    wire [W_IN / 2-1:0] lhs = in[W_IN / 2 +: W_IN / 2];
    wire [W_IN / 2-1:0] rhs = in[0        +: W_IN / 2];
    wire left_empty = ~|lhs;

    count_lead_zero #(
        .W_IN (W_IN / 2)
    ) inner (
        .in  (left_empty ? rhs : lhs),
        .out (half_count)
    );

    assign out = {left_empty, half_count};
end
endgenerate

endmodule

Yosys synth results for 64 bits:

=== count_lead_zero ===

   Number of cells:                121
     $_ANDNOT_                       1
     $_AOI3_                         1
     $_MUX_                         56
     $_NOR_                          1
     $_NOT_                          7
     $_ORNOT_                        1
     $_OR_                          54

It's fairly compact, but critical path will be through one mux layer and one NOR reduction per stage (since the reduction trees don't start computing correct output til their inputs are valid), which works out to ~20 logic levels to get the LSB. I imagine the other solution with the balanced tree would be faster but similarly-sized.

Note that this will give an output of 63 (all-ones) if given an all-zeroes input; you didn't specify this in your question so not sure if this is needed. This is simple and cheap to amend: do a NOR reduction on the whole input, concatenate this bit to the LHS of the result, and mask off the rest of the result when this bit is set.