第7回: ALUと演算器の高速化

ALU

[p.76] 加算だけでなく、減算や論理和・論理積などのいろいろな演算を 切り替えて行う回路を算術論理演算ユニット (Arithmetic and Logic Unit; ALU)と呼びます。 
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;

entity alu is
  port (
    a, b: in std_logic_vector(7 downto 0);
    opcode: in std_logic_vector(2 downto 0);
    x: out std_logic_vector(7 downto 0)
  );
end alu;

architecture arch of alu is
begin
  process (a, b, opcode)
    case opcode is
      when I_AND => x <= a and b;
      when I_OR  => x <= a or b;
      when I_NOT => x <= not a;
      when I_XOR => x <= a xor b;
      when I_ADD => x <= a + b;
      when I_SUB => x <= a - b;
      when I_ACC => x <= a;
      when I_DAT => x <= b;
      when others => x <= "XXXXXXXX";
    end case;
  end process;
end arch;

package alu_pack is
constant I_AND: std_logic_vector(2 downto 0) := "000";
...
end alu_pack;
このALUのVHDL記述そのものは、意外と単純で、行う演算を指定する opcodeの値に応じて、出力xを、入力a, bから求める式を case文で切り替えているだけ、です。 (ちにみに後半のpackage以下で、演算の指定に使っている I_ANDなどの定数の値を定義しています。C言語での#defineのようなものと 理解しておいてください)

ここでちょっと面白いのは、その論理合成結果[p.77「論理回路図」]です。 1ビット分のALUは、入力であるa[n], b[n]からいろいろな演算回路を通し、、 そのうちの1つをopcaodeによって、セレクタを使って選ぶ、という 構成になっています。(※セレクタは[p.67]参照) 上から4つの論理演算は、そのまんま、なのですが、 真ん中の加算・減算のところが、ちょっと一工夫があります。 opcode=100のときは、xはa+b(加算)なので、加算器を通した 結果がxに出てきますが、この加算器のcin(下の桁からの桁上げ)は、 下半分の図からわかるように、最下位ビットのALUでは、opcode[0]に なっています。 opcode=100(加算)のときは、opcode[0]=0ですので、 まさに桁上げ伝播加算器(RCA)の構成となります。

ところがoppcode=101(減算)のときは、加算器のb側には b[n]をNOTゲートを通したもの(/b)が与えられています。 またこのときopcode[0]=1ですので、全体としては、 「a + /b + 1」が求められることになります。 ところが、/b + 1 とは、bの「2の補数」ですので、 2進数の数としては、bの符号を反転したもの(-b)と同じ意味となります。 (2の補数については、ここなどを参照) つまり出力xは、「a - b」と同じ意味となり、減算が行われていることに なります。

加算器の高速化

ここではちょっとVHDLから離れて、加算器と乗算器の高速化の手法について みていくことにしましょう。

全加算器と生成項・伝播項

コンピュータは演算を行うもの、で、すべての演算は加算から導かれますから、 加算を行う加算器 (adder)は、まさにコンピュータの基本要素といえます。 そして2進数で数値・データをあらわす現在のコンピュータでは、 2進数の加算を行う加算器が必要なわけですが、 結局1桁分の2進数の加算を行う「1ビット加算器」があれば、 それを組み合わせて何桁の加算、さらにはどんな演算もできますから、 1ビットの加算器こそ、コンピュータの究極の基本要素といえます。

加算対象の2つの1ビットの数An, Bnと、前の桁からの 桁上げ信号Cn-1を加算し、その結果Snと、次の桁への 桁上げ信号Cnを生成するのが、1ビットの加算器である 全加算器 (full adder; FA)でした。 この全加算器の出力であるSn, Cnのうち、Snは

とかけますが、 桁上がりについて、もう少し考えてみると、 桁上がりが発生する(Cn=1となる)場合は、次のいずれかです。 この2つを分けて考えると、次のような論理式を書くことができます。 ところがQn=An + Bnとおくと、 PnとQnの違いはAn=Bn=1のときだけで、Pn=0, Qn=1となりますが、 このときは生成項Gn=1なので、伝播項Qnに関係なく無条件にCn=1となります。 言い換えると、Cnは次のように書いても、結果はまったく同じであるわけです。 これらの式を使って、全加算器をつくることができるわけです。

リプルキャリー加算器

N桁の(2進数の)加算を行う最も簡単な構成は、N個の全加算器をつなぐもので、 リプルキャリー加算器桁上げ伝播加算器(Ripple Carry Adder; RCA)と 呼ばれます。 つまり次の図のように、N個の全加算器をつなぐわけです。

リプルキャリー加算器では、前の桁の桁上げ(キャリー)が 次の桁の入力につながっていますので、最大ですべての桁、つまり 桁数分(=N)のキャリーの伝播が起こることになり、 全体として加算が終了するまでの時間(演算時間)は 桁数Nに比例する、という問題点があります。

桁上げ先見加算器

さきほどの全加算器の論理式は、キャリーが生成する場合(生成項)と 伝播する場合(伝播項)に分けて、次のように書くことができました。 (または Qn = An + Bn とおいて、Cn = Gn + Qn・Cn-1)

たとえば4ビット加算器をつくるとして、 この生成項と伝播項を順番に書くと次のようになります。
G0 = A0・B0P0 = A0B0 C0 = G0 + P0・C-1
G1 = A1・B1P1 = A1B1 C1 = G1 + P1・C0
G2 = A2・B2P2 = A2B2 C2 = G2 + P2・C1
G3 = A3・B3P3 = A3B3 C3 = G3 + P3・C2
このうち、C1は次のように書くことができます。
C1 = G1 + P1・C0 = G1 + P1・(G0 + P0・C-1) = A1・B1 + (A1B1){A0・B0 + (A0B0)・C-1}
つまり、C1が、前の桁からの桁上がりC0を使わずに、 入力An, Bn(とC-1)のみであらわせることになります。 同様に、C2, C3も、入力An, Bnのみであらわすことができます。

ちなみにSn = Pn + Cn-1ですから、 これらを使うと、この4ビット加算器の回路図は次のようになります。

この構成では、RCAのようなキャリーの伝播は起こらず、 すべての桁のキャリーが、入力An, Bnのみから決まるため、 RCAのように桁数に比例した演算時間がかかることはありません。 このような構成の加算器を キャリー先見加算器 (Carry Look-ahead Adder; CLA) と呼びます。 (※上図中のQ0〜Q3はそれぞれP0〜P3の間違いです)

このようにCLAは桁数が多くても高速な演算が可能ですが、 桁数が多くなるほど、キャリーCnを求めるための論理式が 急激に複雑になり、論理回路が大規模になってしまうという問題があります。 (元気がある人は8ビットCLAでも作ってみましょう・・・) 現実的にはCLAの構成は4ビット分にとどめ、それ以上のビット数の 加算器が必要な場合は、4ビットCLAをつなげる、という構成をとるのが 一般的です。

乗算器の高速化

乗算は加算の繰り返しですが、非常によく使う演算なので、 乗算を行う乗算器自体に関しても、いろいろな工夫が知られています。

2進数の乗算

乗算の基本は、やはり筆算です。 例えば4桁の2進数の掛け算「1001×0101」(10進数で、9×5=45)を 次のように求めることができるでしょう。 
    1001  ：被乗数(X)
×) 0101  ：乗数  (Y)
----------
    1001  ：部分積
   0000
  1001
 0000
