コンピュータシステムの理論と実装(1)

7995 ワード
コンピュータシステムの理論と実装 Nand2Tetris CPU CPU テキストリンク

1章：ブール論理

CPUを光学顕微鏡でみると論理ゲートという回路が見える。
論理ゲートは、ブール関数を実装したもので、基本ゲートから構成される。
ハンダゴテなどを使って実際に回路を繋ぎ合わせて作る前に、
HDL（ハードウエア記述言語）を使って論理ゲートを表現しテストをする。
テストはハードウエアシュミレーターで行う。

ハードウエアシュミレーターをインストールする

まずjavaをインストール

brew install java

Updating Homebrew...
==> Auto-updated Homebrew!
(中略)
==> Summary
🍺  /usr/local/Cellar/openjdk/13.0.2+8_2: 631 files, 314.6MB

インストール成功！！

https://sota0113.hatenablog.com/entry/2019/01/13/153532
これを参考にNand2Tetris.zipをダウンロードして、toolsに移動してHardwareSimulator.shを実行すると始まるらしい

$ cd nand2tetris/
$ ls
projects    tools
$ cd tools
$ ls
Assembler.bat       JackCompiler.bat    VMEmulator.sh
Assembler.sh        JackCompiler.sh     bin
CPUEmulator.bat     OS          builtInChips
CPUEmulator.sh      TextComparer.bat    builtInVMCode
HardwareSimulator.bat   TextComparer.sh
HardwareSimulator.sh    VMEmulator.bat
$ bash HardwareSimulator.sh
No Java runtime present, requesting install.

できないっぽい、、、
JDK・・・Java developing kit
をダウンロードする必要あるらしい
https://www.oracle.com/java/technologies/javase-jdk14-downloads.html
oracleのホームページからmac OS用のをダウンロード

もう一回やったら開いたよ！！！！面白そう
ハードウエア記述言語(略してHDL、ardware discription language)で書いていくよ！！！

$ bash HardwareSimulator.sh


nand2tetris/projects

の中に、コードがたくさん入ってて、これの穴埋めをすればいいようになっている。中身はこんな感じ。

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Xor.hdl

/**
 * Exclusive-or gate:
 * out = not (a == b)
 */

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    // Put your code here:
}

シュミレーターの窓で直接書き込めるのかなと思ったけどできないっぽい、めんどくさいけど、
他のエディタで書いてから実行する感じになるんかな〜そんなことある、、、？？

ブール代数

定義 ： ブール関数とは、0,1を入力値として受け取り、0,1を出力する関数である。

特定の関数のことをいうわけではない。知ってるやつだと、and,or,xorとかは全部ブール関数って感じ。
入力は{0,1}の何個かの積集合の場合もある。andだと 

f : \{0,1\}×\{0,1\} \rightarrow \{0,1\}

ブール関数は必ず「正準表現」で書くことができる、つまり

f(x,y,z)=\bar{x}\bar{y}z + \bar{x}yz

のような変数または変数の否定を結合した形でかける。

試しに知ってるand,or,xorとかを表してみよう！

and(x,y)=xy\\

or(x,y)=x+y\\

xor(x,y)=x\bar{y}+\bar{x}y\\

x,yに0,1とかを色々入れてみるとわかる。
でもちょっと疑問なのは、or(1,1)=2になってしまって定義域外なのでは、、、？？？？
２＝1ってできる根拠ないし、なんなんだろ、、、教えて

変数がn個ある場合、入力例は2^n個あって、そのそれぞれに{0,1}を対応させていくことを考えると、
n個のバイナリ変数によって定義できるブール関数は 2^2^n個あることがわかる。

重要な性質

全てのブール関数はNandだけで実装できる

nand(x,y)=\bar{x}\bar{y}

確かめる。
まず、and,or,notで全てのブール関数は作れる(自明)ので、この３つがNandだけで作れることを証明すれば十分。

