【最適化】算術論理演算器(ALU)を最適化してみた(Nand to Tetris part2)

はじめに

こんにちは、enari_Kと申します。普段は東京科学大学(旧東工大)で材料工学を専攻する傍ら、traPというサークルでゲーム制作、競プロ、kaggle、web開発などに取り組んでいます。

今回は、算術論理演算器を最適化してみました。

Nand to Tetrisとは

Nandのみしか使えないという縛りの元で、最小の論理回路の一つであるNandを出発点にCPUを構築し最後テトリスをプレイするところまでもっていくという海外の有名なコースになります。気になる方はこちら。実際にハードを作るところからはじめ、OS、アセンブリ、コンパイルなどを経てゲームを作るところまで学べるので、低レイヤのすべてを学べます。日本語のガイドとしてこちらの書籍があり、大変優れていて、私もとてもお世話になったのでおすすめです。それぞれのセクションについて原理などがしっかり網羅されており、勉強になると思われますので、せひ。

動機

さて、この記事では最適化と銘打っている通り算術論理演算器(ALU)の高速化を目指しています。コンピューターは１動作につき少なくとも１回は計算するはずですので、この算術論理演算器(ALU)の高速化はコンピューターの性能に直接かかわってきます。また、Nandを使う数が増えるのも問題です。Nandを使う数が増えるほど消費電力も増えていきます。ゆえに、この記事では算術論理演算器のNand数最小化と高速化に挑んでいます。

読者への挑戦：ALUの最適化

課題２は課題１で製作したチップを用いて、半加算器・全加算器・加算器そして指定された算術論理演算器(ALU)を製作する課題です。ここからは、課題に取り組む方もいらっしゃると思いますので下に最も最適化した場合Nandいくつで組めるのか、そして組むべき加算器・演算器の入出力表を載せておきます。ぜひ考えてみてください。

半加算器

a	b	carry	sum
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

※加算器の名前の通り、aとbから来た値の和を計算して出力します。2進数で計算し、1の位をsumに桁上がりをcarryとして出力します。

全加算器

a	b	c	carry	sum
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

※加算器の名前の通り、aとbとcから来た値の和を計算して出力します。2進数で計算し、1の位をsumに桁上がりをcarryとして出力します。

16ビット加算器

16ビットの数aと16ビットの数bの和を16ビットで出力する演算器です。17ビット以上の値については無視して出力します。

16ビットインクリメンタ

16ビットの入力された値に1を加えた値を出力する演算器です。17ビット以上の値については無視して出力します。

算術論理演算器(ALU)

zx	nx	zy	ny	f	no	out
1	0	1	0	1	0	0
1	1	1	1	1	1	1
1	1	1	0	1	0	-1
0	0	1	1	0	0	x
1	1	0	0	0	0	y
0	0	1	1	0	1	!x
1	1	0	0	0	1	!y
0	0	1	1	1	1	-x
1	1	0	0	1	1	-y
0	1	1	1	1	1	x+1
1	1	0	1	1	1	y+1
0	0	1	1	1	0	x-1
1	1	0	0	1	0	y-1
0	0	0	0	1	0	x+y
0	1	0	0	1	1	x-y
0	0	0	1	1	1	y-x
0	0	0	0	0	0	x&y
0	1	0	1	0	1	xory

最小化した場合

加算器・演算器	最小Nand数
半加算器	5
全加算器	9
16ビット加算器	140
16ビットインクリメンタ	76
算術論理演算器	479

高速化した場合

加算器・演算器	最小Nand段数
16ビット加算器	22段
16ビットインクリメンタ	4段

※上記で言う段数は、演算器・加算器の中で最も多くNandを通る場所を調べた場合に一番Nandを通るところが何個通っているかを指します。現実の場合、Nandの計算は同時にこなされるはずなので、一番Nandを通ったところが何個Nandを通ったかが高速化に影響します。

ここから解説パートに入ります。自分で実装したい方はいったん読むのを中断することをお勧めします。

解説

図で示す装置は特に言及がなければ、Nandです。

半加算器

• 半加算器

a	b	carry	sum
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

• And

a	b	out
0	0	0
0	1	0
1	0	0
1	1	1

• Xor

a	b	out
0	0	0
0	1	1
1	0	1
1	1	0

