問題
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があるか
を階層的に解いていくのが本質らしい。