社内勉強会で発表した内容のコピペ。
今日のアジェンダ
今年の目標
「骨太なプログラマになる」
我々が日々開発しているアプリケーションは全てコンピュータの上で動いているので、まずは「コンピュータの動く仕組み」を知らなければならないと思った。
コンピュータシステムの理論と実装
一言でいうとコンピュータ作ってみようぜって本です。 本には仕様とヒントしか載ってなくて写経できないのが良いです。
コンピュータを理解するための最善の方法はゼロからコンピュータを作ることです。(裏表紙より)
See. 「コンピュータシステムの理論と実装」をやりきりました - Qiita
実は 1 年半前からずっと積んでました…。 英語版 は無料で読めます。
今日話す部分
本当は最後までやり切ってから発表したかったのですが、2ヶ月前から準備したにも関わらずバーチャルマシンの途中までしか実装が終わらなかったので、今日は1~5章のハードウェアの部分を中心に話します。
理解度2割ぐらいなので、間違ってたらドンドンご指摘ください。
1. ブール論理 〜Boolean Logic〜
- あらゆるデジタル機器は回路からできている
- 回路を論理的に表現するためのブール代数ではブール値(true/false, yes/no, 1/0, on/off などで表せる値、2値ともいう)を扱う
- 物理的にはトランジスタ(スイッチ素子)によって回路のオンオフが切り替えられる
- スイッチング技術によってコンピュータ開発者は物理的な要素に囚われず論理の世界(抽象化された世界)でハードウェアを扱うことができる
- 現在はスイッチングに電気を使うのが一般的だが、磁石、光、バイオ、水圧、空気圧などオンオフが切り替えられるものであればなんでも良い
- HDL(Hardware Description Language)は回路を設計するための言語
- 論理ゲートは論理演算を行う回路のこと、HDL で表現できる
Nand ゲートだけ与えられた状態から、Not, Or, And, Xor, Mux, Dmux などのコンピュータの基礎となる論理ゲートを実装せよ
:github: https://github.com/daido1976/nand2tetris/pull/1
2. ブール算術 〜Boolean Arithmetic〜
- 2進数とは 01 のやつ
- 2進数の加算は最下位ビットから順に足していき、キャリービット(桁上がりビット)と次の桁の和を足す、最後のキャリービットが1であればオーバーフローとして桁が一つ多くなる
- 符号付き2進数は +- を表現するやつ、4ビットなら -8~7 まで表現できる(符号なしの場合は0~15まで)
- 符号付き2進数を表現するためには2の補数を表現するのが一般的
- 正の数の最上位ビットは 0 で負の数の最上位ビットは 1
- x から -x を得るには x のビットを全て反転させその結果にの最下位ビットに1を足せば良い
- ALU は CPU の中心的役割を担う回路で、CPU でおこわなれる算術演算(四則演算)と論理演算は ALU で行われる
1 章で作成した論理ゲートを使って加算器(Adder)、インクリメンタ、ALU(算術論理演算器)を実装せよ(計算をできるようにせよ)
:github: https://github.com/daido1976/nand2tetris/pull/2
ALU マジムズイ :sob:
3. 順序回路 〜Sequential Logic〜
- 1, 2 章で実装した回路は全て 組み合わせ回路 で、入力の組み合わせだけで出力が一意に決まるため計算はできるが状態を保つことができない
- 過去の内部状態と現在の入力とで出力が決まる 順序回路 によって、状態を保持することができる
- 記憶とは時間に依存する行為で、「前 に記憶したものを 今 思い返す」という行為が本質である(なので回路上でも時間の経過を表現しなくてはならない)
- フリップフロップ(data flip-flop, DFF) はクロック入力を絶えず受け取り、一つ前の入力値を出力する
- レジスタ) とはデータを格納、呼び出しする記憶装置(本章だけでなく後ほど出てくるプロセッサ内のレジスタなど、結構いろんな文脈で出てくる)
- メモリは複数のレジスタを積み重ねて実装される、どのレジスタへの読み書きなのかを表現するためにアドレスを用いる
- プログラムカウンタとは次に実行すべき命令が格納されているメモリ上のアドレスを保存しているレジスタ
与えられた DFF と今まで実装した回路を使って、レジスタ、メモリ、プログラムカウンタを実装せよ(状態を保持できるようにせよ)
:github: https://github.com/daido1976/nand2tetris/pull/3
4. 機械語 〜Machine Language〜
- 機械語(バイナリ)は 01 で表現するやつ、機械語を人間にも読みやすくしたのがアセンブリ(アセンブリと機械語は 1 対 1 で対応している)
- コンピュータは機械語しか解釈できない
- 機械語は仕様に決められた形式に従い、プロセッサ(CPU)とレジスタを用いてメモリを操作する
- 一般的にアセンブリは算術演算、論理演算、メモリアクセス、分岐命令用のコマンドを持つ
- ADD とか LOAD とか JNG とか(ここら辺のコマンド名は各コンピュータのアセンブリ言語の仕様に依存する)
- Hack 機械語の仕様について(軽くで良さそう)
アセンブリで乗算(掛け算)プログラムと入出力操作プログラムを作ってみよう(アセンブリと機械語を理解せよ)
:github: https://github.com/daido1976/nand2tetris/pull/4
5. コンピュータアーキテクチャ 〜Computer Architecture〜
- 我々の周りにある機械と比べて、デジタルコンピュータだけが持つ最も際立つ特徴は多様性である(同じハードウェアであっても様々なアプリケーションを起動することができる)
- プログラム内蔵(Stored Program)方式 とはプログラムによる
命令
もデータ
と同じようにメモリに置いて実行するというもの- コンピュータサイエンスにおける最も深遠な発明の一つで、プログラム内蔵方式によりコンピュータは多様性を手に入れた(1930年より前にはハードウェアによる物理的な結線によるロジックの実装も存在していた)
- ここ本文では超熱い文章なんですが、箇条書きにすると魅力が伝わりづらい
- コンピュータのアーキテクチャとして超有名な ノイマン型アーキテクチャ ではプログラム内蔵方式をベースにしている(ていうかノイマン型以外のコンピュータアーキテクチャって何かあるんだろうか :thinking_face_google: )
- ノイマン型アーキテクチャでは CPU を中心としてメモリを操作し、入力デバイス(キーボードなど)からデータを受け取り出力デバイス(スクリーンなど)へデータを送信する
- ノイマン型アーキテクチャのメモリには
データ
と命令
の 2 種類の情報が保存される - CPU の役割は現在読み込まれている
命令
を実行することで ALU、レジスタ、制御ユニットを用いて行う - I/O(入出力)デバイス(キーボードやスクリーンなど)はメモリマップド I/O として扱う
メモリ(スクリーン、キーボード含む全体)、CPU、コンピュータを実装せよ(機械語を理解するコンピュータを構築せよ)
:github: https://github.com/daido1976/nand2tetris/pull/5