LoginSignup
3
1

More than 1 year has passed since last update.

@NY0R0N

コンピュータシステムの理論と実装 第1章ゆるーく

Last updated at Posted at 2021-08-01

『コンピュータシステムの理論と実装』という本を買いました。
最近勉強したいと思っていた事と近そうな内容で、レビューも良かったので楽しみ。
プロプラグラマでもなく趣味で書いてるだけの私ですが、備忘録的に各章の回答を載せて行くことにします。

実行環境~
MacBook Air(M1, 2020)
macOS Big Sur 11.5.1
コンピュータシステムの理論と実装　初版第7刷

準備 Hardware Simulatorの実行（超初心者向け)


Simulatorの準備を表示する

本書
C.3　ソフトウェアツールの実行方法
MACユーザー及びUnix/Linuxユーザー
より

注意　以下3つの記述はnand2tetrisをdesktopに置いている人のみ。
違う所に置いた人はcdのところを各々変えてください。
蛇足でしょうが下のコードは1行ずつ入力してね。

ターミナル
cd desktop
cd nand2tetris
cd tools
chmod 777 HardwareSimulator.sh

僕のMacにはjavaが入っておらずこのままでは実行できなかったので下記。
Homebrewが入っていない人は「Homebrew インストール」とかで調べて、
Homebrew入れてから実行してください。

ターミナル
brew install java
sudo ln -sfn $(brew --prefix)/opt/openjdk/libexec/openjdk.jdk /Library/Java/JavaVirtualMachines/openjdk.jdk

パスワードが求められるので入力してEnter。
その後

ターミナル
cd .. 
cd ..
~/Desktop/nand2tetris/tools/HardwareSimulator.sh &

desktopまで戻って本書に書いてある実行用のコマンド入力。

「1.5 プロジェクト」に挑戦


※詳細な画面操作などについて書いてます。忙しい方はこの次のタグの「回答」をご覧ください。
ターミナル
~/Desktop/nand2tetris/tools/HardwareSimulator.sh &

本書に記載の方法でHardware Simulatorを開きました。ここに編集したファイルを入力してテストするんですね。

HardwareSimulator.png

ではNotから実装してみます。~/nand2tetris/projects/01/内のNot.hdlを編集。編集にはSublime Text4を使いました。

ちなみに回路の話は全くの初心者なので、実際にLEDとか使って組んでいる人の記事を色々参考にしました...後は本書の11ページ、XorのHDLプログラムのソースと図を読んでいる内になんとなく分かってきました。int 理解力 =　0。

//Put your code here:はデフォで書かれてます。あえて残しました。
その下が僕が書いたものになります。

Not.hdl
/**
 * Not gate:
 * out = not in
 */

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    // Put your code here:
    Nand(in=a, in=b, out=out);
}

.hdlファイルを編集して保存したら、Hardware Simulatorの左上FileからLoad Chipを選択。Not.hdlを選んでLoad Chip。

select_file.png

chip_load.png

次にLoad Scriptからtstを選択してload。同じ手順です。

test_load.png

多分Simulatorが下のように更新されたはずです。

hardware.png

そうしたらこれ↓を押してテスト開始です。

kore.png

Simulatorの左下にEnd of Script -Compression ended successfullyが
出たら文字通り成功です。

end.png

そうすると、~/nand2tetris/projects/01/内にNot.outというファイルが勝手に出来上がります。みてみましょう。

Not.out
|  in   |  out  |
|   0   |   1   |
|   1   |   0   |

入力が0の時は1を返す、入力が1の時は0を返すの2通りしかないので、成功です！
なお一々.outファイルを見に行くのも面倒なので、Hardware Simulatorの右上のView:からoutputで自分のtest結果を、compareで模範解答を見られます。

View:
menu.png

Output　テスト結果
output.png
result.png

Compare　模範回答

compare.png
result.png

結果と模範回答の出力結果が同じなので、今回書いたNot回路が正解ということがわかります。

男子個人　詳細な操作説明記載　日本代表


回答

Not
入力 in　出力 out 関数 If in=0 then out=1 else out=0
入力と逆の出力をします。
Nandの入出力には4パターンありますが、そのうち「aとbの出力が両方0なら1を返す」、「両方1なら0を返す」という2パターンはNotと同じです。
なのでNandの入力の2つを1つに結べばNot回路になります。(...と、こちらの記事に書いてありました。)

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

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

And
入力 in　出力 out　関数 If a=b=1 then out = 1 else out = 0
Nandの結果を反転させればAndの結果になります。
Nandで2つ入力→出力されたものを(Nandで作った)Notにかける =　And。
Nandだけで表現するのが目標なので2パーツともNandで書いていますが、
分かりやすく書くと下のコメントアウト内のパーツになります。