---------
 0101101 (0x2d = 45(dec))
乗数Yの各桁に対して、被乗数Xを順番にずらして 並べていき、最後にすべてを足すわけですが、 途中の、被乗数Xを順番にずらしていった項を 部分積と呼びます。 部分積を求めるのは簡単で、 被乗数Yの、その桁が1であればXそのもの、 その桁が0であれば0、となります。

並列乗算器

もっとも直感的な乗算器の作り方は、この筆算をそのまま回路にする、 というものです。 つまり部分積xi・yjを求める回路と、 上から下へ部分積を加算していく、という筆算の手順のとおりに並べる、 という方法です。

[p.75]の図は、このような方法による8ビットの乗算器(並列乗算器)の 例です。 結局1桁の2進数の乗算は、AND演算そのものですから、 それぞれの部分積xi・yjをANDゲートで求めつつ、 上から下へ足していく加算を行う回路を並べていけばよいことになります。 このような構成の乗算器を並列乗算回路と呼びます。

並列乗算回路では、部分積の段数、つまり乗数Yの桁数分と ほぼ等しい数だけ加算器が並びますので、 この段数が、全体の演算時間を決めるもっとも大きな要因となります。

ブースのアルゴリズム

乗算器の高速化のためには、部分積の段数を減らすことが効果的ですが、 そのためのうまい方法として、ブースのアルゴリズム (Booth's algorithm) というものが知られています。

詳細は省略しますが、乗数Yに対して、次のようなYjを求めると、 Yのビット数の半分の数のYjを加算するだけで 乗算結果を求めることができる、というものです。 （ただしyjは、乗数Yのjビット目）

つまり、部分積の加算数を半分にできるため、その分、高速化を することができることになります。
配布資料
戻る