Nand2Tetris読書会（4章）

概要

Nand2Tetris読書会 を開催しています。
今回取り上げるのは、4章『機械語』です。

前の記事は こちら。

内容

コンピュータ言語には2種類ある。

• 機械語(低水準言語): ハードウェアとソフトウェアを繋ぐ。対象とするハードウェア上で直接実行する。ハードウェア全体を制御する。
• 高水準言語: 汎用性・機能性を重視。

機械語は、プロセッサとレジスタを用いてメモリを操作するように設計される。

• メモリ: データや命令を保存するハードウェアデバイスのこと。固定幅のセルが連続して並んでいる。
  • ワード/ロケーション: メモリ内の各セルのこと。
  • アドレス: ワードを指し示すユニークな値。
• プロセッサ(中央演算装置/CPU): 仕様で決められた基本的な命令セットを実行できる。中央演算装置/CPUと呼ばれる。
  • オペレータ(演算子): どのような演算をするかを表す。
  • オペランド(非演算子): 演算の対象となる値。
• レジスタ: ひとつの値だけを保持できる。プロセッサに複数個備えられている。メモリアクセスよりもレジスタアクセスの方が高速。

機械語のプログラムは一連の符号化された命令であり、2つの表記がある。

• バイナリコード(2値コード): コンピュータのビット数に応じた桁数の、0/1の組み合わせで表される命令。
• ニーモニック: 何をするのかが記号や英単語で示された命令。名前から命令の内容を読み取れる。

記号による表記は、プログラムの読み書き両方に用いられる。

• アセンブリ言語/アセンブリ: ニーモニックでプログラムを記述する表記。
• アセンブラ: アセンブリからバイナリ表現(機械語)に変換するプログラム。
  1. テキスト処理のプログラムで、アセンブリを領域単位(ニーモニックとオペランド)へ分解。
  2. 領域ごとに、対応するバイナリ表現に変換。
  3. 変換結果を組み合わせて、機械語の命令コードが完成。

コンピュータごとに、CPUの命令セットやレジスタ、アセンブラの構文ルールは異なっており、いろいろな機械語が存在する。
ただ、機械語の種類が違っても、一般的なコマンドにはある程度共通するものがある。

• 算術演算・論理演算
  例:
  • 加算/減算
  • ビットシフト
  • ビット単位の否定: ビット単位の補数(各ビットを反転)を生成。
• メモリアクセス
  • コマンド:
    • 算術演算や論理演算で、レジスタだけでなく特定のメモリ位置に対しても操作を行う。
    • メモリに対して明示的に読み込み/格納をする。
  • アドレッシングモード: 要求されたメモリのワードに対して、アドレスを指定する方法。
    • 直接アドレッシング: メモリのアドレスを直接指定する。
    • イミディエイトアドレッシング: 命令コード中の値をそのまま読み込む。
    • 間接アドレッシング: アドレスを保持しているメモリ位置が命令によって指定される。ポインタを扱うときに用いられる指定方法。
• 分岐命令: 基本的にプログラムは頭から順に実行されるが、次のコマンドとは別の位置に分岐させる。
  • 反復: ループ処理の開始位置に戻る。
  • 条件分岐: もし条件がfalseならば、if-then節の後にある位置に移動する。
    • 無条件分岐: 常に指定された位置に移動する。
      例: ループ内の処理が終わったら、必ずループ処理の開始位置に戻る。
    • 条件分岐: 与えられたブール条件に合致しない場合だけ指定された位置に移動する。
  • サブルーチン呼び出し:
    あるコードセグメントの最初のコマンドに移動する。関数やメソッドのイメージ。

5章で作成するコンピュータでは、Hack機械語を使用する。
その仕様を見ていく。

Hackコンピュータ: ノイマン型のプラットフォームであり、16ビットのマシンである。以下を備えている。