And.hdl
CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a,b=b,out=Nout);
    Nand(a=Nout,b=Nout,out=out);

/* 
    結局こういうこと
    Nand(a=a,b=b,out=Nout);
    Not(in=Nout,out=out);
*/
}

Or
入力 in 出力 out　関数 If a=b=0 then out = 0 else out = 1
どちらか若しくは両方が1なら1を返します。

Nandは両方１の時のみ0を返します。Nandへの入力をNotで逆にして、
aの逆、bの逆を再度NandにかければOrと同じ結果が得られます。

(0,0) 逆に (1,1) Nand-> (0)
(1,0) 逆に (0,1) Nand-> (1)
(0,1) 逆に (1,0) Nand-> (1)
(1,1) 逆に (0,0) Nand-> (1)
これで0,0の入力時に0出力、他は1を再現できました。

Or.hdl
CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a,b=a,out=Nouta);
    Nand(a=b,b=b,out=Noutb);
    Nand(a=Nouta,b=Noutb,out=out);

    /*
    Not(in=a,out=outa);
    Not(in=b,out=outb);
    Nand(a=outa,b=outb,out=out);
    でも可
    */
}

Xor
入力 in 出力 out　関数 If a ≠ b then out = 1 else out = 0
入力abが異なる場合にだけ1を返します。

入力(0,0)出力(0)
入力(1,0)出力(1)
入力(0,1)出力(1)
入力(1,1)出力(0)

これに関しては本書11ページ、XorのHDLのソースと図を見た方がイメージ湧くと思います...
ただNandだけで実装することが目的なので長いですがコードを書いていきます。

Xor.hdl
CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    // Not
    Nand(a=a,b=a,out=NotOutA);
    Nand(a=b,b=b,out=NotOutB);

    //And
    Nand(a=a,b=NotOutB,out=NandOutA);
    Nand(a=NandOutA,b=NandOutB,out=AndOutA);

    Nand(a=b,b=NotOutA,out=NandOutB);
    Nand(a=NandOutB,b=NandOutB,out=AndOutB);

    //Or
    Nand(a=AndOutA,b=AndOutA,out=OrOutA);
    Nand(a=AndOutB,b=AndOutB,out=OrOutB);
    Nand(a=OrOutA,b=OrOutB,out=out);
}

Multiplexor
aとb2つの入力から、selが0ならaから、selが1ならbを選択して出力するゲートとのこと。
入力 a,b,sel　関数 If sel = 0 then out = a else out = b
要はselが0の時はaだけ見て、selが1の時はbだけ見るので

a b sel out
0 - 0 0
1 - 0 1
- 0 1 0
- 1 1 1

の表のように考えれば良いです。
aを見るときはselをNotで逆にしAndを通し、bを見る時はNotを使わずにAndを通す...すると、

a=0,sel=1 -> And 0　aを見たが0、bは見ていないので結果は0。
a=1,sel=1 -> And 1　aを見ると1、bは見ていないので結果は1。
b=0,sel=1 -> And 0　bを見たが0、aは見ていないので結果は0。
b=1,sel=1 -> And 1　bを見ると1、aは見ていないので結果は1。

とシンプルになります。つまり両方0なら0、片方が0でももう片方が1なら1を返せばOK。
両方1はあり得ません。これはOrを使えば実装することができます。

Mux.hdl
CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
    //aを見る用のNot sel作成
    Nand(a=sel,b=sel,out=NotSel);

    Nand(a=a,b=NotSel,out=AndA);
    Nand(a=AndA,b=AndA,out=NotSelA);

    Nand(a=b,b=sel,out=AndB);
    Nand(a=AndB,b=AndB,out=SelB);
    //Or 
    Nand(a=NotSelA,b=NotSelA,out=outA);
    Nand(a=SelB,b=SelB,out=outB);
    Nand(a=outA,b=outB,out=out);
}

Demultiplexor
Multiplexorの反対。入力 in,sel 出力 a, b
関数 If sel=0 then (a=in,b=0) else (a=0,b=sel)

出力が2つに増えましたが、実装はMultiplexorより簡単です。
inが1でもselが0ならb=0、つまりinもselも両方1の必要があるのでbの出力はAndが必要です。
aですが、selをNotで逆にしないとin=sel=1と確認できません。
実装は下記の通りです。※そろそろ全てNandで書くのに疲れてきました。

DMux.hdl
CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:
    Not(in=sel,out=NotSel);
    And(a=in,b=NotSel,out=a);
    And(a=in,b=sel,out=b);
}

多ビットNot

本当にこんな力技？と思って色々調べたんですが、変数宣言もforも失敗しました。そしてNandじゃなくてNotで書けばよかった..