見比べてみると、半加算器はcarryにAnd(a,b)をsumにXor(a,b)を出力するだけのものだと気付けると思います。
ここで、XorとAndのNandのみの回路図を見比べてみましょう。

• And
  

• Xor
  

この二つを合成するだけなのですが、見比べてみると、Nand(a,b)の部分が使いまわせることに気付くと思います。この部分を使いまわすことで、半加算器をNand５個で実装することが出来ます。回路図は以下のようになります。

全加算器

半加算器を２つ合わせると、全加算器になるという情報から推察します。半加算器のsumをHsum、carryをHcarryと表記すると、求めるcarryとsumは
※Hsum(X,Y)を2進数におけるXとYの和の一の位、Hcarry(X,Y)を2進数におけるXとYの和の十の位と考えると理解しやすいかもです。

$$carry = Or(Hcarry(a,b),Hcarry(Hsum(a,b),c))$$

$$sum = Hsum(Hsum(a,b),c)$$

となります。ここで、先ほどの班加算器の回路図から

$$Hsum(X,Y) = Nand(Nand(X,Nand(X,Y)),Nand(Nand(X,Y),Y))$$

$$Hcarry(X,Y) = Not Nand(X,Y)$$

また、前回の記事での議論から

$$Or(X,Y) = Nand(Not X, Not Y)$$

より、これらを代入して今回のcarryは

$$carry = Nand(Not Not Nand(a,b),Not Not Nand(Nand(Nand(a,Nand(a,b)),Nand(Nand(a,b),b)),c))$$

よって、Not二重を消去して

$$carry = Nand(\color{red}{Nand(a,b)\color{black}{,\underline{Nand(Nand(Nand(a,\color{red}{Nand(a,b)\color{black}{),Nand(\color{red}{Nand(a,b)}\color{black}{,b)),c))}}}}}}$$

また、今回のsumは上記の議論の内容から代入すると

$$sum = Nand(Nand(Hsum(a,b),Nand(Hsum(a,b),c)),Nand(Nand(Hsum(a,b),c),c))$$

より

$$\text{sum} = \text{Nand} \left( \text{Nand} \left( \color{red}{S_1}, \underline{\text{Nand} ( \color{red}{S_1}, c )} \right), \text{Nand} \left( \underline{\text{Nand} ( \color{red}{S_1}, c )}, c \right) \right)$$

※ $\color{red}{S_1} = \text{Nand} \left( \text{Nand} ( a, \text{Nand}(a, b) ), \text{Nand} ( \text{Nand}(a, b), b ) \right)$

上記の赤い部分さらには点線部分を使いまわして、回路図は以下のようになります。

このようにして、Nand9個で全加算器を作ることが出来ました！

16ビット加算器

Nand数を最小化する実装

今回作った、加算器と半加算器を用います。一桁目は値が繰り上がってこないので、半加算器を用います。2桁目から16桁目は繰り上がりの数(=前の桁を計算した加算器のcarry)と数aと数bを足さなければならないので、加算器を用います。

今回作った加算器はNand9個で、半加算器はNand5個ですので

$$5 + 9 \times 15 = 140$$

よりNand140個で実装することが出来ました！
しかし、この方法だと最もNandを多く通るところで、34回Nandを通る(=(5回)2の位のsum + 2 $\times$ 13回(3~15の位の全加算器carry)+3回(16の位の全加算器sum))ことになり、現実のハードウェアに落とし込んだ場合とても遅いです。ということで、16ビット一回の計算でよりNandを通る数を減らす実装を以下に示します。

より高速化する実装

キャリー先読み(CLA)とは

この16ビット加算器をより高速化するための理論になります。
16ビット加算器についてすべての情報を計算するのに必要な入力は同時に与えられます。つまりすべてのキャリーと各桁の出力は同時に計算を開始できるはずです。よりNandを通る数を少なく実装しようと思ったら、Nandの数を最小化するのではなくNandを贅沢に使ってこの同時計算をよりたくさんこなす実装を考えます。同時計算するうえで障害になるのがこれまでの実装では前の桁が分かるまで確定しなかったcarryです。しかし、このcarryについても計算に必要な値は入力で全部同時に与えられるので、同時に計算を開始できるはずです。これをキャリー先読みといいます。

実装

以下では16ビット加算器でaとbを足す場合について考え、i桁目の値を$a_i$,$b_i$とします。ここで、

