ALUにおけるボローフラグを考える

引き算は、足し算で表現される

実は、引き算を行う電子回路というものは存在しません。それでは、どうやって引き算命令を処理しているかというと、よく情報工学の教科書で書かれているように、足し算機能を用いて引き算を行っています。引き算を足し算で表現するには、以下のような式変形を行うとわかりやすくなります。

x - y = x + (-1 - y) + 1

式変形の結果を一見すると、"(-1 - y)"という引き算を行う必要があるように思われます。ですが、この計算には引き算回路は必要ありません。有限ビット数で符号付整数を表現する場合、"-1"は、すべてのビットが"1"になった状態に相当します。例えば、8ビットの符号付整数値の場合には、"11111111"(2進数表現)となります。この数に"1"を足すと"00000000"(ゼロ)になることから、この数が"-1"を表現している事を直感的に理解する事ができると思います。

つまり、"(-1 - y)"を計算するためには、すべてのビットが"1"になった数から"y"を引く、すなわち、"y"のすべてのビットを反転すれば良いということがわかります。

引き算を足し算で表現したALU

引き算が足し算で表現できるという性質を使うと、ALUが簡単に構成できるようになります。足し算と引き算を数式で表現すると、このようになります。

足し算: s = x + y + 0
引き算: s = x + ~y + 1

ここで、記号「~」は、すべてのビットを反転する操作を意味しています。この数式をブロック図で表現すると、このようになります。

引き算回路を導入する代わりに、入力"f"に従って信号を反転する回路が取り入れられました。もちろん、引き算回路よりも反転回路の方が簡単な回路で済みます。

全加算器で足し算器を構成する

上のブロック図で構成したALUには、3入力の足し算回路が使用されていました。3入力といっても、第3の入力は1ビットです。この足し算器は、全加算器という回路で実現できます。

足し算を行う回路を加算器(adder)と言います。1ビットの加算器は、2入力2出力の半加算器(half-adder)と、3入力2出力の全加算器(full-adder)に分類できます。これらの加算器の2出力のうち一方は、そのビットでの和(sum)であり、もう一方は、上位ビットへの繰り上がり(carry)を意味します。

当然のことながら、上位ビットでは、下位ビットで発生した繰り上がりを考慮した足し算を行うため、2項の足し算では、全加算器を使用する必要があります。例えば、8ビットの足し算器は、8個の全加算器をつないで構成します。

この時、最下位ビットの第3の入力をキャリー入力、最上位ビットからの上位ビットへの繰り上がり出力をキャリー出力と呼んでいます。

キャリー入力とボロー入力を考慮したALU

先のブロック図で示したALUでは、下の桁からの「繰り上がり」を示すキャリーと「借り」を示すボローの2つの入力(Cin、 Bin)は、実装されていませんでした。そこで、数式にこれら2つの入力を与えます。まずは、キャリー入力もボロー入力も正論理で考えていきます。

足し算: s = x + y + Cin
引き算: s = x + ~y + 1 - Bin

足し算は、全加算器の機能を使えば計算できます。一方、引き算の場合には、"Bin"という1ビットの項が追加されているので、そのままでは、全加算器で計算することができません。そこで、"+ 1 - Bin"の部分を"+ (1 - Bin)"すなわち、"Bin"の反転に式変形して考えます。

足し算: s = x + y + Cin
引き算: s = x + ~y + ~Bin

これで、ALUを全加算器で表現することができるようになりました。このALUをブロック図で書き表すと、このようになります。

ALUからキャリー出力とボロー出力を取り出す

ALUが出来上がりましたが、まだ機能が不足しています。キャリー出力とボロー出力が実装されていないのです。ここでも、キャリー出力とボロー出力は、正論理で考えます。

足し算の場合、ALUのキャリー出力は、全加算器のキャリー出力そのものです。一方、引き算の場合、ALUのボロー出力は、全加算器のキャリー出力の反転になります。これは、"x = y = Bin = 0"の場合に全加算器のキャリー出力が"1"になることからも類推されます。キャリー出力とボロー出力を含めて考えると、以下の式のようになります。

足し算: { Cout、 s[7:0]} = x[7:0] + y[7:0] + Cin
引き算: {~Bout、 s[7:0]} = x[7:0] + ~y[7:0] + ~Bin

これをブロック図で書き表すと、以下のようになります。

ボローをキャリーフラグで代用したALU

一般的なCPUでは、ボローフラグというものは、存在しません。キャリーフラグがボローの情報を持つように設計されているからです。そこで、このALUでも、"Bin = Cin"、"Bout = Cout"として、ボローをキャリーで表現するようにしてみます。

足し算: { Cout、 s[7:0]} = x[7:0] + y[7:0] + Cin
引き算: {~Cout、 s[7:0]} = x[7:0] + ~y[7:0] + ~Cin

これをブロック図で書き表すと、以下のようになります。

ボローを負論理キャリーで表現する

以上の設計から、「借り」を正論理で表現すると、全加算器のキャリー入力で1回、キャリー出力の部分で1回、論理を反転する必要があることがわかりました。キャリー入出力を反転するかしないかは、足し算命令を実行するか引き算命令を実行するかによって使い分ける必要があります。そのためには、マルチプレクサなどの切り替え機構が必要になってきます。

そこで、論理を反転しなくて済むように、「負論理のボローとしてキャリーフラグを使う」ALUを設計してみます。

足し算: {Cout、s[7:0]} = x[7:0] + y[7:0] + Cin
引き算: {Cout、s[7:0]} = x[7:0] + ~y[7:0] + Cin

これをブロック図で書き表すと、以下のようになります。

このALUの場合に必要なのは、"y"の反転切り替え機構だけです。また、もはや、足し算命令でも、引き算命令でも、キャリー入出力の取り扱いを変更する必要は無く、切り替え機構が不要になりました。このように、ALUを設計するという視点で見た時、ボローは負論理のキャリーで表現した方が自然であり、また、切り替え機構が不要になるなど回路資源の節約にもなります。さらに、切替機構などの回路の段数が減少することによって、上限動作周波数が上がり、高速動作が可能になることも期待できます。

このごろ流行のプロセッサでも

最近、多くのアプリケーションで使われているCPUに、ARMがあります。ARMの引き算命令もボローを負論理のキャリーとして扱っています。ARMのそもそもの設計思想が、小型のCPUを目指していたことを考えると、回路規模を抑えるためにボローをこのように定義したのだろうと納得できます。

昔のCPUでは、6502もボローを負論理のキャリーで表現していました。少しでも回路を簡単に作ろうとした先人の知恵の結晶なのだろうと思うと、感慨深いものがあります。