半導体フロントエンド設計100本ノック、第9問。
今回は複数のrequest bitのうち、最下位bit側から最初に立っているbitを選択するPriority Encoderを作る。
固定優先度のencoderそのものは単純だが、request数をparameter化した場合にどう書くか、またRTL上の記述と合成後の回路構造をどう考えるかがポイントになる。
問題
以下のようなPriority Encoderを作る。
module priority_encoder #( parameter int NUM_REQ = 8 ) ( input logic [NUM_REQ-1:0] i_req, output logic o_valid, output logic [NUM_REQ-1:0] o_grant, output logic [$clog2(NUM_REQ)-1:0] o_index );
LSB側を最高優先度とする。
例えば、
i_req = 8'b10110100
なら、最下位にある1はbit 2なので、
o_grant = 8'b00000100 o_index = 2 o_valid = 1
となる。
i_req='0 の場合は o_valid=0 とする。
o_grant は常にone-hotまたはall-zeroでなければならない。
まず素直に考える
LSB側から順番にrequestを見ていき、最初に見つかった1だけをgrantすればよい。
固定bit数なら、
if (i_req[0]) begin ... end else if (i_req[1]) begin ... end else if (i_req[2]) begin ... end
と書ける。
ただし NUM_REQ をparameter化したいので、これを for 文で一般化したい。
問題は、単純に、
for (int i = 0; i < NUM_REQ; i++) begin if (i_req[i]) begin o_grant[i] = 1'b1; end end
とすると、立っているrequestがすべてgrantされてしまうこと。
「それより下位bitにrequestが存在しない」という条件が必要になる。
lower bitにrequestがあったかを保持する
そこで、LSB側から現在位置までにrequestが存在したかどうかを表す信号を作る。
logic [NUM_REQ:0] w_ignore;
w_ignore[i] を、
bit i より下位に、すでにrequestが存在したか
という意味にする。
最初は下位bitが存在しないので、
w_ignore[0] = 1'b0;
とする。
各bitについて、
if (!w_ignore[i] && i_req[i])
なら、このbitが最初に見つかったrequestになる。
その場合だけgrantを立てる。
同時に、それ以降のbitではrequestを無視したいので、
w_ignore[i+1] = w_ignore[i] | i_req[i];
相当の状態を次へ渡していく。
実装
実際には以下のように書ける。
logic [NUM_REQ:0] w_ignore; always_comb begin w_ignore[0] = 1'b0; o_index = '0; for (int i = 0; i < NUM_REQ; i++) begin if (!w_ignore[i] && i_req[i]) begin w_ignore[i+1] = 1'b1; o_index = i; end else begin w_ignore[i+1] = w_ignore[i]; end end end
この w_ignore は、実質的には下位bitのprefix ORになっている。
例えば、
i_req = 8'b10110100
なら、LSBから見ると、
bit0 = 0 bit1 = 0 bit2 = 1 <- 最初のrequest bit3 = 0 bit4 = 1 ...
となる。
bit2より上では w_ignore=1 になるため、その後にrequestがあってもgrant対象にはならない。
grantの生成
w_ignore[i] は「bit iより下位にrequestが存在するか」を表すので、
assign o_grant = i_req & ~w_ignore[NUM_REQ-1:0];
とできる。
例えばbit2が最初のrequestなら、
i_req = xxxx0100 w_ignore = xxxx0000 // bit2まではlower requestなし
なのでbit2だけが残る。
bit2より上では w_ignore=1 になっているため、上位requestはmaskされる。
o_valid はrequestが1つでも存在すればよいので、
assign o_valid = |i_req;
でよい。
RTL
最終的には以下のようになる。
module priority_encoder #( parameter int NUM_REQ = 8, parameter int IDX_W = $clog2(NUM_REQ) ) ( input logic [NUM_REQ-1:0] i_req, output logic o_valid, output logic [NUM_REQ-1:0] o_grant, output logic [IDX_W-1:0] o_index ); logic [NUM_REQ:0] w_ignore; always_comb begin w_ignore[0] = 1'b0; o_index = '0; for (int i = 0; i < NUM_REQ; i++) begin if (!w_ignore[i] && i_req[i]) begin w_ignore[i+1] = 1'b1; o_index = i[IDX_W-1:0]; end else begin w_ignore[i+1] = w_ignore[i]; end end end assign o_valid = |i_req; assign o_grant = i_req & ~w_ignore[NUM_REQ-1:0]; endmodule
o_index はrequestが存在しない場合には0としている。
したがって o_index の値が有効かどうかは o_valid とセットで見る。
w_ignoreは何を計算しているのか
この回路の本質は w_ignore。
例えば、
i_req = 8'b00101100
とする。
LSB側から見ると、
bit0 : 0 bit1 : 0 bit2 : 1 bit3 : 1 bit4 : 0 bit5 : 1
となる。
w_ignore は、
bit0を見る時点 : 0 bit1を見る時点 : 0 bit2を見る時点 : 0 bit3を見る時点 : 1 bit4を見る時点 : 1 bit5を見る時点 : 1
となる。
つまり、
w_ignore[i] = OR(i_req[i-1:0])
というprefix ORを作っていることになる。
したがって、
i_req[i] & ~w_ignore[i]
となるbitは、「自分自身が1であり、かつ自分より下位には1が存在しないbit」。
これはLSB側の最優先requestそのもの。
bit演算だけでも書ける
LSB側の最初の1bitだけを取り出す処理には、よく知られた式がある。
grant = req & -req;
2の補数を使えば、
grant = req & (~req + 1'b1);
と書ける。
例えば、
req = 8'b10110100
なら、
~req + 1 = 01001100
となり、
10110100
AND 01001100
------------
00000100
でLSB側の最初の1だけが残る。
したがって、grantだけ必要なら、
assign o_grant = i_req & (~i_req + 1'b1);
というかなり短いRTLでも書ける。