Zenn
Open5

「コンピュータシステムの理論と実装」メモ

haseyuyhaseyuy

コンパイラが行う変換作業は、概念的には次の二つのステージからなる

  • 構文解析：ソースコードが解析され、その結果は構文気と呼ばれるデータ構造に格納される
  • コード生成：そのパース木を再帰的に処理し、中間言語で書かれたプログラムを生成する

中間言語とは、高級言語と機械語の間にある言語のこと
中間言語には、スタックベースのVM上で動作する一連の手続きが書かれている
アセンブリコードはアセンブラによってバイナリコードに変換されなければならない

流れとしては、以下
構文木->抽象構文木->高レベル中間言語->低レベル中間言語->ターゲットマシン依存の中間言語->アセンブラ

haseyuyhaseyuy

ブール代数

  • ブール代数はブール値を扱う
  • 通常true/false, 1/0 などのラベルが使われる
  • ブール関数は入力としてブール値を受け取り、出力としてブール値を返す関数である

真理値表(truth table)による表現

  • 関数の入力について、すべての可能な組み合わせを列挙sい、入力の各組み合わせに対する関数の出力をひとつずつ埋めていくこと
  • 変数の数をnとすると、変数の組み合わせは2^n通りある

ブール式

  • 真理値表による指定の他に、ブール関数はブール式によって記述することもできる
  • ブール式の基本はAnd, Or, Notの3つである

正準表現(canonical representation)

  • どのようなブール関数でも、少なくとも一つの正準表現と呼ばれるブール式で表すことができる
  • 真理値表から正準表現を導くには、真理値表で関数の出力が1である行だけに注目し、そのような各行について、
    その行に入力されるリテラルをAnd(+)で結合して新たな項を作成する
  • どのようなブール関数であれ、3つのブール演算And, Or, Notを用いて表現できる

Nand関数

  • And, Or, NotはそれぞれNand(またはNor)だけから作ることができる
  • 例： x Or y = (x Nand x) Nand (y Nand y)というように、NandだけからOrを作ることができる

基本ゲートと複合ゲート

  • 論理ゲートの入力と出力はすべて0と1からなる要素であるため、それらを互いに組み合わせて複合ゲートを構成することができる

例：3入力のブール関数であるAnd(a, b, c)の実装

ブール代数を用いると 以下のように記載でき、

a・b・c = (a・b)・c

前置表記法の場合、以下の記載となる
And(a, b, c) = And(And(a, b), c)

haseyuyhaseyuy

ハードウェア記述言語

  • コンピュータ上でハードウェア記述言語を用いて、回路のアーキテクチャを設計し、最適化を考えることができる
  • ハードウェアシミュレータはHDLで書かれたプログラムを入力として読み込み、メモリ上にそのプログラムで指定された回路を構成する
  • 仮想回路へのさまざまな入力に対して回路の出力をシミュレートし、出力を期待される結果を比較する

Nandゲート

  • Nandゲートから他のすべてのゲートと回路が作られる
a b Nand(a, b)
0 0 1
0 1 1
1 0 1
1 1 0
Nand
/**
 * Nand gate: out = a Nand b.
 */
// CHIP宣言：「CHIP」といキーワードの次に回路の名前が続く
CHIP Nand {
　// 「IN」というキーワードの次に、入力ピンの名前のリストが続く
    IN  a, b;
　// 「OUT」というキーワードの次に、出力ピンの名前のリストが続く
    OUT out;

    BUILTIN Nand;
}

Notゲート

a Not(a)
0 0
0 1
1 0
1 1
Not
/**
 * Not gate:
 * out = not in
 */

CHIP Not {
    IN in;
    OUT out;

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

Andゲート

a b And(a, b)
0 0 0
0 1 0
1 0 0
1 1 1
And
/**
 * And gate:
 * out = not in
 */

CHIP And {
    IN a, b;
    OUT out;

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

Orゲート

  • Or関数は少なくとも入力のひとつが1のとき1を返し、それ以外は0を
a b Or(a, b)
0 0 0
0 1 1
1 0 1
1 1 0
haseyuyhaseyuy

真理値表→論理式の導出

真理値表

A B C Z
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

主加法標準形

  • 最小項(どれか一つの組み合わせのみ1となる関数で、A, B, Cの文字をそれぞれ一回ずつ含む論理積)の論理和である
  • 上記の真理値表に対する主加法標準形は
Z = ¬A∧B∧C+A∧¬B∧C+A∧B∧¬C+A∧B∧C

主乗法標準形

  • 最大項(どれか一つの組み合わせのみ0となる関数で、A, B, Cの文字をそれぞれ一回ずつ含む論理和)の論理積である
  • 上記の真理値表に対する主加法標準形は
Z = (A∨B∨C)∧(A∨B∨¬C)∧(A∨¬B∨C)∧(¬A∨B∨C)
haseyuyhaseyuy

マルチプレクサ

  • 選択制御入力に従い、複数の入力信号のうちからひとつを選び、出力信号とする回路

真理値表

a b sel z
0 0 0 0
0 1 0 0
1 0 0 1
1 1 0 1
0 0 1 0
0 1 1 1
1 0 1 0
1 1 1 1
sel b
0 a
1 b

デマルチプレクサ

  • 選択制御入力に従い、複数の入力信号のうちからひとつを選び、出力信号とする回路
sel a b
0 in 0
1 0 in