1
\$\begingroup\$

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
\$\endgroup\$
  • 5
    \$\begingroup\$ Is it a programming question or hardware? In hardware can be done in a single cycle with simple combinatorial logic. \$\endgroup\$ – Eugene Sh. Oct 23 '15 at 14:26
  • \$\begingroup\$ What encryption algorithm does this help you with? \$\endgroup\$ – pjc50 Oct 23 '15 at 14:43
  • \$\begingroup\$ Could you elaborate on your lookup table? How would that work exactly? I think you are aiming at a binary search. A true LOT will use a huge amount of memory. \$\endgroup\$ – jippie Oct 23 '15 at 15:22
  • 2
    \$\begingroup\$ I'm voting to close this question as off-topic because this question belongs on Stack Overflow. \$\endgroup\$ – Nick Johnson Oct 23 '15 at 15:36
  • \$\begingroup\$ @NickJohnson I never realized there are Verilog questions on SO. Wouldn't be my first place to lookt though. \$\endgroup\$ – jippie Oct 23 '15 at 16:08
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How would that compare in speed to just a lookup table with 64 items? It appears there would be quite a few clock cycles to get through these steps. \$\endgroup\$ – J Kula Oct 24 '15 at 19:29
  • \$\begingroup\$ A 64bits LZC has 64inputs and 7 outputs. Implemented as a table, it is 7 * (2**64) bits. Quite large. Impossibly large. Crazy large. Larger than the RAM of all supercomputers on earth. \$\endgroup\$ – TEMLIB Oct 24 '15 at 19:39
  • \$\begingroup\$ Maybe you are thinking about "content adressable memory", used mostly in network equipment. It could be possible to store a priority encoder in one such memory, but the circuit complexity is far larger than the solution above. \$\endgroup\$ – TEMLIB Oct 24 '15 at 19:42
  • \$\begingroup\$ @TEMLIB: Nice trick, I didn't know this one. Upvoted. It deserves a comparison with the other natural divide-and-conquer approach. \$\endgroup\$ – Renaud Pacalet Oct 25 '15 at 5:41
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.