TuringComplete(ゲーム)でわかるCPUが計算する仕組み

読み飛ばしてください

どうも、限界派遣SESです。
ひとりアドカレ14日目です。

今日は、TuringCompleteというゲームを使ってCPUがどのように計算しているのか？ということを説明してみます。

TuringCompleteとは

TuringCompleteは、自分でCPUを作ってプログラムを書くゲームです。

この記事にはゲームのネタバレを含みます。
ネタバレが嫌いな方は、ここで読むのをやめてゲームを購入しましょう。
私は好きなYoutuberがプレイしているのを見てネタバレされるのが嫌だったので、途中で購入しました。

ジャンルとしてはパズルゲームになりますが、CPUの仕組みを理解するのにもってこいだと思います。
なぜなら、最低限のゲートであるNANDゲートを使って他のゲートなどを作っていき、最終的にCPUを作るという流れがとてもわかりやすいからです。

知識がなくても大丈夫

このゲームをプレイした筆者の学力は中卒レベルです。
なので、知識がなくても大丈夫です。

実際にどんな事をしているのか？というと、NANDゲートから始まり、ANDゲート、ORゲート、XORゲート、NOTゲート、フリップフロップ、レジスタ、ALU、RAM、CPUといった流れでCPUを作っていきます。
多いなぁと思うかもしれませんが、これらを一つずつ作っていくので1つ1つのゲートを理解することができます。

NANDがあれば何でもできる

NANDゲートは、他のゲートを作るための最低限のゲートです。
入力が2つあって、どちらも1の時だけ出力が0になります。

入力 1	入力 2	出力
0	0	1
0	1	1
1	0	1
1	1	0

このNANDゲートから他のゲートも作る事ができます。

ちなみに、NANDゲートを作る方法はこのゲームでは解説されていませんが以下の動画が参考になります。

ここでは足し算の計算をするための加算機モジュールを作ることを目標にしていきます。

NOTゲート

実際にゲームの中でNOTゲートを作っていきます。

NANDゲートがありますね。この左側が入力、右側が出力です。
入力が赤の時は0を指していて、緑の時は1を指しています。

一つの入力が 入力1 と 入力2 に繋がっています。

つまり、先程の表の通り、入力1と入力2が1の時だけ出力が0になります。

よって、このNANDゲートはNOTゲートとして使うことができます。

入力	出力
0	1
1	0

ANDゲート

ANDゲートもNANDゲートから作ることができます。

NANDゲートの出力をNOTゲートに繋げることでANDゲートを作ることができます。

入力 1	入力 2	出力
0	0	0
0	1	0
1	0	0
1	1	1

ここで、NOTゲートはNANDゲートから作られていることを考えると、ANDゲートはNANDゲートのみで作ることができるということがわかりますね。

ORゲート

2つの入力値を反転させることでNANDゲートをORゲートに変えることができます。

入力 1	入力 2	出力
0	0	0
0	1	1
1	0	1
1	1	1

XORゲート

XORは、AND、OR、ANDの組み合わせで作ることができます。

入力 1	入力 2	出力
0	0	0
0	1	1
1	0	1
1	1	0

これで、加算機モジュールを作るためのゲートが揃いました。

加算機モジュール

加算機モジュールは、2つの数値を足して出力するモジュールです。

全加算器

1bitの計算をする回路のことを全加算器といいます。
この全加算器は2つの入力と前の桁からの繰り上がりを入力として、和と繰り上がりを出力します。

入力 1	入力 2	前の桁の繰り上がり	和	繰り上がり
0	0	0	0	0
1	0	0	1	0
0	1	0	1	0
0	0	1	1	0
1	1	0	0	1
1	0	1	0	1
0	1	1	0	1
1	1	1	1	1

これで、加算機モジュールが完成しました。
この加算機は主に足し算をするものですが、引き算や掛け算、割り算もすることができるようになります。

8bit加算機

先ほどの加算機は1bitの加算機でしたが、8bitの加算機を作ることもできます。
これにより、0から255までの数値を表現することができます。

加算機の入出力は以下の通りです。

繰り上がり桁を前の加算機から次の加算機に渡すことで、8bitの加算機を作ることができます。

これの8個つなげることにより8bit加算機が完成します。

なお、問題点として繰り上がり桁が出るまで計算結果が出力されないため、計算に時間がかかるという点があります。

