NANDからCPUを作る（前編）

Androidアプリ開発部の奥澤です。この記事はkubell Advent Calendar 2024（シリーズ1）12月2日の記事です。12月1日は日曜日のためお休みでした。

本日2024年12月2日は、書籍「コンピュータシステムの理論と実装 第2版 モダンなコンピュータの作り方」の発売日です¹。「コンピュータシステムの理論と実装」についてはご存知の方も多いと思いますが、NANDというコンピュータの最もプリミティブな構成要素からスタートし、CPU、仮想マシン、OSを作り上げるというものです。何と、その第2版が本日発売とのことです。

www.oreilly.co.jp

本記事執筆時点では第2版を手に入れることはできませんので、代わりに数年前に購入した初版を本棚から引っ張り出しましてCPUを作るところまでをやってみたいと思います。長くなりそうなので前後編に分け、本記事はその前編です。

本記事において詳細な実装方針まで示してしまうのはこれから本書を読む方の楽しみを奪ってしまうことになるため厳に慎みますが、つまづきやすいポイントについてヒントを出しつつ、味わい深い箇所の感想を書いていこうと思います。

NAND

本書では、最もプリミティブな構成要素をNAND（本書の記述では「Nand」）として、NANDは所与のものとして始めます。NANDとは否定論理積です。すなわち論理積の否定です。それっぽく書くと NOT (A and B) です。うーんちょっと分かりにくいですね...。こんな時は真理値表を書いてみましょう。こんな感じでしょうか。

A	B	A and B	NOT (A and B)
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

これで分かりやすくなりました。日本語で言うと「2つの真理値のどちらかがfalseならtrue」といったところでしょうか。大雑把に言ってしまえば、このNANDなるものを最もプリミティブな構成要素としてCPUを作っていく...ということが本書前半の内容です。このように単純な真理値表を持つNANDを元にしてCPUを作ることができる、ということには驚かされます。同時に、知的な好奇心がムクムクと湧いてきます。どうやってこのNANDからCPUを作ることができるのか...！？

ところで本書においてNANDは所与のものとされます。NANDは既に存在するもの、実装されているものとして扱い、その詳細を読者が知る必要はありません。NANDを実現する物理的な何かがあれば、NANDを組み合わせてCPUを作ることができる、そのような振る舞いは抽象化して考えることができる、というのが本書の主張です。それはそのとおりだとは思うのですが、実際にどう作られているのかは気になるところです。

本書では以下のように記述されています。現代で使用されているNANDでは電気を使うことが普通ですが、電気じゃなくても実現できるという内容です。

スイッチング（切り替え）や伝送を行うことができる技術が電気の他にあれば、それを採用することもできる。実際、過去50年間の間に、ブール関数を実現するために多くの研究がなされており、その中には、磁石、光、バイオ、水圧、空気圧などのメカニズムが使われているものもあった。今日においては、ほとんどのゲートがシリコンから作られたトランジスタにより実現されており、そのようなゲートは回路（またはチップ）としてパッケージされている。

コンピュータシステムの理論と実装（p.5）

ここからは記憶で書きますが、おそらく古典的にはP型半導体とN型半導体を組み合わせることでNANDを実現できたのではないかと思います。P型半導体は電荷のキャリアとしてホールを用いる半導体、N型半導体は電荷のキャリアとして自由電子を用いる半導体です。2024年現在はもっと現代的な手法が使われているような気はします。

とにかく、NANDは利用可能なものとして話を進めます。本書では以降ハードウェア記述言語を用いてハードウェアの実装をしていきますが、NANDについては最初から利用可能な状態となっています。

基本論理ゲート

第一の関門は基本論理ゲートと呼ばれる NOT AND OR XOR の実装です。簡単なブール式ではありますが、改めて NAND から実現しろと言われるとどうしていいかわからなくなります。

まずは NOT を例に取って考えてみましょう。 NOT の真理値表は以下のようになります。ここで、in はゲートへの入力、out はゲートからの出力を表します。入力が 0 なら 1 を出力し、入力が 1 なら 0 を出力します。真理値表としては単純ですが、改めて NOT を NAND で実装するとなると難しいです。

In	Out
0	1
1	0

NAND ゲートの入力と出力に焦点を当てて、真理値表を書いてみます。

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

NOT ゲートは入力が1つのみで、0 か 1 です。それを踏まえて NAND ゲートの真理値表を眺めてみると、a と b の組み合わせが0-0となっている1行目と、1-1となっている4行目が使えそうな気がしてきます。具体的には、NAND ゲートの2つの入力に同一の入力を与えれば良さそうです。これをハードウェア記述言語で書くとこうなります。

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Not.hdl
/**
 * Not gate:
 * if (in) out = 0, else out = 1
 */
CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Nand(a = in, b = in, out = out);
}

ここでハードウェア記述言語の読み方ですが、上記のコードは NOT ゲートの入力 in を NAND の入力 a と b に入力して、 NAND の出力 out （ = の左側の out ）を NOT の出力 out （ = の右側の out ）として出力する、というように読むことができます。

とにかくこれでテストは通ります。AND と OR と XOR も同様に NAND のみから実装できます。

マルチプレクサ、デマルチプレクサ

第二の関門はマルチプレクサとデマルチプレクサです。

マルチプレクサは3つの入力（ a b 、sel ）を受け取り、そのうち1つの入力であるセレクタ（sel）が 0 なら a を、1 なら b を出力します。デマルチプレクサはその逆で、2つの入力（ in、sel ）を受け取り、セレクタ（ sel ）が0なら in を a に、0を b に出力します。また、セレクタ（ sel ）が1なら in を b に、0を a に出力します。

一言で言えば、マルチプレクサは2つの入力値 a と b のどちらかを出力するもの、デマルチプレクサは入力値を a と b のどちらかに出力するゲートです。NAND と、ここまでで実装した AND OR XOR を使って実装できます。

ここではマルチプレクサの実装方法について順を追って考えていきます。真理値表を書いてみます。

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

真理値表を書くと理解しやすくなりました。sel が 0 の時は a を、sel が 1 の時は b を出力するというだけのことです。実装方法を考えていきます。

まずは sel が 1 の時に b を、そうでなければ 0 を出力することを考えます（マルチプレクサを最後まで実装すると、最初にこのような場合を考える意味がわかると思います）。sel が 1 の時、 b が 0 なら 0 を、b が 1 なら 1 を出力する、という実装は AND を使えば実現できそうです。

では、a についてはどうでしょうか？b の場合は sel との AND を取れば良かったんですが、a の場合は単に AND を取っても実装できません。ですが、例えば sel が 0 の時に 1 を、1 の時に 0 を出力するゲートがあればどうでしょうか？このようなゲートは、実は既に実装済みです。

最初、HDLの書き方につまずくかもしれません。あるゲートの出力を別のゲートに出力するためには、以下のように書くことができます（コードは疑似こーどです）。ここでは、OR の出力に o1 という名前をつけて、o1 を AND への入力としています。

    PARTS:
    Or(a = a, b = b, out = o1);
    And(a = o1, b = ..., out = ...);

ここまで実装できれば、得られた2つの出力からマルチプレクサの出力を得るところまでもう一歩です。

デマルチプレクサについても同様に実装します。

多ビットゲート

ここまでは単一のビットを扱うゲートを実装してきました。一方、一般的なコンピュータのハードウェアでは、16ビットや32ビットのビットの配列を操作するように設計されています。ここでは、16ビットのビット配列を操作するゲートを実装します。

ここまでの記事で、ハードウェア記述言語で配列は扱いませんでした。ここからは配列を扱います。16ビットの入力を持つ NOT の入出力は、以下のシグネチャとなっています。

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Not16.hdl
/**
 * 16-bit Not gate:
 * for i = 0, ..., 15:
 * out[i] = Not(a[i])
 */
CHIP Not16 {
    IN in[16];
    OUT out[16];

    PARTS:
    // TODO
}

ここで用いているハードウェア記述言語のインデックスは「0始まり」なので、長さが16の配列にはインデックス 0 〜 15 でアクセスできます。16ビットの NOT では、各インデックスに対して in[i] を反転して out[i] に出力すればいいです。愚直に書けば実装できると思います。

まとめ

ここまでの内容で、1章の一部のみカバーすることができました。前後編で完結するつもりで記事を書き始めましたが、どうもそれは難しそうな予感がしてきました。

本記事ではNANDからCPUを作るという過程の極一部を紹介するに留まりましたが、もしかしたら記事を読んで「コンピュータシステムの理論と実装」の内容に興味を持ってくれた方もいるかもしれません。興味を持った方は、是非「コンピュータシステムの理論と実装」を手に取っていただければと思います。もしそのような方が一人でもいれば、本記事の目標は達成できました。

明日は @awekuit による「パーサーコンビネータを世界一深く理解できるかも知れない解説 - 第1回」です。楽しみですね。

• kubell - Qiita Advent Calendar 2024 - Qiita