ドモルガンの法則を証明で使うのでメモ

\overline{xy}=\overline{x}+\overline{y}\\

[命題]


not(x)=nand(x,x)\\
or(x,y)=nand(nand(x,x),nand(y,y))\\
and(x,y)=not(nand(x,y))=nand(nand(x,y),nand(x,y))\\

[証明]なんか数式左寄せできなくてツッっっっっら。。。。

nand(x,x)=\overline{x}\overline{x}=\overline{x+x}=\overline{x}=not(x)\\
nand(nand(x,x),nand(y,y))=nand(not(x),not(y))=nand(\overline{x},\overline{y})=\overline{\bar{x} 
 \bar{y}}=\overline{\overline{x+y}}=x+y=or(x,y)\\
nand(nand(x,y),nand(x,y))=nand(\overline{xy},\overline{xy})=\overline{\overline{xy}}=xy=and(x,y)

やったー〜。

論理ゲート

n個受け取ってm個返すようなブール写像も、n変数ブール関数でf=(f1,f2,...fm)という風にあらわせ、
そのそれぞれのf(x1,...xn)もf(x1,x2)のような二変数関数で表すことができる
二変数関数（最も単純なゲート）は、スイッチ素子を特定の配線経路の組み合わせで作ることができる。
このスイッチ素子をトランジスタという。

ハードウエア設計者は、基本論理ゲート（基本論理回路）であるand,or,notの三つを使って複合ゲートを設計する。

論理ゲートは、外側からの視点（インターフェイス）と内側からの視点（アーキテクチャ）がある。
必ずしもこれは一対一対応しない。例えば、xorのインターフェイスは一つしかないが、アーキテクチャはたくさん存在する。

ハードウエア設計者は、たくさんのアーキテクチャの中から最適なものを探す。
回路の正確性、処理速度、エネルギー消費量、回路設計のコストなどに注意をはらい、ハードウエアシュミレータで定量化する。コストパフォーマンスが要望を満たすまで実験を繰り返し、満たした段階で初めて設計図が完成。

ハードウエアシュミレーターで色々実装する

上のスクショはAndを実装したときの
左上のFileからLoad ChipでHDLを、Load scriptでtest scriptを開く。
矢印[>]を押すと上から順番にテストしてくれて、
[End of script - Comparison ended successfully]
と出ればテスト成功！！！

HDLの書き方

第1章の課題は、Nand回路を最小構成としてAnd,Not,Or,Xor,マルチプレクサを構成する。
最小回路のNandを利用するには"PARTS:"内に記述する必要がある。

手順としては
(1)図を書く
(2)エディタで書く
(3)シュミレーターで開いてテストする


こんな図を書いてin,outの変数を決めてから書くと書きやすい

[And.hdl]
CHIP And {
    //インターフェイスについて記述
    IN a, b; 
    OUT out;
　　　
    //回路の繋ぎ方の記述
    PARTS:
    Nand(a=a,b=b,out=c);
    Nand(a=c,b=c,out=out);
}
[Or.hdl]
CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a,b=a,out=o1);
    Nand(a=b,b=b,out=o2);
    Nand(a=o1,b=o2,out=out);
}
[Xor.hdl]
CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a,b=a,out=nota);
    Nand(a=b,b=b,out=notb);
    Nand(a=a,b=notb,out=o1);
    Nand(a=nota,b=b,out=o2);
    Nand(a=o1,b=o2,out=w1);
    Nand(a=o2,b=o2,out=w2);
    Nand(a=w1,b=w1,out=o3);
    Nand(a=w2,b=w2,out=o4);
    Nand(a=o3,b=o4,out=out);
}

Not迷ったけど定義するのは入力の変数のみで、Nandにいれる変数はなんでもいいっぽい？

[Not.hdl]
CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Nand(a=in,b=in,out=out);
}

この後他変数、マルチプレクサ、ALUもやっていくっぽい？読み進めたいなー