これを解決するために桁上げ先取り回路などがありますが、結構複雑な回路になるため以下の記事を参考にしてください。

諸々省略してCPUを見てみる

先ほどの加算機モジュールを作ることができたので、実際に作ったCPUを見てみましょう。
ちなみにめちゃくちゃ回路が汚いのですが、気にしないでください。

右のほうにあるALUというのが実際に計算をする部分です。その中で先程の8bit加算機などを使って計算をしています。
入力値をレジスタに入れて、ALUに入力して計算、結果をレジスタに戻すという流れになります。

実際に計算してみる

63 + 45を計算してみます。
これは以下のコードで表現できます。

右下の赤丸のついたレジスタ3の値が108になっていますね。煩悩の数です。
これがCPUの計算した結果です。

軽く解説すると

名称	意味
reg	レジスター(8bitのメモリ的なもの)
add	足し算命令
数値のみ	即時入力値

ということです。

まず、即時入力値というのはプログラム上の数値を指します。
これはレジスタ0に格納されます。
計算はレジスタ1と2の値を使ってレジスタ3に結果を出力します。
そのため、即時入力値をレジスタ1とレジスタ2に入れてadd命令で計算して結果をレジスタ3に出力しています。

以下のADD命令を見てみると、7bit目が1でALUを使って計算する命令というのがわかり、また3bit目が1の場合ADD命令になることがわかります。

先ほどのコードはこのようにバイナリとして実際にCPUに入力されているということになります。

ですので、以下の通り全ての命令を数値に変換しても計算できます。

これでも計算できていますね。

なんでこれで計算できるの？

私もこのゲームをやるまで不思議でした。だって、NANDゲートしかないのにどうやって計算するの？って感じですよね。
何事もそうですが、実際に起きていることは思った以上にシンプルなことの積み重ねが多いです。

このCPUは上位2bitで命令を表しています。

それぞれの命令は以下の通りです。

bit	命令	意味
00	Immediate	即時入力値をレジスタに格納
01	Compute	ALUを使って計算を行う
10	Copy	特定のアドレスから特定のアドレスに値をコピー
11	Condition	条件式の結果をレジスタに格納

では、なぜbitがそれぞれの命令を表しているかというと。これらは回路の切り替えに使われているからです。

デコーダーという回路を使って、上位2bitの値によって回路を切り替えています。
デコーダーは00などのOPECODEを受け取り、それぞれ1つのみの信号を返します。
00の場合はImmediateの命令の信号を返します。

それぞれの回路は信号を受け取るまで動作しないようになっているため、それぞれの回路は信号を受け取ることで動作を開始します。
この時、同時に下位6bitの値も回路に入力されるため、どのような計算を行うかが決まります。

例えばCompute命令をする場合はALUを使って計算を行うため、ALUの回路に信号を送ります。

このInstructionはCompute命令のADDなどの命令を表します。ここでは3bitの命令を受け取り、ALU内で回路を切り替えて計算を行います。

実際に作ったALUでは以下のような回路です。
デコーダーは下位3bitを受け取り、SWCというゲートを使って計算結果の出力を切り替えています。

このように、CPUは信号を受け取ることで回路を切り替え、計算を行っているということになります。

このCPUの制限

このCPUは即時入力値が63までしか入力できません。
これは上位2bitが命令を表しているためです。
つまりCPU中に書いた命令で定数的な値として利用できる数は0~63の範囲になります。
めちゃくちゃ扱いにくいですよね。

また、計算で利用するレジスタの場所も予め決められた場所を使うため、計算のたびにレジスタの値を移動させる必要があります。

さらに、ALUにはビットシフト命令などが実装されていないため、掛け算命令や割り算命令を実装すると足し算によってそれを表現することになり非常に非効率な計算になります。
例えば、掛け算をする場合は足し算を繰り返すことになります。
2 * 3 = 2 + 2 + 2 = 6という感じです。

このような制限があるため、実際にプログラムを書く際にはかなりの制約があります。

まとめ

回路レベルでの低レイヤーな知識を持っていると、実際にコードがどんな変換をされているのか？など気になることが出来ます。
無知の知というやつですね。知ることが多くなるほど、知らないことが多くなるということです。

次回は、このCPUを使ってBrainf**kインタプリタとコンパイラを作ってみたいと思います。

それでは。