Nand2Tetris の ALU の設計が美しくて感動した話

tl;dr

これはなに

この記事はドワンゴ Advent Calendar 2023 の 7 日目の記事です。

Nand2Tetris ってなに

Nand2Tetris は、Nand to Tetris という意味であり、Nand ゲートという非常にシンプルな素子だけ*1を使ってテトリスを組み上げるという、すごいプロジェクトです。英語資料は https://www.nand2tetris.org/ から読むことができ、日本語版はオライリー・ジャパンから「コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方」というタイトルで出版されています。

 

ここでいう Nand ゲートというのは、

  • 0 または 1 が 2 つ入ってくる
  • 入ってきたのが両方 1 なら、0 を出す
  • それ以外が入ってきたら、1 を出す

という振る舞いをする、なんらかの代物です。

 

この「なんらかの代物」が如何なる物理的実体によって実現されているかはどうでもよく、ただ単にその機能を果たしてくれる素子がめちゃめちゃたくさん与えられたときに、そいつらをうまく組み合わせてテトリスを実装しよう（そして、その過程でコンピュータがどんな仕組みで動いているのかの全体像を把握しよう）、というのがこのプロジェクトです。

www.youtube.com

ものすごく壮大に見えると思います。実際、だいぶ壮大です。欲張りとも言えるでしょう。

 

しかし、この本は非常によくできていて、この「Nand からテトリスを作るぞ」というコンセプトの実現のために最低限必要な部分だけを本当に上手く抽出し、短くまとめ上げています*2。

 

実際に紙の本を買うとこのまとめ上げっぷりのすごさが如実に分かります。なんと、厚みにして 2 cm ほどしかありません。ページ数も 400 ページを切っています。

本の側面に、東急ハンズで買った 2cm 角の真鍮のキューブを載せた写真

本の側面に、東急ハンズで買った 2cm 角の真鍮のキューブを載せた写真

この 21 cm × 15 cm × 2 cm、体積にして 630 ml の中に、Nand とテトリスとその間にあるあらゆるものが非常に上手に詰め込まれているのは本当にすごいことです。

 

特にその中でも、第 2 章で登場する ALU（算術論理演算器）が非常に美しく思えたので、それについて書いていこうと思います。

ALU

ALU (Arithmetic Logic Unit) とは、雑に言うと CPU の中で計算を担当してくれるやつのことです。

Nand2Tetris で作られる CPU は 16 ビット CPU なので、入ってきた 16 ビットの値 2 つをもとに計算をして、新たな 16 ビットの値を作るというのが主目的になります。

これは組み合わせ回路として作られます。つまり、内部状態・記憶・フィードバックループといったものを一切持たず、「Nand ゲートを使い倒して、入力として入ってきた 0 や 1 をもとに、新たな 0 や 1 を作っていく」ということだけが許されています。

 

そして、Nand2Tetris においては、この設計が本当に上手い。

書籍の本文にも

最小限の内部パーツだけから構成されてはいるが、それにもかかわらず、非常に多くの機能を持つ。それゆえ、その論理設計は「効率さ」と「簡潔さ」を示す良い手本になるだろう。 ―「コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方」p.34

という、作者本人による自画自賛が書いてあります。実際めちゃめちゃ良い手本だと思います。

Nand2Tetris の ALU 設計

さて、ここからが本題です。

Nand2Tetris の ALU はどんな設計になっているのか。

C 言語で書くと、こんな感じの設計です（フラグについては後述）。

#include <stdint.h>
#include <stdbool.h>
uint16_t ALU(uint16_t x, uint16_t y,
 bool zx, bool nx,
 bool zy, bool ny,
 bool f, bool no) {
    x = zx ? 0 : x;
    x = nx ? ~x : x;
    y = zy ? 0 : y;
    y = ny ? ~y : y;
    uint16_t o = f ? (x+y) : (x&y);
    o = no ? 0 : o;
    return o;
}

つまり、

  • 入力として x や y を使うか、それともそれを無視して代わりに 0 を入れるかを選択するフラグ、zx と zy がある（ステップ 1）
  • ステップ 1 を経由してきた入力を、ビット反転（0→1, 1→0）するかしないかを選択するフラグ、nx と ny がある（ステップ 2）
  • ステップ 2 を通過した 2 つの入力を、「足し合わせる」のか「bit ごとに AND を取る」のかを選択するフラグ、f がある（ステップ 3）
  • ステップ 3 で計算された値を、ビット反転するかしないかを選択するフラグ、no がある（ステップ 4）
  • ステップ 4 で計算された値を出力する

という設計です。

 

この設計の面白さとして、「非常に簡潔でありながら、やたら多くの機能を提供できている」というのがあります。

この zx, zy, nx, ny, f, no の 6 種類のフラグを切り替えるだけで、なんとこの ALU は

  • 何が入ってきても、定数 0, 1, -1, -2 を出力する回路
  • x と y を足し引きする回路
  • x と y に対して bit ごとの OR や AND などを計算できる回路*3
  • x+1, x, x-1, y+1, y, y-1 を計算できる回路
  • -x, -x-1, -x-2, -y, -y-1, -y-2 を計算できる回路
  • x+y+1, x-y-1, -x+y-1, -x-y-1, -x-y-2 を計算できる回路

として振る舞うことができるのです。

 

なお、Nand2Tetris の ALU は、出力値と同時に「その出力値が 0 と等しいかどうか」「その出力値が負の数かどうか」という情報も出力してくれるようになっています。

 

なぜこれで上手くいくのか

こんなにも上手くいく理由は、専門的にいうと「2 の補数表現においては、x をビット反転したものは -x-1 であるから」と言えます。

 

専門的ではない言い方もしておきますか。ということで、その説明のために突然話題を変えることにします。

 

「6832 円の支払いに対して、1 万円札を出した時のお釣りの計算」をパッと暗算できるようになると便利ですね。

それを素早くやるためのテクニックとして、「1 万円から 6832 円を引き算するのではなく、先に 9999 円から 6832 円を引き算して後で 1 円を足す」という手があります。

 

9999 から 6832 を引くのは、繰り下がりが発生しないので、

9-6 → 3

9-8 → 1

9-3 → 6

9-2 → 7

とすればよいですね。

慣れてくると、6832 と見ただけで、それぞれの桁を 3167 と変換できるようになるでしょう。

 

ということで、「足して 9 になるような数」へと各桁を変換して、最後にその結果に 1を足したものが、1 万円を支払ったときのお釣りになります。

 

「先頭に 1 があり、その後ろに 0 が並んだ、キリの良い数」からの引き算をするときには、いつでもこのテクニックが使えます。

 

さて、16 ビット整数を使った 2 進法の計算をするときに、このテクニックを使うことを考えると、「0 → 1、1 → 0」という変換を各桁にかますというのは、この「ピッタリの数から引き算をする操作」のうち、最後に 1 を足す操作をしなかった、というのに相当します。

 

ということで、-x-1 になるんですねぇ。

別れの挨拶

本当はもうちょい説明したいんですが、22:00 に退勤したいので、ここで筆をおくことにします。締切ドリブン執筆。

*1:その手の人のための補足: タイトルに反して、順序回路を作るために DFF もプリミティブな素子として提供されています。キーボードとスクリーンは Memory-mapped I/O になっているものとします

*2:必要最低限以外は本当に華麗に削られていて、たとえばこの本には16進数が一度も登場しません。

*3:XOR と XNOR 以外のあらゆる 2 入力 bit 演算ができます