Zenn
Open62

『コンピュータシステムの理論と実装』をやっていく会

mohiramohira

2022/01/03(月)

やったこと

  • まえがき
  • 環境構築

MEMO

  • コンピュータをマジでゼロからつくる！
  • NANDからはじめる
  • テンションが高まる、まえがき
  • 読書会じゃなくて、俺達は、大学に通っている気持ち

次回開催メモ

  • xix 「イントロダクション」から
mohiramohira

2022/01/10(月)

やったこと

  • xix 「イントロダクション」からp.12 HDLでのXOR実装まで

MEMO

  • 本書の全体感とか流れ
  • ブール代数 / ブール式 / ブール関数 / 正準表現
  • NANDがあれば、NANDもできる！
  • 抽象化 / インタフェースと実装
  • Hello HDL!!! たのしい

次回開催メモ

  • p.13 仕様
jnuankjnuank

本書では3つを学ぶ

「コンピュータの動く仕組み」「複雑な問題を扱いやすいモジュールに分
割する方法」そして「ハードウェアとソフトウェアからなる巨大なシステムを開発す
る方法」

mohiramohira

それは、「コンピュータの動く仕組み」「 割する方法」そして「ハードウェアとソフトウェアからなる巨大なシステムを開発す る方法」である。

wkwk

mohiramohira

一方、 コンピュータサイエンスの分野で「抽象化」という言葉が使われる場合は、次のよう に非常に具体的な意味合いで使われる。それは「この要素は何をするのか（what）」 だけを考え、その詳細である「それをどのように行うのか（how）」は無視するという ことである。

ここまで言い換えられるか。確かに。

この機能部分のみを記述するためには、その要素に関係のない情報は含 めずに、それを使うために必要な情報はすべて記載する。つまり、その要素の実装部 分にかかわる情報は、 それを使おうとするユーザーの目に触れてはならない 。なぜな ら、ユーザーにとってそれは意味のない情報だからである。

隠すならちゃんと隠す。隠してこその、抽象化

jnuankjnuank

機械語もまた抽象化されたものであり、物理的には存在しない。

たしかに。

jnuankjnuank

ところで、標準言語ライブラリとは何だろうか？ そして、オペレーティングシステ
ム（ OS ）はどのように動いているのだろうか？ これらの問は 12 章で扱われるテーマ
である。

たしかに。あまり考えたことがなかったな。
12章が楽しみだ。

jnuankjnuank

一般的にコンパイルには、コンパイラ、バーチャルマシン、アセンブラの 3 つの変換器が関連する。

そうなの？　コンパイラだけが全部やってくれるんじゃないのか

jnuankjnuank

コンパイラが、高水準言語のコードから中間コードを生成する。
変換作業は、構文解析とコード生成

jnuankjnuank

ブール関数の表現

  • 真理値表
  • ブール式
    • f (x, y, z) = (x + y) · z̄
  • 正準表現
    • f (x, y, z) = x̄yz̄ + xȳz̄ + xyz̄
mohiramohira

正準表現（canonical representation）
重要な結論を導く。それは、どのようなブール関数であれ、 たとえそれがどれだけ複雑であったとしても、3 つのブール演算 And、Or、Not を用 いて表現できる、ということである。

これが正準表現の威力！

直観的には納得できる話。

mohiramohira

Nand 関数は（Nor 関数も同様に）、理論的に興味深い性質を持っている。それは、 And、Or、Not はそれぞれ Nand（または Nor）だけから作ることができるという点 である。たとえば、x Or y = (x Nand x) Nand (y Nand y) というように、Nand だけから Or を作ることができる。

証明した！

また、正準表現を用いることで、すべてのブール関 数は And、Or、Not の操作によって作ることができた。そのため、すべてのブール関 数は Nand だけから作れることになる。

NAND最強！

mohiramohira

ここで注意すべきは、ゲートのインターフェイスはただひとつしか存在しない、と いうことである。

ここから考えられるのは、

インターフェイスの設計がひどいと、おそらく悪いことになるし、
インターフェイスの設計が良いと、嬉しい。

mohiramohira

ゲートの設計と実装の話は抽象化の説明として良いな〜

