バレルシフタと段階的な MUX

前提知識：MUX^{iマルチプレクサ 選択信号に従い、複数の入力から一つを出力に接続する組合せ回路です。選択ビットと入力番号の対応を仕様で定めます。 詳しく見る}、論理・算術シフト、組合せ回路の伝搬遅延^{i伝搬遅延 入力が変わってから、出力が正しい値に安定するまでの時間です。論理式の等価性と時間特性は別の性質です。 詳しく見る}を理解していること。

可変シフトを固定配線の選択に変える

一ビットずつ移動するシフトレジスタ^{iレジスタ 複数ビットの状態を記憶する回路です。このコースの同期式レジスタは、クロックエッジで定められた入力を記憶します。 詳しく見る}は、移動回数分のクロックを使います。バレルシフタは移動量を入力とし、一つの組合せ経路で結果を作ります。ビットが時間をかけて何度も動くのではなく、必要な入力位置を出力へ結ぶ配線経路を選びます。

16 ビット値を 0～15 桁移動するなら、移動量は $s=s_0+2s_1+4s_2+8s_3$ です。そこで 1・2・4・8 桁を動かす四段を直列に置き、各段の MUX が「そのまま」と「固定桁数の移動」を選びます。

例えば 11 は二進数 1011 なので 1・2・8 桁段を選び、4 桁段は通過します。$X=0xD2A5$ の論理右シフトでは、0x6952、0x1A54、0x1A54、0x001A が順に得られます。これは四クロックの値ではなく、四つの組合せ段の値です。

各段 16 個の MUX が四組、つまり 64 個の 1 ビット 2:1 選択点です。これは配線・定数伝播の最適化前の構造数です。一般に $W=2^K$ では、選択構造は $W\log_2W$、深さは $\log_2W$ に比例します。各出力へ W:1 MUX を個別に描いても、合成後は木構造になり得るので、RTL の行数で面積や周波数を断定できません。

下では 0xD2A5 を論理右へ 11 桁移します。移動量 1011 の各ビットが選ぶ四つの組合せ段であり、四クロックにわたる実行ではありません。

右シフト回路で左シフトも作る

ビット順を反転した入力を右へ s 桁論理シフトし、結果を再び反転すると左論理シフトです。この対称性で四段を共有できます。ただし入出力の方向選択 MUX が加わるため、総コストは 64 個では終わりません。固定のビット逆順そのものは配線です。

算術右シフトは、空いた上位に元入力の符号ビットを埋めます。左シフトは算術モードでも 0 を埋めます。2 の補数^{i2 の補数 固定幅のビット列で符号付き整数を表す方式です。n ビットの範囲は −2^(n−1) から 2^(n−1)−1 です。 詳しく見る}の算術左シフトと論理左シフトは同じビット移動で、signed オーバーフローを自動検査しません。

移動量の範囲も回路の取り決めです。下の例は 5 ビット shamt で 0～31 を受けます。16 以上なら論理シフトと左シフトは 0、算術右シフトは符号ビット 16 個です。下位四ビットだけ使うと 16 桁を 0 桁と誤解するので、別処理が必要です。

module barrel16 (
  input  wire [15:0] x,
  input  wire [4:0] shamt,
  input  wire left,
  input  wire arithmetic,
  output wire [15:0] y
);
  wire fill;
  wire [15:0] stage [0:4];
  assign fill = (!left) && arithmetic && x[15];

  for (genvar i = 0; i < 16; i++) begin : direction
    assign stage[0][i] = left ? x[15-i] : x[i];
    assign y[i] = shamt[4] ? fill :
                  (left ? stage[4][15-i] : stage[4][i]);
  end

  for (genvar k = 0; k < 4; k++) begin : shift_stage
    localparam int D = 1 << k;
    assign stage[k+1] = shamt[k]
      ? {{D{fill}}, stage[k][15:D]}
      : stage[k];
  end
endmodule

generate の k は回路構成時の定数であり、実行中にループを四回回す装置ではありません。各段の部分選択と繰返し連結の長さが固定なので、四種の固定配線と MUX になります。fill は段ごとに変わらず、複数段を選んでも同じ符号で拡張します。

この RTL は符号埋めを明示し、unsigned^{iunsigned ビット列を非負整数として解釈する規則です。n ビットの範囲は 0 から 2^n−1 で、同じビット列の signed 解釈と異なる場合があります。 詳しく見る} ベクトルにも算術シフトを実装します。演算子で短くする場合、算術右シフトには signed の左オペランドと >>> が必要です。>>> を付けるだけ、または部分選択の元変数だけを signed にするだけで安全とは考えないでください。連結や一部の選択は signed 解釈を失うため、まず意図した幅の signed 値へ変換します。合成対応演算子は AMD の Verilog 式の文書を参照できます。

遅延と情報損失を分けて扱う

四つの組合せ段に、方向・範囲選択と配線の遅延も加わります。タイミング不足なら途中にレジスタを置けますが、残りの移動量・方向制御もデータと同じクロック数だけ遅らせます。すると出力レイテンシ^{iレイテンシ 入力を受け入れてから対応する出力が得られるまでの時間またはサイクル数です。単位時間の処理量を示すスループットとは異なります。 詳しく見る}が変わり、単純な組合せモジュールと同じインターフェースでは扱えません。

シフトで捨てた情報は復元できません。unsigned 左シフトで捨てた上位に一つでも 1 があれば範囲超過です。signed の範囲超過は元の符号と捨てるビットも考慮します。このモジュールはそのフラグを出しません。また負数の算術右シフトは $2^s$ で割った値を下側の整数へ丸めます。したがって $-3$ を一桁ずらすと $-2$ で、0 方向の整数除算の $-1$ とは異なります。