NAND2テトリス本「ハードウェア編」まとめ

はじめに

NAND2テトリス本の目的は、コンピュータ・サイエンスの全レイヤー(論理回路からプログラミング言語)を実際に実装してみることを通じて学ぶことである。

https://d33wubrfki0l68.cloudfront.net/178440fefe35208524003ff9cd1c6608bed8b33c/bc0ae/images/1615725469.webp

この本は特に、CS出身ではない社会人プログラマにとっては有用だと思う。おれは電気電子出身でありCS出身ではないため、なんとなくは知っていた(あるいは想像していた)が、はっきりと知っていたわけではない知識もソフトウェアパートにはあった。学科で学んでだろうハードウェアパートでも、多くの知識はすでに吹っ飛んでおり、よい復習となった。ここから言えることは、この本は電気電子学科の学生にとって特にオススメしたいということである。この本によって、自分たちが学んでいることが世の中でどのように役立っているかがわかり、それらの知識が結びつくことでより有機的なものとなる。実際、おれが在学中にこの本があればより勉強が身についただろうと思う。

しかし、すべての実装課題をこなすのはとてもめんどくさい上に、実際には単なる単純作業になりがちである。しかも、コンピュータを作成するまでは付属されたしょうもなHDL(Hardware Description Language)を使わなければならず、はっきり言ってやる気が起きない。

そこでおれは、実装は一切しないことにした。しかし、本を読んではいおしまいでは知識は身につかないことを知っているので簡単なまとめ文書を作ることにした。このまとめは本を読む上でのガイドにもなるだろうし、「そもそも本すら読みたくない」という多忙な人にとっても有益なものになるはずだ。

この本は大きく2つのパートに分けられる。1つはハードウェアパート、もう1つはソフトウェアパートである。ハードウェアパートでは、何らかの機械語によって駆動するコンピュータを作るところまでをやる。ソフトウェアパートでは、プログラミング言語からこの機械語を吐くまでをやる。

この記事を書くにあたって気をつけたことは、要点のみを掴めるように出来るだけ最小限に、コンパクトに書くことである。動的メモリの確保やオブジェクト指向型の構文など、本質的でない拡張については切り捨てた。もし、興味がある人は本を実際に買ってみてほしい。

論理回路

  • どんな真理値表も、ANDとORとNOTだけを使ってブール関数を構築出来る(標準表現)
  • NANDがあればANDとORとNOTが作れる
  • 時間tに依存しない回路を組み合わせ回路という
  • 応用的な回路として、マルチプレクサ、デマルチプレクサなどが存在する

ALU

加算器

  • 2の補数表現を使う。-x = 2^n - xで計算出来る。引き算を足し算で表現出来るため、コンピュータで扱いやすい。足し算した上でオーバーフロービットを無視すれば、引き算の結果が得られる(オーバーフロービットが2^nの部分に相当するため捨てられる)
  • 全加算器があればnビットの加算器が作れる(全加算器をn個並べればよい)
  • 全加算器は半加算器2つを組み合わせることで実装出来る
https://d33wubrfki0l68.cloudfront.net/dfb84190ce0e1e42ca9dc71510d51170e82da96c/88a6b/images/1615725703.webp
https://d33wubrfki0l68.cloudfront.net/b462034b895b0d4760e131e185b8aa76c3789b14/c5b06/images/1615725739.webp

ALU

Hack計算機では、ALUはout = fi(x, y)という関数を表現する。

fiは、AddかAndであり、

  • f(1ならAdd、0ならAnd)、zx(xをゼロにする)、nx(xを反転する)といったフラグによって決定される
  • zx=1,nx=1の時は、ゼロにした上で反転する(つまり-1を表す)
https://d33wubrfki0l68.cloudfront.net/dde5233cd1abf1a5980c0cc883c6e6be1b2a40ed/df7de/images/1615725804.webp
https://d33wubrfki0l68.cloudfront.net/b42d1d7869820a01d14f9f5f8d1b0c5987210397/145d7/images/1615725847.webp

課題ではALUを実装する。選択には、多ビットマルチプレクサを使えばよい。

順序回路

D-FF

  • 記憶素子を作るためには順序回路が必要である
  • ここではD-FFを基本回路として採用する
  • D-FFはout(t) = in(t-1)という式で表される
  • D-FFは、外からクロックが入った(0->1に上がった時に)時に値を入力を取り込む
  • このクロックによって回路上の全D-FFは同期的に値を変更する。これによって、回路上の計算結果がクロックごとに変化する
https://d33wubrfki0l68.cloudfront.net/7072b9291f55810d828e40146bc689e1e2eed6cc/368a2/images/1615725993.webp
https://d33wubrfki0l68.cloudfront.net/8a605b346b28e1f7561b6d305e54d8bd687ec654/3f32a/images/1615726081.webp

レジスタ

D-FFを使って1ビットレジスタ(ビット)を作ることが出来る。

https://d33wubrfki0l68.cloudfront.net/e9e342d8a7b1262731d6722e3f7e118defd64220/bba74/images/1615726120.webp