• CPU
• メモリモジュール: 2つのメモリがあり、いずれも16ビット幅で15ビットのアドレス空間を持つ。
  • 命令メモリ: 読み込み専用。CPUは命令メモリのプログラムだけを実行可能。
  • データメモリ: 読み書き可能。
• メモリパップドI/Oデバイス
  • スクリーン用
  • キーボード用

レジスタには、DとAの2つの16ビットレジスタがある。

• D: データ値だけを保持。
• A: データ値もアドレスも保持。データメモリに直接アクセスするために利用される。

Hack言語は2つの一般的な命令から構成される。

• A命令: Aレジスタに15ビットの値を設定する。
  例: @5 → 5の2進数表記の値をAレジスタに保存
  • 用途:
    • 定数代入
    • メモリ操作: あらかじめAレジスタにメモリのアドレスを設定、指定したメモリ位置のデータをその後のC命令で操作する。
    • 移動命令: あらかじめAレジスタに移動先のメモリアドレスを読み込み、その後の移動をするためのC命令で、次の命令の位置を移動する
• C命令: 以下の3つを組み合わせた命令を「$dest=comp;jump$」という形式で表す。
  • comp: 何を計算するか？
  • dest: 計算した結果をどこに格納するか？
  • jump: 次に何をするか？
    • 次の命令をフェッチして実行する
    • 別の場所にある命令をフェッチして実行する

アセンブラのコマンドは、定数かシンボルでアドレスを参照できる。

• 定義済みシンボル: RAMアドレスの特別なもの。
  • 仮想レジスタ: R0~R15がRAMアドレスの0~15に対応。
  • 定義済みポインタ: SP, LCL, ARG, THISがRAMアドレスの0~4に対応。
  • 入出力ポインタ(I/Oポインタ): SCREENとKBDは、それぞれスクリーンとキーボードのメモリマップ上のベースアドレスに対応。
    • メモリマップ: I/Oデバイスに結びついたメモリ領域にバイナリ値を読み書きして、I/Oデバイスの状態を変更したり取得したりするもの。
• ラベルシンボル: ユーザが定義する。gotoコマンドの行き先を表すシンボルであり、その値はシンボルが定義された場所の次のコマンドのアドレスを表す。
• 変数シンボル:
  ユーザが定義したシンボルの中で、定義済みシンボルでもラベルシンボルでもない場合、変数として扱われる。アセンブラによって一意のメモリアドレスが割り当てられる。

予習メモ

ノイマン型コンピュータ

構成要素として、以下の5つの装置を備える。

• 中央演算装置: 与えられた命令に従って演算をする。
• 中央制御装置: 各装置に命令を出して制御し、プログラム実行を進める。
• 記憶装置: 命令や計算途中の値、外部から入力された値を保持する。
• 入力装置: コンピュータと人間がやり取りをするための外部記憶媒体からのデータを、主記憶装置へ転送する。
• 出力装置: 主記憶装置から外部記憶媒体へデータを転送する。

現在では、以下のようにまとめて呼ぶことが多い。

• CPU(中央演算処理装置)/プロセッサ: 中央演算装置+中央制御装置
• メモリサブシステム: 記憶装置+入力装置+出力装置
  • メモリマップドI/O: コンピュータ内でCPUと入出力装置の間で、入出力を行う方法のひとつ。

ノイマン型コンピュータの計算処理は以下のように進む。

1. 中央制御装置は、主記憶装置との接続箇所を管理している(プログラムカウンタ)。
2. 接続箇所にある記憶装置から1ワードを読み出す。
3. 主記憶装置との接続箇所を次のワードへ移す。
4. 2で読み出したワードを、命令なのか数値なのか、どのような命令なのか解釈して実行する。

ノイマン型コンピュータでは、主記憶装置の大きさに関わらずひとつの接続箇所から順にワードを呼び出す。
したがって、システムが大きくなればなるほど転送には時間がかかる。
このボトルネックを解消するため、並列実行をしたり、CPUと主記憶装置の間にレジスタファイルやキャッシュメモリを備えるなど、工夫がなされている。