mohiramohira
Xor.hdl
/** Exclusive-or gate. out = a xor b */
CHIP Xor {
  // ヘッダーセクション
  IN a, b;
  OUT out;

  // パーツセクション
  PARTS:
  Not(in=a, out=nota);
  Not(in=b, out=notb);
  And(a=a, b=notb, out=w1);
  And(a=nota, b=b, out=w2);
  Or(a=w1, b=w2, out=out);
  // わざと壊す
  // And(a=w1, b=w2, out=out);
}
Xor.tst
load Xor.hdl,
output-file Xor.out,
// compare-to Xor.cmp,
compare-to FailedXor.cmp,
output-list a b out;

set a 0,
set b 0,
eval,
output;

set a 0,
set b 1,
eval,
output;

set a 1,
set b 0,
eval,
output;

set a 1,
set b 1,
eval,
output;
Xor.out
a | b | out
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Xor.cmp
a | b | out
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
FailedXor.cmp
| a | b |out|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |


jnuankjnuank

流れとしては、
ブール関数は、ブール式は正準表現などでAnd、Or、Notで構成することができる。

さらに言うと、And、Or、NotはNANDだけで全て表現ができることを証明したので、
コンピュータの最小構成要素はNAND、という説明だった

mohiramohira

2022/01/17(月)

やったこと

  • p.12 1.1.5 〜 p.22 Xorの実装まで

MEMO

次回開催メモ

  • p.22 マルチプレクサの実装から
mohiramohira

このシミュレータを使い、最終的に は汎用コンピュータを作るまでに至る。

まだ疑っている！

あるいは、「汎用コンピュータ」の定義が実は曖昧が原因。

mohiramohira

NANDもできるNAND

この Nand ゲートから他のすべてのゲートが作成される。

mohiramohira

1 入力の Not ゲートは「インバータ」とも呼ばれる。

「インバータ」って結構聞くよね。

jnuankjnuank

そのため、ここで述べるゲートは基本要素としてみなす必要はない。

Not, And, Or も最小構成要素ではない

mohiramohira

コンピュータのハードウェアは「バス」と呼ばれる複数のビットからなる配列を操 作するように設計されているのが一般的である。たとえば、32 ビットのコンピュータ は 32 ビットのバス 2 本に対して And 関数を行う必要がある。

???

mohiramohira

多ビットマルチプレ草

// 全部a か 全部b にする
if sel=0 {
  for i = 0..15 {
    out[i] = a[i]
  }  
} else {
  for i = 0..15 {
    out[i] = b[i]
  }
}
mohiramohira

・多ビットは、同じバスの他のビットに依存しない。演算が独立しているって感じ

・多入力は、入力すべてに依存するみたいなノリ

mohiramohira


# Python風

def Mux4Way16(
  a[16],b[16],c[16],d[16], # バス幅16ビットで4入力"""
  sel[2] # セレクタは2つ (4 = log2(k) ∴ k = 2)
  ) -> out:
  if (sel[0], sel[1]) == (0, 0): # sel = 00
    for i=0..15:
        out[i] = a[i]
    
  elif (sel[0], sel[1]) == (0, 1): # sel = 01
    for i=0..15:
        out[i] = b[i]

  elif (sel[0], sel[1]) == (1, 0): # sel = 10
    for i=0..15:
        out[i] = c[i]

  elif (sel[0], sel[1]) == (1, 1): # sel = 11
    for i=0..15:
        out[i] = d[i]
jnuankjnuank

多入力多ビットマルチプレクサは、バス幅が変わろうがセレクタの数は特に変わらない。

m 入力 n ビットのマルチプレクサ。k個の制御ビット

k = log 2 m
制御ビット個数 = log2 入力数

※ log2n = 8 　→　n = 3

jnuankjnuank

回路を作る考え方

  • 真理値表を作る
  • 正準表現を作る
  • 回路を作る
  • Nandにすべて変換
  • テスト通す
  • リファクタ
mohiramohira

XORの論理式を導いて、実装して、リファクタリングする流れの図解

正準表現 → 正準表現を回路図に起こす → 実装&テスト → リファクタリング

正準表現って、洗練されているっぽい式だけど、それを愚直にNANDだけで表現すると、無駄が生まれることもあるわけです！