$p_i = \text{And}(a_i, b_i)$
$g_i = \text{Xor}(a_i, b_i)$

上記のようにi桁目のXorとAndについて表すこととします。また、以下ではAndを$\land$,Orを$\lor$と表します。

$$c_{i+1} = g_i \lor (p_i \land c_i)$$

$$c_1 = g_0 \lor (p_0 \land c_{in})$$

$$c_2 = g_1 \lor (p_1 \land (g_0 \lor (p_0 \land c_{in})))$$

$$c_2 = g_1 \lor (p_1 \land g_0) \lor (p_1 \land p_0 \land c_{in})$$

$$c_3 = g_2 \lor (p_2 \land g_1) \lor (p_2 \land p_1 \land g_0) \lor (p_2 \land p_1 \land p_0 \land c_{in})$$

３ビットについては上記のように表されます。

$$c_4 = g_3 \lor (p_3 \land g_2) \lor (p_3 \land p_2 \land g_1) \lor (p_3 \land p_2 \land p_1 \land g_0) \lor (p_3 \land p_2 \land p_1 \land p_0 \land c_{in})$$

４ビットについては、上記のように表されます。

$$c_{i+1} = g_i \lor \sum_{j=0}^{i-1} \left( g_j \land \prod_{k=j+1}^{i} p_k \right) \lor \left( c_in \land \prod_{k=0}^{i} p_k \right)$$

これまでの議論から、↑のような式が成り立つと考えられます。

さて、上記式を用いて計算します。

1. $g_i, p_i$ の生成（第1〜3段）式の中の $g_i = And(a_i, b_i)$ と $p_i = Xor(a_i, b_i)$ を作ります。入力が届いてから、まず $p_i$ が確定するまで 3段 消費します。

2.式の中の $\prod p_k$（積）や $\sum (g_j \cdot \prod p_k)$（和）の部分を、まず4ビットの固まりごとに計算します。

4ビット分の $P_{block} = p_0 p_1 p_2 p_3$ を作る（Andツリー）:
4段4ビット分の $G_{block} = g_3 \lor (p_3 g_2) \lor \dots$ を作る（And/Orツリー）: 6段
4ビットの情報をまとめるのに、2入力Nandの組み合わせで 6段 消費します（累計9段）。

3. 先ほど求めた各ブロックの $G_B, P_B$ を用いて、ブロックをまたぐキャリー（$c_4, c_8, c_{12}, c_{16}$）を予測します。これは先ほどの式を「ブロック単位」で適用する工程です。2入力Nandで And/Or ツリーを構成すると、ここでも 6段 かかります。これにより、最上位のキャリー $c_{16}$ が確定するまで、累計 15段 となります。

4. 上位ユニットで決まった $c_4, c_8, c_{12}$ を、各4ビットブロックの中にある各桁へ配り、個別の $c_i$ を確定させます。式の中の $c_{in} \land \prod p_k$ などの項を最終的に計算する段階です。この分配と結合に 4段 消費します。

5. 最後は $sum_i = Xor(p_i, c_i)$ です。Xorゲートの段数である 3段 を加算します。合計: $19 + 3 = \mathbf{22}$ 段

よって、高速化する実装の場合22段になることが示されました。

16ビットインクリメンタ

Nand数を最小化する実装

今回作った半加算器と前回作ったNotを用います。
16ビットインクリメンタは、入力された16ビットの数に対して1加算した値を出力する演算器です。
まず、１の位について考えてみましょう。
１加算された値を返すので、入力の１の位が１なら出力の１の位が０で１繰り上がり、入力の１の位が０なら出力の１の位が１になり繰り上がりはなしになることが分かると思います。
以上を整理すると一の位については入力された数の１の位の数をＸとすると、

• Not(Ｘ)を一の位に出力
• Ｘをcarryとして次の位に渡す
  ということをすることで、Not一つで表すことが出来ます。
  また、それより上の桁についても桁上がりと入力された数しか考えなくていいので半加算器で表すことが出来ます。

以上より、16ビットインクリメンタをNand76個(= 1個(Not) $+$ 5個(半加算器) $\times$ 15)で表すことが出来ました！
しかし、この方法だと最もNandを多く通るところで、31回Nandを通る(=0回(一の位のcarry)+2回 $\times$ 14回(2~15の位の半加算器carry)+3回(16の位の半加算器sum))ことになり、現実のハードウェアに落とし込んだ場合とても遅いです。ということで、16ビット一回の計算でよりNandを通る数を減らす実装を以下に示します。