ディスカッションメモ

メモリの種類にはどのようなものがある？

メモリは以下のような階層構造になっている。

https://ja.wikipedia.org/wiki/キャッシュ_(コンピュータシステム)#/media/ファイル:Memory_hierarchy.svg

L1キャッシュやL2キャッシュを利用すると、主記憶までデータを取りに行く必要がなくなるので、高速に処理できる。

CPUに複数コアがあると、レジスタは各CPUで独立している？

レジスタは、CPUそのものに内蔵されている記憶装置であるため、CPUに複数コアがある場合はCPUごとに独立したレジスタを持っている。

レジスタが「プロセッサから極めて近い」とはどういうこと？

「物理的に近くにある」ということ。
普通は、CPUの中にレジスタが入っているため、CPUの外にあるメモリにアクセスするよりもレジスタにアクセスする方が速い。

64ビットコンピュータなら命令は64ビットになる？

コンピュータのビット数は、命令のビット数というよりもそのコンピュータのレジスタの大きさのことを示す。
とは言うものの、どうやら命令も64ビットと思われる…？
32ビットコンピュータに比べると、指定できるアドレスの幅が広がるのが大きなメリット。

間接アドレッシングの例で出てくるオペランドの順序の意味は？

STR R2, x だけ 2つ目のオペランド ← 1つ目のオペランド となっているが、他は 1つ目のオペランド ← 2つ目以降のオペランドの演算結果 となっている。
これは、ロード命令 と ストア命令 でオペランドの順序を合わせようとしたためと考えられる。
この考え方では、ロード命令でもストア命令でも1つ目のオペランドがレジスタを示していることが分かる。

Hackプログラムの終わりに無限ループがあるが、プログラム自体は無限に実行され続ける？

ハードウェアの終了は、電源がオフになる(=クロックが終了する)こと。
Hackプログラムとしては、無限ループ=プログラムの終了(待機)である。
プログラムを無限ループにしておくと、何も起こらないことが保証されて、実質プログラムが終了したと言える。

Aレジスタはなぜ2役を担っているの？Dレジスタを2つじゃ駄目？

Aレジスタが2つの役割をこなすと、アドレスを+1していくような処理をするときに楽。
Dレジスタを増やさなかったのは、システム構成を簡略化する(=なるべくCPUを簡単にする)ためである。
Dレジスタを多く持たせると最適化が可能となり、より高速なコンピュータを構成できる。

コンピュータはレジスタとメモリのどちらを使うかをどうやって決めているの？

レジスタとメモリのどちらを使うかという問題は レジスタ割り付け として長く研究されている。
レジスタ割り付けには、ローカルレジスタ割り付けとグローバルレジスタ割り付けがある。

演習メモ

• 最初に書き慣れたプログラミング言語でスクリプトを書くと、アセンブリで処理を実装するときのヒントになった。
  • 処理をどのようにブロック分けするとよいか
  • どのような値を変数として保持しておくとよいか
• ループをするときは、実行回数をカウントアップしていくよりもカウントダウンしていくと、カウントが0に等しくなったらループを終了するという処理になるため、ループの終了条件の判定が簡潔に書ける。
• メモリから読み出した値をうまく活用すると、変数として保持する値の個数を減らせる。

感想

3章までの演習問題では、読書会の参加者の間でそこまでコードに差が出ませんでしたが、この章では演習の解答にかなり個性が出ていました。
可読性・拡張性を重視する人、コードの行数をいかに減らすかにチャレンジする人など、その人のこだわりが見える結果になりました。

最後に

『Nand2Tetris読書会始めました』の記事でも紹介していますが、読み進めているのはこちらの本です。
https://www.oreilly.co.jp/books/9784873117126/

初学者なりに書籍やその他に調べた内容をまとめていますが、理解が足りておらず間違ったことを書いているかもしれません。
そのような箇所を見つけた場合はコメントなどで指摘していただけると助かります。

次の記事は こちら。