p.22 Xorのリファクタリング: 正準表現を愚直にやったけど、Not(Not(x))があったので、回路を小さくできた · mohira/nand2tetris-shakyo@4a2477d

jnuankjnuank

一括リネーム

 ls -1 hoge* | awk -F"." '{print "mv "$0" fuga."$2}'   
mv hoge.json fuga.json
mv hoge.swp fuga.swp
mv hoge.txt fuga.txt
mohiramohira

Xorのフォルダをベースに、新しいGateのフォルダを作る

cp -a Xor NewGate;  ls -1 Xor* | awk -F"." '{print "mv "$0" NewGate."$2}'    | sh
mohiramohira

2022/01/24(月)

やったこと

  • p.22 マルチプレクサとデマルチプレクサの実装

MEMO

  • HDLのtstファイルの罠！
    • 完全な文字列一致でやるので、半角スペースとかがおかしいとだめ！
    • 左詰めとかに注意！
  • NAND4つでつくるデマルチプレクサをどうやって考えればいいか謎すぎる！ 未解決。

次回開催メモ

  • p.22 多ビット Not/And/Or ゲートから
mohiramohira

compareはマジの文字列単純一致だから、余計なスペースが入っていたりすると、テスト落ちるよ！

jnuankjnuank

ぱっと見わからんけども、代入して展開すると、とりあえず正準表現にはできそう

sel a out 
0   1  1  sel not * a 
0   0  0


sel b out 
1   1  1  sel * b 
1   0  0
mohiramohira

tstファイルは1テストケースに付き1行で書いた方がめっちゃわかりやすい！

Multiplexer.tst
load Multiplexer.hdl,
output-file Multiplexer.out,
compare-to Multiplexer.cmp,
output-list s a b out;

set s 0, set a 0, set b 0, eval, output;
set s 0, set a 0, set b 1, eval, output;
set s 0, set a 1, set b 0, eval, output;
set s 0, set a 1, set b 1, eval, output;
set s 1, set a 0, set b 0, eval, output;
set s 1, set a 0, set b 1, eval, output;
set s 1, set a 1, set b 0, eval, output;
set s 1, set a 1, set b 1, eval, output;
jnuankjnuank

入力3つだと8通りあるんで、ブレース展開で生成

$ echo "set s "{0,1}", set a "{0,1}", set b "{0,1}" eval, output;\n"  
set s 0, set a 0, set b 0 eval, output;
 set s 0, set a 0, set b 1 eval, output;
 set s 0, set a 1, set b 0 eval, output;
 set s 0, set a 1, set b 1 eval, output;
 set s 1, set a 0, set b 0 eval, output;
 set s 1, set a 0, set b 1 eval, output;
 set s 1, set a 1, set b 0 eval, output;
 set s 1, set a 1, set b 1 eval, output;
mohiramohira

2022/02/14(月)

やったこと

  • p.22 多ビット Not/And/Or ゲートから

MEMO

  • とくになし！

次回開催メモ

  • p.29 符号付き2進数
mohiramohira

他入力のAnd、Or、Notを書くのが面倒だったので、Orだけで済ませた！

mohiramohira

Q. 複数入力ゲートの定義が怪しい！

まー、後半で実装するときに(==使うときに)また振り返りましょう！

mohiramohira

2022/02/28(月)

やったこと

  • p.29 符号付き2進数

MEMO

  • 半加算器、全加算器、加算器、インクリメンタ
  • ALU
    • ALUの「効率さ」と「簡潔さ」
    • 6ビットかつ、少ない演算で、多様な関数を表現しているのすごい
      • 「俺なら、18ビットでいっちゃうけどね？」
    • 思いつくのむずくね？

次回開催メモ

  • 加算器の実装から
jnuankjnuank

引き算は足し算として扱えることができる

これ、めっちゃ重要な気がする。

中1でここまでわからんかった…！

mohiramohira

なぜ？

与えられた数字に 1 を加算することができる回路。そのような回路があると便利である。

mohiramohira

なぜ？

制御ビット（control bits） と呼ばれる 6 ビットの入力ビットを用いる。

mohiramohira

真理値表から「きれいな」回路を思いつくのむずくね？

正準表現でゴリ押す意外にどうしたらよいのやら！？

mohiramohira

ALU、実装できる気がしない件

でも、作れたらかっこいいと思う！