見出し画像

From Nand to Tetris:コンピュータシステムの理論と実装

Nand2tetrisと呼ばれている「コンピュータシステムの理論と実装」という書籍があります。

現在使われているノイマン型コンピュータは、論理的にはNAND(Not AND)ゲートだけですべて構成することができるのですが、この本は、NANDゲートからコンピュータのハードウェアを実装して、そのコンピュータ上でソフトウェアのテトリスを動かすまでの、コンピュータシステム全体を通して実装しましょうという教科書です。
実際には動かすのはテトリスではなく、Pongという壁打ちテニスゲームですけど。

内容は全部で12章で構成されていて、各章の課題を順番にこなすことで、論理回路(ブール代数)からCPU、コンピュータシステム、機械語、アセンブラ、バーチャルマシン、コンパイラ、オペレーティングシステムと順番に実装しながら学ぶ(体験する)ことができます。

学習をサポートするソフトウェア群(ハードウェアシミュレータ、CPUエミュレータ、VMエミュレータ、アセンブラ、コンパイラなど)や、課題のテスト環境がとても良くできて、それらを動かしながら課題を解いていくことで、実装できるようになっています。
実装でつまずきそうな場所は、読み返してみるときちんと本の中にヒントが書かれていて、実装しながら読み返すことで、理解が深まるようになっています。特にネットで調べたりすることもなく、本を読み返すことで、ほぼ解決できました。

実習用のソフトウェアは下記のページから入手できます。ソフトウェアはJavaで作られているので、WindowsでもLinuxやMacでも動かすことができます。

自分は昨年の8月下旬に本を購入して、時間のあるときに少しずつ実装して、やっと1月に終わったので、約半年かかってしまいました。

一番時間がかかったのは11章のコンパイラの部分でした。nand2tetrisではJavaを簡略化したようなJackという言語を実装するのですが、Jack言語の仕様を十分に理解しないままコンパイラの実装を始めたので、ずいぶん迷走してしまいました。また、11章のテストではOKだったのに、12章のOSの実装を進めていると、自分のコンパイラがおかしい部分があることが発覚したりもあって、時間がかかりました。

また、12章のOS(オペレーティングシステム)の実装では動くことは動くのですが、自分の実装では画面の表示がとても遅くて、Pongがゲームとして成り立たない状態で、その部分はネットで調べてしまいました。

具体的にはScreen.jackというグラフィックの描画の部分です。
これに関しては書籍にもヒントが書かれていないようなので、もしかすると、同じところで迷う人もいるかもしれないので、対応策を書いておきます。

① (x, y)の画素座標から、メモリアドレスを計算する必要があるのですが、CPUには掛け算、割り算がなく、ソフトウェアで実装していて性能が悪いため、掛け算、割り算を使わないように、下記のようなルックアップテーブルを使って計算する。

let addr = 16384 + (y * 32) + (x / 16);
↓
let addr = x_array[x] + y_array[y];

② 余りの計算も負荷が高い演算なので、16で割った余りの計算(16のモジュロ)を15のandにする。

let shift = x - ((x / 16) * 16);
↓
let shift = x & 15;

③ 16画素長の水平線の描画では、画素単位の描画を16回繰り返すのではなく、メモリに直接1ワード(2バイト)単位で書き込むようにする。

以上の①~③などをすることで、Pongのゲームも成立するような描画速度になりました。

エミュレータで動作中のPong

以上、HDLによるハードウェアの実装からコンパイラやOSの実装までを一気通貫で知ることができ、自分の若い頃にこういった本があったら良かったのにと思いました。

この本は12章で構成されていると書きましたが、実際には13章で構成されています。最後の13章には課題による実習はなく、この本を終えた方々が次に進むステップアップへの提案箇所が書かれています。
本書の実装体験を通して、自分がコンピュータシステムのどの部分をさらに詳しく身に付けたいかが分かり、次のステップに進むための指南書となるかと思いました。

是非、コンピュータ好きな若い人にチャレンジしてもらいたいと思います。書籍の後半のコンパイラの実装などは、自分の好きなソフトウェア言語を使って実装するので、何らかの言語でソフトを作れるスキルが必要(自分はC/C++を使った)ですが、特に難しい数学などがでてくることもないので、高校生などでもチャレンジできるのではないかと思います。





この記事が気に入ったらサポートをしてみませんか?