より高速化する実装

16ビットインクリメンタの場合、16ビット加算器よりもさらに容易にキャリー先読みでの高速化をすることが出来る。なぜなら、もとの数で1桁目から連続して1をとる桁のみが繰り上がり(=carryが1をとる)して、それ以外は繰り上がりをしないからだ。

1. 16桁すべてをAndに適用することで、一桁目からどの桁まで1を連続で取るかが確定する。これらは並列に計算することで、$log_216$すなわち4段のAndで計算することが可能である。Nandのみで回路を構成する場合、Andと同様の効果を得るためには前回の議論からNandが2つ必要であるのでcarryをすべてそろえるために2 $\times$ 4 = 8段使う。

2. すべてのcarryが揃ってから、各桁のsumを出すためには半加算器でのぎろんよりxorを用いる。xorの計算には3段用いるので、ここまでの議論を適切に実装することで、入力から出力が揃うまで累計で11段でできることが示された。

以上より、16ビットインクリメンタを11段で実装できることが示されました！

算術論理演算器(ALU)

ALUの各入力の役割を整理します。

1. zxは1の時、入力xを0に書き換えます。

2. nxは1の時、入力xのビットを反転します。

3. zyは1の時、入力yを0に書き換えます。

4. nyは1の時、入力yのビットを反転します。

5. fは1の時、出力結果をxとyの加算に、0の時出力結果をxとyの各桁についてAndを適応したものにします。

6. noは1の時、出力結果のビットを反転します。

実装

普通に考えると下記のような実装になります。

この実装の場合のNandの使用数は560個(=6 $\times$ 49個(Mux16) + 3 $\times$ 16個(Not16) + 32個(And16) + 140個(Add16) + 1個(Not) + 3個(Or) + 2 $times$ 21個(Or8way))となります。

Add16とAnd16の合体

半加算器と全加算器は以下のような回路図になっています。

上記を注意深く観察すると、Addを計算する過程で2数のAndも出していることが分かると思います。つまり、ここからAnd16の出力をとってくることによってAnd16分の32個のNandを節約することが出来ます。

Mux16→Not16→Mux16の合体

zxについては、このような論理式で表すことが出来ます。

$$And(Not zx,x)$$

これによって、zx = 1なら、強制的に出力は全部0に、zx = 0なら、xの値がそのまま出力することが確認できると思います。また、nxについては上記の式の考えかたを応用すると、このような論理式で表されます。

$$Or(And(x , Not nx), And(Not x ,nx))$$

(さっきのzx = 1なら、強制的に出力は全部0に、zx = 0なら、xの値がそのまま出力する論理式から片方は強制的に全部0になるので、自動的にもう一方が採用される論理式)

上記の式は前回のxorでの議論から

$$Or(And(a, Not(b)), And(Not(a), b)) = Nand(Nand(a, \color{red}{Nand(a, b)} \color{black}{ ),Nand(}\color{red}{Nand(a, b)}\color{black}{ , b))}$$

より、赤文字部分さらにはNot zxを全ビットで使い回すことでx1ビットにつきNand6個で表すことが出来ます。よって、このようなユニットはNand97個で表すことが出来ます。よってこのようなユニット一つにつき、17個Nandを節約でき、上記の回路にはこのMux16→Not16→Mux16が3個あるので合計で51個Nandを節約することが出来ました。

まとめ

ここまでの、議論を適切に実装することによりALUをNand479個($= 560 - 32 - 51$)でALUを製作することが出来ました。

高速化について

実はこれまでの議論でいくつかの部品を統合しましたが、同時に高速化にも成功しています。これとこれまでで議論した全加算器の高速化を組み合わせることで、Nand数を減らしつつ十分に高速なALUを製作することが出来ます。

おわりに

ということで、今回はNand to Tetris第二回としてNand回路一つを用いて可能な限り最小のNand数でさまざまな加算器・演算器を構成し、さらには一部高速化にも挑戦してみました。Nand to Tetrisの第三回ではNand to TetrisのソフトではDFFが作れないということで、これまでやってきたことを全部C#で構築しなおし、メモリやDFFも実装してみるので楽しみにしていてください！

ここまで読んでくれてありがとうございました。