Not16.hdl
CHIP Not16 {
    IN in[16];
    OUT out[16];

    PARTS:
    Nand(a=in[0],b=in[0],out=out[0]);
    Nand(a=in[1],b=in[1],out=out[1]);
    Nand(a=in[2],b=in[2],out=out[2]);
    Nand(a=in[3],b=in[3],out=out[3]);
    Nand(a=in[4],b=in[4],out=out[4]);
    Nand(a=in[5],b=in[5],out=out[5]);
    Nand(a=in[6],b=in[6],out=out[6]);
    Nand(a=in[7],b=in[7],out=out[7]);
    Nand(a=in[8],b=in[8],out=out[8]);
    Nand(a=in[9],b=in[9],out=out[9]);
    Nand(a=in[10],b=in[10],out=out[10]);
    Nand(a=in[11],b=in[11],out=out[11]);
    Nand(a=in[12],b=in[12],out=out[12]);
    Nand(a=in[13],b=in[13],out=out[13]);
    Nand(a=in[14],b=in[14],out=out[14]);
    Nand(a=in[15],b=in[15],out=out[15]);
}

多ビットAnd
ゴリ押し

And16.hdl
CHIP And16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    And(a=a[0],b=b[0],out=out[0]);
    ・・・略・・・
    And(a=a[15],b=b[15],out=out[15]);

}

多ビットOr
ゴリ押し

Or16.hdl
CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    Or(a=a[0],b=b[0],out=out[0]);
    ・・・略・・・
    Or(a=a[15],b=b[15],out=out[15]);
}

多ビットマルチプレクサ


割愛
Mux16.hdl
CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);

}

多入力Or

Orに7回通せば良いだけなので簡単。

Or8Way.hdl
CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:
    Or(a=in[0],b=in[1],out=out1);
    Or(a=out1,b=in[2],out=out2);
    Or(a=out2,b=in[3],out=out3);
    Or(a=out3,b=in[4],out=out4);
    Or(a=out4,b=in[5],out=out5);
    Or(a=out5,b=in[6],out=out6);
    Or(a=out6,b=in[7],out=out);
}

多入力多ビットマルチプレクサ

Mux4Way16
inとselが倍になった分、2つのMux16に一度通して最後に
もう1度Mux16を通すことで実装。

Mux4Way16.hdl
CHIP Mux4Way16 {
    IN a[16], b[16], c[16], d[16], sel[2];
    OUT out[16];

    PARTS:
    Mux16(a=a, b=b, sel=sel[0], out=outA);
    Mux16(a=c, b=d, sel=sel[0], out=outB);
    Mux16(a=outA, b=outB, sel=sel[1], out=out);
}

Mux8Way16
Mux4からinが倍になっただけなのでMux4を2つ使い、最後にinが2つのMux16に通せば完了。ただsel[0..1]に辿り着くのに時間がかかった。
これ32や64bit用の基本ゲートとかを作ればもっと大きな入出力も簡単に実装できそう。

CHIP Mux8Way16 {
    IN a[16], b[16], c[16], d[16],
       e[16], f[16], g[16], h[16],
       sel[3];
    OUT out[16];

    PARTS:
    Mux4Way16(a=a,b=b,c=c,d=d,sel=sel[0..1],out=outA);
    Mux4Way16(a=e,b=f,c=g,d=h,sel=sel[0..1],out=outB);
    Mux16(a=outA,b=outB,sel=sel[2],out=out);
}

DMux4Way
Mux4wayの要領で実装。同じ様に、

CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:
    DMux(in=in, sel=sel[1], a=outA, b=outB);
    DMux(in=outA, sel=sel[0], a=a, b=b);
    DMux(in=outB, sel=sel[0], a=c, b=d);
}

DMux8Way
も、1度Dmux4Wayを通して、出力が8個になる様にselを変えたDmuxを
4種類実装すれば完了。

DMux8Way.hdl
CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;

    PARTS:
    DMux4Way(in=in, sel=sel[1..2], a=outA, b=outB, c=outC, d=outD);
    DMux(in=outA, sel=sel[0], a=a, b=b);
    DMux(in=outB, sel=sel[0], a=c, b=d);
    DMux(in=outC, sel=sel[0], a=e, b=f);
    DMux(in=outD, sel=sel[0], a=g, b=h);
}

感想戦

準備〜テストで3時間くらい、qiita書くのに何故か2時間くらいかかったので、日曜日の午前中が無くなりました。
NandからNot、And、Orを作った感動は束の間、forが使えないゴリ押しの状況で多ビットが始まり「なんだこれ合ってんのか...」という感じでしたが、
多ビットを使って多in多outが簡単に作れたので達成感がありました。上でも触れましたが、応用すれば32bit、64bitの実装もできるのかな？？？

以上、githubにコード上げれば良いのに丁寧に書きすぎて失踪不可避ですが
『コンピュータシステムの理論と実装』最後まで頑張ります。

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
1