FPGA開発日記

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

半導体フロントエンド設計100本ノック (9) Parameterized Priority Encoder

半導体フロントエンド設計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でも書ける。