32bit_me (32bit_me) wrote,
32bit_me
32bit_me

Считаем нули

Рассмотрим теперь операцию нахождения количества ведущих нулей (то есть нулей, находящихся слева).



Напишем сначала самую простую реализацию, совсем очевидным образом:

module zeroes (
  input wire rst_n,
  input wire clk,
  input wire [31: 0] in,
  output reg [5: 0] out_reg
);

reg [31: 0] in_reg;
  
always@(posedge clk, negedge rst_n)
begin
  if(!rst_n)
  begin
    out_reg <= 0;
    in_reg <= 0;
  end
  else
  begin  
    in_reg <= in;
    out_reg <= trailing_zeroes(in_reg);
  end
end

function [5: 0] trailing_zeroes;
  input [31: 0] in;
  integer i;
  begin: count
    for(i = 31; i >= 0; i = i - 1)
    begin
      if(in[i])
      begin
        trailing_zeroes = 31 - i;
        disable count;
      end
    end
	 trailing_zeroes = 31;
  end
endfunction

endmodule


Синтезируем, получаем (для Cyclone 10LP speed grade 6):

Total logic elements 59 / 6,272 ( < 1 % )
Total registers 38

Fmax = 259,88 MHz (restricted 250 MHz)

Совсем неплохо, учитывая, что комбинаторная цепочка довольно длинная (кликабельно):



И, наконец, тест модуля (кликабкльно):



Вариант 2.

Мы видим, что функция достаточно хорошо реализована, но можно ли сделать её ещё лучше?

Напишем так:

module zeroes2 (
  input wire rst_n,
  input wire clk,
  input wire [31: 0] in,
  output reg [5: 0] out_reg
);

reg [31: 0] in_reg;
  
wire zeroes_5 = in_reg == 31'h0000_0000;

wire zeroes_4 = !zeroes_5 && (in_reg[31: 16] == 16'h0000);

wire zeroes_3 = !zeroes_5 && (zeroes_4? (in_reg[15: 8] == 8'h00) : (in_reg[31: 24] == 8'h00));

wire zeroes_2 = !zeroes_5 && (zeroes_4? (zeroes_3? (in_reg[7: 4] == 4'h0) : (in_reg[15: 12] == 4'h0)) :
                                        (zeroes_3? (in_reg[23: 20] == 4'h0) : (in_reg[31: 28] == 4'h0)));
								  
wire zeroes_1 = !zeroes_5 && (zeroes_4? (zeroes_3? (zeroes_2? (in_reg[3: 2] == 2'b00) : (in_reg[7: 6] == 2'b00)) : 
                                                  (zeroes_2? (in_reg[11: 10] == 2'b00) : (in_reg[15: 14] == 2'b00))) :
                                       (zeroes_3? (zeroes_2? (in_reg[19: 18] == 2'b00) : (in_reg[23: 22] == 2'b00)) : 
								                          (zeroes_2? (in_reg[27: 26] == 2'b00) : (in_reg[31: 30] == 2'b00))));

wire zeroes_0 = !zeroes_5 && (zeroes_4? (zeroes_3? (zeroes_2? (zeroes_1? (in_reg[1] == 1'b0) : (in_reg[3] == 1'b0)) :
                                                              (zeroes_1? (in_reg[5] == 1'b0) : (in_reg[7] == 1'b0))) : 
                                                   (zeroes_2? (zeroes_1? (in_reg[9] == 1'b0) : (in_reg[11] == 1'b0)) :
											 	                          (zeroes_1? (in_reg[13] == 1'b0) : (in_reg[15] == 1'b0)))) :
                                        (zeroes_3? (zeroes_2? (zeroes_1? (in_reg[17] == 1'b0) : (in_reg[19] == 1'b0)) :
                                                              (zeroes_1? (in_reg[21] == 1'b0) : (in_reg[23] == 1'b0))) : 
                                                   (zeroes_2? (zeroes_1? (in_reg[25] == 1'b0) : (in_reg[27] == 1'b0)) :
												                          (zeroes_1? (in_reg[29] == 1'b0) : (in_reg[31] == 1'b0)))));
												 
always@(posedge clk, negedge rst_n)
begin
  if(!rst_n)
  begin
    out_reg <= 0;
    in_reg <= 0;
  end
  else
  begin  
    in_reg <= in;
    out_reg <= {zeroes_5, zeroes_4, zeroes_3, zeroes_2, zeroes_1, zeroes_0};
  end
end

endmodule


Запускаем тест, всё работает. Временная диаграмма теста выглядит точно так же, как и показанная выше, не будем её повторять.

Посмотрим на RTL (просто ради любопытства):



А теперь результаты синтеза:

Total logic elements 48 / 6,272 ( < 1 % )
Total registers 38

Расход LE уменьшился на целых 11 штук!

Fmax = 159,08 MHz

Итак, мы видим, что, хотя общий объём комбинаторики уменьшился и (визуально) цепи стали не такими длинными, частота сильно просела, хотя и остаётся достаточно высокой. Поэтому пока что выбор между двумя этими вариантами не вполне очевиден.
Tags: fpga, verilog
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 18 comments