1ビットレジスタを実装出来るならば、任意ビット幅のレジスタも実装出来る。

メモリ

Hack計算機では、レジスタを並べることによって16ビット幅のメモリを表現する。

メモリを実装する上では指定したアドレスのレジスタを指定することである。このために、3ビットマルチプレクサを使い、メモリを階層的に構築する。トータルで32KBのメモリ空間を持つ。(16K * 2B)

https://d33wubrfki0l68.cloudfront.net/ff753cede62aacf4dd8fef666307f37a0bb5fc8d/0e92d/images/1615726160.webp
https://d33wubrfki0l68.cloudfront.net/147dff3a3a56fb6d7dfd96339448509803033219/4c6f6/images/1615726187.webp

Hack機械語

Hack計算機には、2つのレジスタがある。これらはともに16ビット幅である。

  • Aレジスタはアドレスを指定するために使われる(アドレスは15ビットで表される)。データを保持する場合もある
  • Dレジスタはデータを保持するために使われる

例えば、Dレジスタにメモリの516番地の値を代入したいならば

  1. Aレジスタに516を代入する(@516と書く。@記法)
  2. D=Mを実行

という2ステップを踏む必要がある。

ジャンプ命令も同様に、

  1. Aレジスタに番地を指定
  2. gotoコマンドを実行

という2ステップを踏む。

このように、計算機の実装を簡単にするため、非常にシンプルな機械語を定義している。

例:

https://d33wubrfki0l68.cloudfront.net/76f025723218617a470a4272f5a79aef5cbe15cf/af911/images/1615726269.webp

Hack計算機には2種類の命令がある。 これらは、最上位ビットによって判断出来る。

A命令

A命令は、Aレジスタに値を代入する。

https://d33wubrfki0l68.cloudfront.net/6a002a8913870523dc1b3f06fbe6166096db4eca/d0f4c/images/1615726352.webp

C命令

https://d33wubrfki0l68.cloudfront.net/be116f6ece2ebd0ac8d1e08a6853ce54b664bdef/806e9/images/1615726392.webp

C命令は、

  1. 計算をする
  2. 計算結果をどこかに保存する(保存しない場合もある)
  3. どこかにジャンプする(ジャンプしない場合もある)

という3つのことを順に行う命令である。

一般形としては、dest = comp; jumpと表される。

comp

compは7bit(a,c1-c6)で表される。

これらのビットの組み合わせによって、何を計算するかが変わる。

MはA番地の値を意味する。

https://d33wubrfki0l68.cloudfront.net/555f0ed18c3a312334d2b873c1d3bca34a714b4a/0b1fb/images/1615726440.webp

dest

destはcompによって計算した値をどこに保存するかを決める。d1,d2がA,Dレジスタに保存するか、d3はMに保存するかを決める。

https://d33wubrfki0l68.cloudfront.net/c5481fc680e71c1e7836330e88cdca0066c35ced/0a23b/images/1615726483.webp

jump

jumpは、compによって出力された値について何らかの比較(3ビットで表される)を行い、その結果によってAレジスタに格納されたアドレスにジャンプするという意味である。

https://d33wubrfki0l68.cloudfront.net/a359dd628632f0d32a7cdabcc8a6807217384963/1af12/images/1615726566.webp

Hack計算機の実装

Hack計算機の概観はこのようなものになる。

https://d33wubrfki0l68.cloudfront.net/9b6a088ba17e3b5bff17df67ca226b71d1d17d0f/17b23/images/1615726606.webp

スクリーンやキーボードとのI/OはすべてメモリマップドI/Oによって行われる。

https://d33wubrfki0l68.cloudfront.net/0a44938acc6adf9fa17724e064b75856c49df9bf/d5dc1/images/1615726640.webp

以下はCPUの実装例である。ここで(c)は制御用ビット列を表す。この(c)は命令から抜き出されて、CPU内の様々なところに入力される。

https://d33wubrfki0l68.cloudfront.net/9f761c23662d5b547c8413c1e6a92fefabad64ad/d48e1/images/1615726672.webp
https://d33wubrfki0l68.cloudfront.net/7cd59a5231f5a5e4f37d946c8711cf68512c6c41/4929c/images/1615726706.webp

命令デコーダの実装

命令デコーダをどのように実装するかについては、本に書かれていない。そこでここでは、自分の考察だけを残すことにする。

  • c5をALUのfに入力すればよさそう。同じように、cビットをALUにつなぐだけでよいのでは?他のビットも同じような感じでうまくいくように恣意的に設計されていそう
  • dビットは、Aレジスタ、Dレジスタ、writeMへの(c)に使えばよさそう
  • c命令は、dest = comp; jumpの2段階で実行される。1段階目でALUの出力をとる必要があるので、これをALUの出力(c)にとって、それとjビットによってなんらかの計算を行って、PCのloadとinc(これがたぶんPCの(c)入力に相当する)を計算出来ればよさそう

続編 NAND2テトリス本「ソフトウェア編」まとめ


このエントリーをはてなブックマークに追加

See also