コンピュータシステムの理論と実装―モダンなコンピュータの作り方
原題: 「The Elements of Computing Systems, second edition: Building a Modern Computer from First Principles 」
https://gyazo.com/9680e145bed0f9f88ba522134a7ccc94
目次
code:目次
まえがき
1章 ブール論理
2章 ブール算術
3章 順序回路
4章 機械語
5章 コンピュータアーキテクチャ
6章 アセンブラ
7章 バーチャルマシン#1:スタック操作・8章 バーチャルマシン#2:プログラム制御
9章 高水準言語
10章 コンパイラ#1:構文解析
11章 コンパイラ#2:コード生成
12章 オペレーティングシステム
13章 さらに先へ
付録A ハードウェア記述言語(HDL)
付録B テストスクリプト言語
付録C Nand2tetris Software Suiteの使い方
まえがき・イントロダクション
本書の目的
現代のコンピュータをゼロから作り上げること
優れた開発者はソフトとハードの絡み合った技術を理解している、そのための手段が作ることだと考えているから
https://gyazo.com/8ef47a62533204822280d1e3a953985d
1 - 5章 ハードウェアプラットフォーム
6 - 12章 ソフトウェア階層
1章 ブール論理
半導体によって作られたトランジスタ(スイッチング素子)によって回路を作成する
どんな複合ゲートも基本ゲートから実現可能
ゲートの中身の実装は何通りもあるがインターフェース(他から見えるoutput)は1つしかない
table:ブール式
論理積 (AND) 両者とも真の時のみ真を出力する x ・ y
論理和 (OR) どちらかが真なら真を出力する x + y
否定 (NOT) 与えられた条件の反対を返す x Not y
否定論理積(NAND) 両方とも真でない場合に真を出力する。 Nand
否定論理和(NOR) どちらかが真の場合を除き、真を出力する。 Nor
排他的論理和(EOR, XOR) どちらか一方が真であるときのみ真 Eor
https://gyazo.com/8ca088f945485e088d3f6d024e0ae93c ※グレーが真
Nand回路
https://gyazo.com/38dc05df5fddf3c3f16fc39a641c6a17
HDL(ハードウェア記述言語またはVHDL): ハードウェアの機能を記述するために使われる言語
マルチプレクサ: 複数の入力信号から出力する信号を選択する信号切り替え器
デマルチプレクサ:「複数の入力信号→1つの出力信号」なやつ
マルチプレクサ:「1つの入力信号→複数の出力信号」なやつ
多ビットの論理ゲートも単一ビットと同じ(p.18)
多入力/多ビットマルチプレクサ
$ k = \log_{2}m
https://gyazo.com/414627f7335e54ad51a8d4a5c3190869
1.5章 プロジェクト
$ sh csadelaide-nand2tetris/tools/HardwareSimulator.sh
1. 実行ファイルの選択 https://gyazo.com/661b3955d3f81d739ce82c8811cb7b6f
2. テストファイルの選択 https://gyazo.com/d0b41b97b14e27c8b305f89b13f3b525
3. 実行 https://gyazo.com/277d626f4ddc2a743b098d1a24353cad
Not → ❌答えみた
And → ❌答えみた
Or → ❌答えみた
Xor → ❌答えみた
kinari321.iconむずい...というか考え方がいまいち分からん....
2章 ブール算術
2.2.2
ALU
CPU(中央処理装置)に含まれる演算装置で、CPUの中心をなすデータ処理実行部分のことをいいます。 算術論理演算装置の英語名でArithmetic and Logic Unitの略で、単に演算装置とも呼びます。
四則演算(加算、減算、乗算、除算)を含む算術演算と、論理演算(AND、OR、NOT)を実行する機能を提供する
https://gyazo.com/47199022be05b4c520830f2d4a39b093
code: ALU
入力
x16, y16・・・ふたつの16ビットデータ入力 zx・・・入力xをゼロにする
nx・・・入力xを反転する
zy・・・入力yをゼロにする
ny・・・入力yを反転する
f・・・関数コード:1は「加算」、0は「And演算」に対応する
no・・・出力outを反転する
出力
zr・・・out = 0 の場合にのみTrue
ng・・・out < 0 の場合にのみTrue
関数
if zx then x = 0・・・16ビットの定数ゼロ
if nx then x = !x・・・ビット単位の反転
if zy then y = 0・・・16ビットの定数ゼロ
if ny then y = !y・・・ビット単位の反転
if f then out = x + y・・・2の補数による加算
else out = x & y・・・ビット単位のAnd演算
if no then out = !out・・・ビット単位の反転
if out = 0 then zr = 1 else zr = 0・・・16ビットの等号比較
if out < 0 then ng = 1 else ng = 0・・・16ビットの負判定
2.5章 プロジェクト
HalfAdder.hdl
⭕️正解した!
FullAdder.hdl
❌不正解
Add16.hdl
❌めちゃ惜しい、これが自分の答え
code:Add16.hdl
CHIP Add16 {
PARTS:
HalfAdder(a=a0, b=b0, sum=out0, carry=c0); FullAdder(a=a1, b=b1, c=c0, sum=out1, carry=c1); ⋮
FullAdder(a=a14, b=b14, c=c13, sum=out14, carry=c14); FullAdder(a=a15, b=b15, c=c14, sum=out15, carry=c15); }
Inc16.hdl
なるほど、そう書けるのか
❌自分の答え
code:Inc16.hdl
CHIP Inc16 {
PARTS:
HalfAdder(a=in0, b=false, sum=out0, carry=c0); HalfAdder(a=in1, b=c0, sum=out1, carry=c1); HalfAdder(a=in2, b=c1, sum=out2, carry=c2); ⋮
HalfAdder(a=in15, b=c14, sum=out15, carry=c15); }
ALU.hdl
❌不正解
https://gyazo.com/128f822bfe21a32fe3b2a45c9575452d
3章 順序回路
順序回路
1-2章で取り上げて回路。一つ以上のDFF(Dフリップフロップ)回路が直接または間接的に組み込まれている回路のこと。
状態を保つ(メモリなど)状態を操作する(カウンタなど)が特徴
フリップフロップ(DFF=D型フリップフロップ)
フリップフロップ回路とは、記憶回路と同期回路を搭載したデジタル回路のことです。
そもそもデジタル回路とは オン・オフ(ハイ・ロウ)のレベルの電圧のみを扱う電子回路(論理回路)である
3.5章 プロジェクト
1ビットレジスタ
❌不正解. 惜しいけど答えなるほど
wビットレジスタ
❌不正解. 答えなるほど
8レジスタメモリ
❌不正解. 答えなるほど
address[3]となっているのは2の3乗が8だから
chatgpt.icon 解説
アドレスは3ビットの値で表され、address[3]は3ビットの信号でアドレスを選択するために使用される。
アドレス信号によって、0から7までの8つのアドレスが選択され、それに応じて対応するメモリセルがアクセスされる。
8つのメモリセルに対応する8つのレジスタが存在し、各レジスタはメモリセルへのデータの読み書きを担当する。
DMux8Wayコンポーネントによって、load信号とaddress信号が使用されて、選択されるレジスタが決定される。
各レジスタはRegisterコンポーネントによって実装され、入力データのロードと出力データの提供を行う。
最終的な出力データは、選択されたレジスタから選択され、Mux8Way16コンポーネントによって選択されたデータが提供される。
nレジスタメモリ
❌不正解. むずし
chatgpt.icon 解説
address[0..2]は、メモリセルのアドレスの下位3ビットを表します。この3ビットの組み合わせによって、0から7までの8つのアドレスが選択されます。address[0]は最下位ビット、address[1]はその次のビット、address[2]は最上位ビットを表します。
address[3..5]は、メモリセルのアドレスの上位3ビットを表します。この3ビットの組み合わせによって、0から7までの8つのグループ(セット)が選択されます。つまり、address[3..5]が 000 の場合は0から7の最初のセット、001 の場合は次のセット、以降、111 の場合は最後のセットが選択されます。
RAM64回路は、8つのセットに分割された8つのRAM8コンポーネントから構成されます。それぞれのセットは、RAM8コンポーネントを介してアクセスされます。
DMux8Wayコンポーネントは、load信号とaddress[3..5]信号を使用して、セットの選択を行います。DMux8Wayは8つのセレクトラインを生成し、各セットに対して選択されたセレクト信号を送ります。
各セット内のRAM8コンポーネントは、それぞれのセットのメモリセルに対応しています。RAM8は、入力データ in をロードするかどうか(load信号)、および出力データを提供します。address[0..2]は、セット内のアドレス選択に使用されます。したがって、各セット内のRAM8コンポーネントは、選択されたアドレスに基づいてデータを読み書きします。
最後に、Mux8Way16コンポーネントによって、各セットの出力が選択され、out信号として提供されます。Mux8Way16は、8つの入力(各セットの出力)と3ビットの選択信号(address[3..5])を使用して、出力データを選択します。
カウンタ
❌不正解. むっず
https://gyazo.com/e9baf9126a0a21e7f28d26183ef632c9
4章 機械語
kinari321.icon4.2章からマジでムズカシイ....ネットで見た感じも4章で挫折してる人が多そう
4.4章 プロジェクト
$ sh csadelaide-nand2tetris/tools/CPUEmulator.sh
$ sh csadelaide-nand2tetris/tools/Assembler.sh
Mult.asmの回答の解説
Fill.asmの回答の解説
5章 コンピュータアーキテクチャ
5.5章 プロジェクト
kinari321.iconむずい...
メモリ
❌不正解
CPU
❌不正解
computer
❌不正解
6章 アセンブラ
6.5章 プロジェクト]
7章 バーチャルマシン#1:スタック操作・8章 バーチャルマシン#2:プログラム制御
7.5章 プロジェクト
未実装
本書で実装するVMの仕様は以下の通り。
・スタックベース: すべての命令はスタック上で行われる。
・関数ベース: VMプログラムはプログラムユニット(関数)ごとにまとまっている。
・4つのコマンド
・算術コマンド: スタック上で算術演算と論理演算をする。
・メモリアクセスコマンド: スタックとVM領域の間でデータを転送する。
・プログラムフローコマンド: 条件付き分岐処理あるいは無条件の分岐処理をする。
・関数呼び出しコマンド: 関数を呼び出してそれからのリターンをする。
コンパイラの種類
コンパイラのどの機能に着目するかで、コンパイラを様々に分類できる。
・何に変換するか?
・ネイティブコンパイラ: 機械語(ネイティブコード)に直接コンパイルする。
・中間コードコンパイラ: 中間コードを生成して、別のコンパイラやインタプリタに後続の処理を任せる。
・どこでプログラムを実行するか?
・セルフ開発: 開発環境と同じ環境でプログラムを実行する。
・クロス開発: 開発環境と別の環境でプログラムを実行する。
・何回でコンパイルできるか?
・ワンパスコンパイラ: 1回でコンパイルが完了する。高速にコンパイルできるが、最適化は難しい。
・マルチパスコンパイラ: ソースコードを複数回に分けて読み込んでコンパイルする。
・いつコンパイルするか?
・事前コンパイラ(AOTコンパイラ): プログラムの実行前にコンパイルをする。
・実行時コンパイラ(JITコンパイラ): プログラムの実行時にコンパイルをする。
https://gyazo.com/755b4f0cd5a4c16945af4110e62423ba
9章 高水準言語
10章 コンパイラ#1:構文解析
再帰下降構文解析とは
関数の再帰を使って構文を小さな領域に分割していき、末端から値を確定させていく手法
・下向き構文解析=解析木を根から下向きに作っていく解析方法
・言語の定義がそのままプログラムになるので簡単
・ただし算術式は簡単には解析できない
LL法またはLL構文解析とは
文脈自由文法のサブセットのためのトップダウン構文解析法の一種
入力文字列を左から構文解析していき、左端導出を行う。
LL(1)の1は、1文字だけ先読みすることを表しており、つまり次に読み込むトークンを1つ先読みして、どの生成規則を使えばよいかを決めてから実際に変換していく方法となる。
10.5章 プロジェクトはパス
コードリーディング
11章 コンパイラ#2:コード生成
・JackCompiler: セットアップや他モジュールの呼び出し
入力ファイル Xxx.jack を受け付けて、 出力ファイル Xxx.vm を作成する。
・JackTokenizer: トークナイザ
・SymbolTable: シンボルテーブル
シンボルテーブルの作成
シンボルテーブルの使用
・VMWriter: VMコードを生成して出力
・CompilationEngine: 再帰によるトップダウン式解析器
JackTokenizer から入力を受け取り、VMWriter で出力を書き出す。
code: tree -L 1
jackcompiler/
├── README.md
├── ast
├── compilationengine
├── go.mod
├── jack
├── main.go
├── parser
├── symboltable
├── token
├── tokenizer
├── value
├── vm
└── vmwriter
12章 オペレーティングシステム
オペレーションシステム(OS)の役割:
・コンピュータのハードウェアとソフトウェアシステムのギャップを埋める
・プログラマーやユーザーにとってコンピュータ全体をより扱いやすくする
今回のOSで目指すのは以下の2つ。
・ハードウェアに特化したサービスをカプセル化
→ ソフトウェアから使いやすいサービスに
・高水準言語を、ファンクションと抽象データ型で拡張
13章 さらに先へ
終わり!!
_____________________________________________________
感想
※ 個人の意見です
読むにあたって本当に色々な方のネット記事をとても参考にさせていただいた。ありがとうございます....自分一人だと色々無理だった
⭐結局全てのレイヤー️️でも広義のプログラミング言語が使われているし、効率と人間の使いやすさのトレードオフが働いているし、解析周りはいかに情報を早く分類するかなのかなと思った。
基本的に学ぶことしかなかったので、9・12章以外は読む価値が大いにあるし後半の6章以降ならこの章だけと拾い読みしても問題なさそう
大体100時間くらいかかった
ネット検索しても最低100時間という感じがする
6月からならただただ読み終わるだけでおそらく100時間くらいかかってる。これ課題もやって100時間ちょいで終わらせてる人凄すぎるな....
2023/6/18から読み始めて2023/10/07読み終わったけど、結局いまだRAMとかROMとかってなんだっけ?となる。
100時間使って少しはコンピュータと仲良くなった気がしたが、まだ距離があるそれは実際に作れたという実感と自信がないから️️
あと気のせいかな、低レイヤー系してる人自分のブログ持ってる人おおい
ただとにかく難しかったし結局はよく分からん...となってしまった
読み終わるのに時間かかりすぎて、そもそもの目的だった「職場の優秀な先輩のコンピュータへの解像感に近づく」というきっかけにもなった先輩がもう職場にいないという悲しみ...
あと自分は技術書読み終わるの下手。全部根気丁寧に読みすぎてるから時間かけなくていいところに時間かかってその逆ができていない
後半になっていくにつれてメモ減っているのがモチベをそのまま反映している。
自分のメモ見るくらいだったらこの方を素晴らしいメモ見た方が良さそう
今の状態でCSの学位くれますか?は即答でNOだと思う。試験全落ちしそう。。
_____________________________________________________
用語集
バス
CPUや主記憶装置などの内部装置は、データをやり取りするための伝送路で結ばれています。この伝送路をバスといいます。
バスが一度に送信できるビット数をバス幅といいます。
バス幅が16ビットなら一度に16ビットずつ送ることができる
https://basics.k-labo.work/wordpress/wp-content/uploads/2017/10/19800da5f674d151193f0d3a147332c5.png
データレース
プログラム中に、先行発生の関係によって順序付けられていない二つの競合するアクセスが行われること。プログラムにデータ競合がない場合、プログラムにおけるすべての実行は順序の整合性があることになる。
オートマトン(automaton)
入力に対して内部の状況に応じた処理を行った結果を出力する仮想的な自動機械の概念です。オートマトンのうち、状態の個数と入力の個数が有限個の場合を有限オートマトン(DFA: Deterministic Finite Automaton)と呼ぶ。有限オートマトンを表す方法として、「状態遷移表」と「状態遷移図」が存在する。
「決定性オートマトン」と「「非決定性オートマトン」の違い
決定性オートマトン:次の状態が一意に決定する状態数が有限個のオートマトン
非決定性オートマトン:次の状態が一意に決定しない状態数が有限個のオートマトン