FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

半導体フロントエンド設計・100本ノック Day31:Leading Zero Counter

問題

DATA_W bitの入力について、MSB側から連続する0の数を求めるLeading Zero Counter(LZC)を実装する。

入力がすべて0の場合はo_count = DATA_W、o_zero = 1とする。まずはMSBから探索するpriority encoder型で実装し、さらにtree構造にした場合のtimingについて考える。

Leading Zero Counterを作る

やること自体は、MSBから順番に見て最初の1が出てくるまで0を数えるだけ。

logic [$clog2(DATA_W+1)-1:0] w_zero_count;
logic                         w_found;

o_countにはall-zeroの場合DATA_Wそのものを出す必要がある。

例えばDATA_W=32なら、

$clog2(32) = 5

だが、5bitで表現できるのは0~31なので32が入らない。

そのため幅は、

$clog2(DATA_W+1)

としている。

実装はMSBからLSBへ探索する。

always_comb begin
  w_zero_count = 0;
  w_found      = 0;

  for (int i = DATA_W-1; i >= 0; i--) begin
    if (!w_found) begin
      if (i_data[i]) begin
        w_found = 1'b1;
      end else begin
        w_zero_count = w_zero_count + 1;
      end
    end
  end

  o_count = w_zero_count;
end

最初は1を見つけた後にcounterをincrementしてしまったが、当然逆だった。Leading Zeroなので、まだ1を見つけていない間の0を数える。

all-zeroの場合は最後までw_foundが立たないので、自然にDATA_W回incrementされる。特別な処理を入れなくてもo_count=32になる。

zero flagはreduction ORで作る。

assign o_zero = ~|i_data;

全体は以下。

module leading_zero_counter #(
    parameter int DATA_W = 32
) (
    input  logic [DATA_W-1:0]           i_data,
    output logic [$clog2(DATA_W+1)-1:0] o_count,
    output logic                        o_zero
);

  logic [$clog2(DATA_W+1)-1:0] w_zero_count;
  logic                         w_found;

  always_comb begin
    w_zero_count = '0;
    w_found      = 1'b0;

    for (int i = DATA_W-1; i >= 0; i--) begin
      if (!w_found) begin
        if (i_data[i]) begin
          w_found = 1'b1;
        end else begin
          w_zero_count = w_zero_count + 1'b1;
        end
      end
    end

    o_count = w_zero_count;
  end

  assign o_zero = ~|i_data;

endmodule

いくつか確認すると、

8000_0000 → count=0
0000_0001 → count=31
0000_0000 → count=32
00F0_0000 → count=8

となる。

32'h00F0_0000では最初の1はbit23なので、その上に8bitの0がある。

Priority chainになる

機能的にはこれで正しいが、回路構造を考えると少し気になる。

このRTLは概念的には、

bit31は1か?
 ↓
まだ見つからない
 ↓
bit30は1か?
 ↓
まだ見つからない
 ↓
bit29は1か?
 ...

というpriority chainになっている。

合成ツールが最適化する余地はあるが、設計意図としては入力幅に対して線形に依存する構造になる可能性がある。

32-bit程度ならそれほど問題にならなくても、64/128/256-bitと広くしていくとtimingが気になる。

そこでtree型のLZCを考える。

まず32-bitをupper/lowerの16-bitへ分割する。

               32bit
             /       \
        upper16     lower16

upper側に1があるなら答えはupper16のLZC、upper側が全部0なら、

16 + LZC(lower16)

になる。

同じことを再帰的に、

32 → 16 → 8 → 4 → 2 → 1

と分割していけば、判定の深さをおおむねlog2(DATA_W)にできる。

最初は16-bit LZCを複数並べればよいかと考えたが、それだけでは「MSB側から最初にnon-zeroだったblockはどれか」というpriority selectionが別途必要になる。

結局LZCでは、

どの領域に最初の1があるか
+
その領域内で何個0があるか

を階層的に解いていくのが本質らしい。