daisuzz.log

"コンピュータシステムの理論と実装 第2章 ブール算術" を読んだ

「コンピュータシステムの理論と実装」を読んだメモを書いていきます。

前回は↓

iikanji.hatenablog.jp

メモ

2進数加算

  • 最下位ビットから加算を行う
  • キャリービットを各桁の和に加算する
  • 最上位ビットの和の結果キャリービットが1の場合オーバーフロー
  • nビットの2進数を加算するハードウェアは3ビット加算器から構築できる

符号付き2進数

  • 2の補数を使う
  • 2の補数=2n-x
  • 正負の加算や減算を、加算器だけで実装できる

加算器 Adder

  • half adder
    • 2つのビットの和を求める回路
    • 入力 a, b
    • 出力 sum, carry
  • full adder
    • 3つのビットの和を求める回路
    • 入力 a, b, c
    • 出力 sum, carry
  • adder
    • 2つのnビットの和を求める回路
    • 入力 a[n], b[n]
    • 出力 out[n]
    • オーバーフローは検知されない
  • incrementer
    • 入力されたビットに1を加算する回路
    • 入力 in[n]
    • 出力 out[16]

算術論理演算器

  • Arithmetic Logical Unit
  • 算術演算と論理演算をまとめたもの
  • 今回の仕様はHackというプラットフォームで使われる専用の回路
  • 入力された6ビットの制御ビットに応じて、入力された16ビットのx,yに対して算術演算または論理演算を行う
  • 出力はout[16], outが0かどうかを表す1ビットzr, outが負の数かどうかを表すng
  • ALUがどのような機能を提供するかはコストとパフォーマンスを考慮して決める
  • ALUに載せればコストはかかるがパフォーマンスはよくなる
  • ALUに載せない場合はOSが機能を提供するためコストはかからないがパフォーマンスは落ちる

実装

Half Adder, Full Adder, Adder, Incrementer, ALUを設計する。 実装は以下。 github.com

途中sub busの記述の仕方に不備があり「Sub bus of an internal node may not be used ~」というエラーメッセージが出た。 SomePart(in=bus[0..7], out=out]);のように入力のときにsubbusを作るのではなくて、以下のように出力のときにsubbusを作るように書くことで解決。

SomePart1(in=foo, out[0..7]=subbus, out=out);
SomePart2(in=subbus, out=out);

参考 http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/Sub-bus-of-an-internal-node-may-not-be-used-td4031198.html

3章は↓

iikanji.hatenablog.jp