5日目: [CPU] レジスタの複数化とマルチプレクサ

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の5日目の記事です。

昨日は1bitのCPUを導入した。

要するにCPUとは、クロックが立ち上がるたびに、計算した値を変数に代入するループであった。 変数はDフリップフロップを用いて実装されており、そのように情報を記録する素子をレジスタと呼ぶのだった。

昨日はCPUの簡単な例を出すのが目的だったので、1bitレジスタ1個のCPUを考えた。 変数はaしかなかった。 今日はレジスタ4個、つまりa,b,c,dの4変数が扱える回路を考える。だいぶCPUらしくなるぞ～

1bitレジスタ4個のCPU

今日の目標はこの回路を理解することだ。 実はこの回路、4個のレジスタに対しmov命令が実行可能な回路になっている。

予告通り、Dフリップフロップが4個左側に並んでいる。このレジスタを上から順にa,b,c,dと命名した。

真ん中あたりに、MUXとかMとかDEMUXなどと書かれた台形の赤い素子がある。 MUXとMはマルチプレクサのことで、DEMUXはデマルチプレクサを表している。 今日はこいつらの解説がメインだ。

昨日の1bit反転CPUと比べると、線が全体的に四本になり、NOTゲートの代わりにマルチプレクサの入った回路になった。しかし本質は全く変わらない。 昨日も今日も、Dフリップフロップの出口(Q)を出発した線がぐるっと一周して入口(D)に帰還する回路であることに変わりはない。

マルチプレクサ

まずは最初の画像の右側にいるマルチプレクサ(Mと書かれた小さな台形)だが、その実装は

左側が省略記号で、右側が基本論理ゲートによる実装を表している。

真理値表は

入力 S	出力 Y
0	A
1	B

つまりマルチプレクサとは、A,Bの2つの入力データから出力を1つ選ぶゲートである。 A,Bを選ぶための線がSで、出力がYだ。 これを3入力1出力のマルチプレクサという。

A,B,Sの電圧が変わると即座にYの電圧も変わるので、マルチプレクサは組み合わせ回路である。 これをHDLで記述すると

module multiplexer_AB (
  input  A,
  input  B,
  input  S,
  output Y,
);

  always_comb begin
    if (S) Y = B;
    else   Y = A;
  end

endmodule

このようにalways_comb中でif文を使って書ける。

次に、マルチプレクサを拡張してみる。

A ,Bの2入力をA,B,C,Dの4入力にすると、最初の図の左下に位置する大きな台形のマルチプレクサになる

このマルチプレクサは6入力1出力となるが、入力6本のうちの4本はデータ線A,B,C,Dで、残り2本はどのデータを選ぶか指定するための線S1,S2となっている。 S1, S2をまとめてSとした絵が、最初の回路図に描かれている。 混乱を避けるために、最初の回路図ではSの線上に斜線を引いて2と書いた。この表記は今後も出てくる。

真理値表は

入力 S1,S2	出力 Y
0,0	A
0,1	B
1,0	C
1,1	D

HDLでこのマルチプレクサを記述すると

module multiplexer_ABCD (
  input  A,
  input  B,
  input  C,
  input  D,
  input  [1:0] S,
  output Y,
);

  always_comb begin
    case (S)
      2'b00  Y = A;
      2'b01  Y = B;
      2'b10  Y = C;
      2'b11  Y = D;
    endcase
  end

endmodule

Sが配列で与えられcase文が使用されているが意味はわかるだろう。 2'b00は、ビットサイズが2で、binary表示(2進数表示)で00で表される値という意味だ。

こういうコードを見たときには、直近のABCD入力のマルチプレクサの動画を思い浮かべて欲しい。 動画中では、Sの値に応じてABCDの1つをYに繋いでいることを強調したつもりだ。

デマルチプレクサ

最初の画像の右下にいるデマルチプレクサ(DEMUXと書かれた大きな台形)を説明する。

これは(S1,S2)の2進数を使い、4本の出力のうち1本を1にして、他は全て0にする組み合わせ回路である。

真理値表は

入力 S1,S2	出力 A,B,C,D
0,0	1,0,0,0
0,1	0,1,0,0
1,0	0,0,1,0
1,1	0,0,0,1

回路図と真理表を見れば意味はわかると思う。

HDLで記述すると、組み合わせ回路(always_comb)であることに注意して

module demultiplexer_ABCD (
  input [1:0] S,
  output A,
  output B,
  output C,
  output D,
);

  always_comb begin
    case (S)
      2'b00 begin
        A = 1'b1;
        B = 1'b0;
        C = 1'b0;
        D = 1'b0;
      end

      2'b01 begin
        A = 1'b0;
        B = 1'b1;
        C = 1'b0;
        D = 1'b0;
      end

      2'b10 begin
        A = 1'b0;
        B = 1'b0;
        C = 1'b1;
        D = 1'b0;
      end

      2'b11 begin
        A = 1'b0;
        B = 1'b0;
        C = 1'b0;
        D = 1'b1;
      end

    endcase
  end

endmodule

冒頭のCPU再考

マルチプレクサとデマルチプレクサが分かったので、いよいよ本題だ。 最初の回路を再掲するが、まずは赤い部分を見て欲しい。

左下のMUXのあたりから線を辿っていくと

1. 左下のMUXは、レジスタa,b,c,dの出力の中から1つを選出している。どれを選ぶかはSyが決める。
2. 1で選ばれたデータが、レジスタaの出力と共にM(マルチプレクサ)に入っている。
3. 2でどちらが選ばれるかは、右下のデマルチプレクサの出力が決める。
4. 右下のデマルチプレクサのうちどれが1になるかは、Sxが決める。

つまり

• まずSyを使い、DフリップフロップのQ(出口)の4本から1つを選出する(yとする)
• 次にSxを使い、DフリップフロップのD(入口)に入る4本のうち1本をyで上書きする

という操作をクロックの立ち上がりのたびに実行している¹。

機械語とニーモニック

今回のCPUの挙動を具体的に考えたいので、Sx=00,Sy=01の場合を考察する。 一回のクロックで各レジスタがどのように代入されるかを現実に忠実に書き下すと

; 以下の4命令が、1回のクロックで同時実行される
mov a, b
mov b, b
mov c, c
mov d, d

ここで、mov a, bはC言語でいうところのa = b;のようなもので、aにbを代入するという理解でよい。 b, c, dについては自分自身を代入しており、普通のプログラミング言語に慣れた身からすると無意味な操作に映るだろう。 しかしCPUの場合、自分自身を代入することは「値を保持する」という操作に対応する。 昨日説明したように、各レジスタはクロック立ち上がりの度に値を保持するか変えるかの二択を迫られているのだ。

従ってCPUの挙動を現実に忠実に表現するには、4つのレジスタa,b,c,dのmov命令を書くのが原理的に正しい。 しかし、わざわざmov b, bとかmov c, cと書くのは面倒くさい。 値の保持は、いわばデフォルトの挙動だからあえて書く必要もないだろう。 ということで、普通は保持命令を簡略化して書く

mov a, b

この形式でCPUの挙動を表現する言語をアセンブリ言語という。 またアセンブリ言語で書かれたCPUの1命令(つまり1行)をニーモニックという。 またSxとSyの値を機械語という。 ニーモニックと機械語の対応関係は

機械語	ニーモニック	説明
0000	nop	何もしない
0001	mov a, b	aをbで上書き
0010	mov a, c	aをcで上書き
0011	mov a, d	aをdで上書き
0100	mov b, a	bをaで上書き
0101	nop	何もしない
0110	mov b, c	bをcで上書き
0111	mov b, d	bをdで上書き
1000	mov c, a	cをaで上書き
1001	mov c, b	cをbで上書き
1010	nop	何もしない
1011	mov c, d	cをdで上書き
1100	mov d, a	dをaで上書き
1101	mov d, b	dをbで上書き
1110	mov d, c	dをcで上書き
1111	nop	何もしない

機械語0000はニーモニックmov a, aになるかと思いきや、nopとなっている。 このときは全レジスタが変更されないので、つまり何もしないno-operationという命令を実行したとみなせる。

回路全体の記述

最後に今回の回路全体をHDLで記述しておく

// movとリセット命令を持つCPU
module mov_only_cpu( input CLOCK, input [1:0] Sx, input [1:0] Sy);

  logic a, b, c, d; // Dフリップフロップ
  logic y;          // ワイヤ
  logic next_a, next_b, next_c, next_d; // ワイヤ

  // コピー元のレジスタをxに繋ぐ
  always_comb begin
    case (Sy)
      2'b00: y = a;
      2'b01: y = b;
      2'b10: y = c;
      2'b11: y = d;
    endcase
  end

  // レジスタ更新用のワイヤを作る
  always_comb
    case (Sx)
      2'b00: begin
        next_a = y;
        next_b = b;
        next_c = c;
        next_d = d;
      end

      2'b01: begin
        next_a = a;
        next_b = y;
        next_c = c;
        next_d = d;
      end

      2'b10: begin
        next_a = a;
        next_b = b;
        next_c = y;
        next_d = d;
      end

      2'b11: begin
        next_a = a;
        next_b = b;
        next_c = c;
        next_d = y;
      end
    endcase
  end

  // レジスタの更新
  always_ff @(posedge CLOCK) begin
    a <= next_a;
    b <= next_b;
    c <= next_c;
    d <= next_d;
  end

endmodule

少し長いが、基本は昨日の1bit反転CPUのHDLコードと同じだ。 あのコードからNOTゲートを抜いて、レジスタをa,b,c,dの4個に増やし、マルチプレクサとデマルチプレクサを加えたにすぎない。

最初のalways_combのブロックは回路図のMUXで書かれたあたりの線の繋がりを記述している。 二番目のalways_combのブロックは回路図のDEMUXとMで書かれたあたりの線の繋がりを記述している。 最後のalways_ffのブロックは回路図の左端でワイヤがDフリップフロップに接続している箇所を記述している。

どうでもいい話

今書いた回路全体のHDLには、CPUとして重要な機能が2つ欠落している。

レジスタの初期化

現状のHDLコードでは、a,b,c,dの値を交換することはできるけど、「aの値を1にする」という操作ができない。 a,b,c,dに値をセットする機能はリセット機能と呼ばれている。 実際のPCは、電源ボタンを押したらCPUのリセット機能が走るように作られている(多分)。

値の表示

a,b,c,dの値を交換したところで、それが我々の目に見えなければ意味がない。 現状のHDLコードでは、a,b,c,dの値を外部から確認する術がない。 実際のPCは、CPUはメモリにつながっており、その中でVRAMと呼ばれる部分に値を書き込むことでディスプレイを光らせることができる。 FPGAでレジスタの値を手軽に見るには、レジスタとLEDを繋げて光らせれば良い。 この辺をうまくやるには制約ファイル等の説明が必要なのだが、面倒くさいので割愛。

---

1. ところでSxやSyはどこに繋がってるの？という疑問がわくが、本質的な答えはメモリだ。メモリから「機械語」をとってきて、それをCPU内(デコーダーと呼ばれる)で加工し、今回の回路図のSxやSyに渡すのだ。今はまだメモリを説明していないし、ちゃんと話すにはプログラムカウンタの知識もいる。ここでは深く考えないことにしよう。とりあえずは人力で、クロックの度にSxやSyにうまく電圧を印加すると思って欲しい。↩

4日目: [CPU] 1bitのCPUとHDL

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の4日目の記事です。

一昨日はトランジスタでNANDゲートを作り、昨日はDフリップフロップを作った。 今日はいよいよCPUを導入する。

昨日はややこしかったけど、今日は簡単だ。しかし今後1週間の中で最も重要な内容だと思う。

Dフリップフロップの復習

昨日登場したDフリップフロップだが、名前は長いし回路はややこしいしで、馴染めなかったと思う。 回路の詳細はぶっちゃけ理解できなくても問題ないのだが

• クロックが上がる瞬間に、入力(D)が出力(Q)にコピーされる
• その瞬間以外は、入力を変えても出力は変わらない

この2つの機能だけはしっかり押さえておく必要がある。

今後は、以下の長方形記号でDフリップフロップを表す。

左図が正式なのだが、クロックに繋ぐのは当然なので省略し、右図のように描くこともある。

1bit不変CPU

ここで、Dフリップフロップの出口を入口に繋いだらどうなるか考えてみよう。 図の左下のクネクネしたやつはクロック生成器を表している。

この回路、実は1bitのCPUなのである

Dフリップフロップの出口(Q)の電圧を、変数aだと思って欲しい。 すると、クロックが上がる毎にaを前回のaと同じ値で塗り替えていることになる。 つまり、a=aという代入命令を毎クロック実行していると解釈できる。 ちなみに上の動画のQの電圧は常にH(緑)なので、aはずっと1のままだと解釈できる。

aがずっと0の状況は以下の動画のようになる

1bit反転CPU

今見た1bit不変CPUの説明を読んでも、分かったような分からないような気分になると思う。そこで次の例を見て欲しい。

さっきと同じくDフリップフロップの出口と入口を繋いだ回路なのだが、途中にNOTゲートを挟んでみた。 さっきより代入してる雰囲気が増したと思う。

クロックが立ち上がる瞬間(つまりクロックが黒から緑に変わる瞬間)に、電圧がぐるーっと回っているが、これは見やすさのためであり実際は即座に伝わる。

この回路の挙動を詳しく説明すると

1. クロックが黒から緑に上がった瞬間に、Dフリップフロップの出口(Q)が入口(D)と同じ電圧になる
2. 入口(D)付近の電圧をb,出口(Q)付近の電圧をaとすると、1.の挙動はa=bの代入と解釈される
3. 代入後、電圧がぐるっと周回し、出口(Q)の電圧は入口(D)の電圧の逆になる
4. これはb=~aの計算を行ったと解釈される (~はビット反転を表す。1=~0, 0=~1)
5. 再びクロックが上がると、代入命令a=bが実行される...

重要な部分だけ抽出すると

• 代入 : クロックが立ち上がる瞬間に、Dフリップフロップの入口が出口を上書きすること
• 計算 : クロックが立ち上がった後に、Dフリップフロップの出口から出た電圧がNOTゲートを通過すること

CPUとは、このように代入→計算→代入→計算→...を繰り返す回路のことなのだ。

CPUの基礎は以上で尽くされる。代入と計算だけだ。これが説明できて嬉しいぜ～

ちなみにクロック立上りの際に「何も代入しない」という選択肢はない。 元の値を保持したければ、最初の回路のように「前回と同じ値を代入」する必要がある。 電圧は0と1しかない(NULLもundefinedも空文字もない)ので、Dフリップフロップはクロック立上り毎に値を変えるか否かの二択を迫られている。

Dフリップフロップのように、CPUの回路上で変数のように働く(情報を保持する)素子をレジスタという。 レジスタを実現する素子は色々あるのだが、とりあえずはDフリップフロップ=レジスタと思って問題ない。

明日以降はレジスタの数を増やし、またNOTゲートの代わりにもっと複雑なゲートを使うことで、CPUをどんどん高機能化していく予定だ。

1bit反転CPU製作キット

今導入した1bit反転CPUを、ハードウェア記述言語(Hardware Description Language, HDL)のSystem Verilogで記述したい。 HDLは変わった言語で、一見ふつうのプログラミング言語に見えるのだが、実態はかなり違う。 以下では、僕の(不正確で浅い)理解に基いてHDLを説明しようと思う。後で大幅に書き換えるかも。

例として、さっき電圧がぐるっと周回していた、1bit反転CPUの製作キットを秋葉原で買ったとする。箱を開けると以下の3パーツが詰まっていた。

内容物は以下の3つだ

• a : Dフリップフロップ
• inv : NOTゲート
• b : ワイヤ

これらの出口を入口に繋いでCPUを組み立てる。 クロックは後で買うとして、組立説明書を見ると

左図では、aの出口をinvの入口に繋ぎ、invの出口をbの入口に繋いでいる。 また説明文にある通り、aの出口の電圧が変われば、その変化はinvを抜けてワイヤーのbまで一瞬で伝わる。 こういう線の繋ぎをalways_combというらしい。

右図では、bの出口をaの入口に繋いでいる。 説明文にある通り、bの電圧が変わっても、Dフリップフロップのaの出口電圧はすぐには変わらない。 こういう線の繋ぎをalways_ffというらしい。

ここまでの話をまとめると、線の繋ぎ方は2パターンあることが分かった。 電圧が即座に反映されるような繋ぎ(always_comb)と、クロック立上りの瞬間だけ電圧が伝わるような繋ぎ(always_ff)の2種類だ。

そんなこんなで製作キットが完成した。

ハードウェア記述言語(HDL)

唐突だが、今の1bit反転CPUをHDL(Hardware Description Language)のSystem Verilogという言語で記述してみる

module cpu( input CLOCK);

  logic a;    // 素子aを用意
  logic b;    // 素子bを用意

  always_comb // 電圧変化が即座に伝わる繋ぎを書く
    b = ~a;   // bの入口に、aの出口を反転して繋いだ
              // bの出口は即座に電圧が変わる。
              // つまりbはワイヤーだ

  always_ff @(posedge CLOCK) // 電圧変化がクロック立上りの瞬間だけ伝わる繋ぎを書く
    a <= b;   // aの入口に、bの出口を繋いだ
              // aの出口はクロック立上りの瞬間だけ電圧が変わる。
              // つまりaはDフリップフロップだ

endmodule

要するにHDL (System Verilog)は

1. logic宣言で素子をたくさん用意する
2. 素子間の繋ぎをalways_combとalways_ffの2パターンに分ける
3. =や<=を用いて、素子の出口を入口に繋ぐ

という言語だ(と僕は思う)。

ちなみにHDLコードの1行目にinput CLOCKという引数がある。 これはmoduleからendmoduleの中に、外部からCLOCKという線を引っ張ってくるという意味だ。 CLOCKは多くの場合にalways_ffの条件指定子(いつ電圧が伝わるか)的な役割を担うことになる。

またHDLコードをよく見ると

• always_combの中では=を使って線を繋ぐ
• always_ffの中では<=を使って線を繋ぐ

となっている。この辺の記号の使い分けはややこしいので、詳細は明日以降に回す。 要するにイコールっぽい記号で線を繋ぐのだなと思って欲しい。

HDLはプログラミング言語ではない

HDLは回路図の絵を描く言語だ。極論すると、有向グラフの絵を描くための言語といえる。 決してプログラミング言語ではないので、注意しないといけない。

たとえばさっきのコードにa <= bがあったけど、これはプログラミング言語の代入文とは全く違う。 つまり変数aに変数bの値を代入するのではない。 素子aの入口に素子bの出口を繋いだだけだ。

最初に1bit不変CPUを導入したとき、CPUは代入と計算を繰り返すと説明したが、それは

1. HDLに従って回路素子を用意し、出口を入口に繋ぐ
2. 線をつなぎ終えた後の回路(1bit反転CPU)に電源を入れて、電圧変動をじーっと眺める
3. フリップフロップ周辺の電圧の時間変化が、プログラミング言語における代入命令のように見える
4. NOTゲート周辺の電圧の時間変化が、プログラミング言語における計算命令のように見える

つまり記事の最初の方に出てきた 代入→計算→代入→計算→... の代入は、回路が完成した後の動作の様子を言語化したものだ。 一方、HDLのa <= bは回路そのものの作り方(線の繋ぎ方)を表している。 これらを混同してはいけない。

言い換えると、HDLは回路の機能を記述する言語では無いのだ。 もちろん何らかの機能を実現するために回路を作るわけだが、その際はまず自分の頭で機能を回路図に変換し、次に回路図をHDLで記述するという手続きを踏むことになる。 今回の場合は

1. 「代入できる変数が欲しい。そこにbit反転して代入する機能も欲しい」という欲求があった
2. その機能は、Dフリップフロップのループ回路で実現できると考えついた
3. そのループ回路をHDLで記述した

という風に僕は考えている¹。

どうでもいい話

僕にはHDLを解説する力量が無い。今も、見よう見まねで適当に書いている。

HDL言語の見た目は、プログラミング言語にそっくりだ。 if文, for文, case文, 四則演算、代入(のような操作)、変数宣言(のような操作)などもある。親しみ深いだろう。 見た目はとっつきやすい。しかし実際は、、、

恥を忍んで、HDLを触り始めたころの僕と、HDLに詳しい人との実録会話をメモしておく

「HDLはどこから処理が始まるんや？main関数はどれや？」

「質問が的外れ。HDLは回路の満たす性質を列挙するものであり、開始やリターン文といった概念は無い」

「always_combとかalways_ffとか意味不明なんやが」

「線を繋ぎ終えた後に満たして欲しい状況を記述する。それを状態と遷移に分ける。前者はalways_comb、後者はalways_ffに書く。簡単なことだ」

「always_ffの中でLEDに1を代入したのに光らんかった」

「always_ff内でワイヤーに線を繋ぐとエラーが出るのは当然だろう。クロック立ち上がり以外で右辺が変化すると破綻する。あと代入という言葉を使うのはやめろ」

「logic a;で変数aを宣言して代入するとき...」

「それはフリップフロップであり変数ではない。そして代入より線を繋ぐという表現の方が適切である」

「for文でレジスタに入ってる値を増やして、LEDに繋いでチカチカさせたいんやが」

「for文は貴様の想像しているものとは違う。あれはコピペ作業を簡略化するための構文である。」

「FPGAからPCにUARTで情報を送りたいときは、01の列を送って、情報を送り終えたらNULLにしといたらええんやな？」

「電圧は0か1しかない。NULLなどない。情報を送らない時は常に0を送り続ける。情報を送りたい時は1を何度か送ってセッションを開始する」

「コンパイルに時間かかりすぎてクソ辛いんやが」

「論理合成やインプリメントはNP困難な問題や四色問題が絡むので、時間がかかって当然」

「なんかいろいろうまくいかんのやが」

「どういう回路図になるか想像しながらHDLを書いてるか？」

「いやぜんぜん」

「HDLはハードウェアを記述する言語だ。どういう回路を作りたいか考えてないのに、それを記述するのは無理にきまっているだろう」

---

1. 初心者が勝手に考えているだけなので、あまり信用してはいけない。↩

3日目: [半導体回路] Dフリップフロップ

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の3日目の記事です。

昨日はnMOSトランジスタの動作原理を説明し、NANDゲートを作り、さらにANDゲートやORゲートも作った。

今日のメインテーマはDフリップフロップ(DFF)だ。こいつはNANDゲートを元に作られている。 彼こそがCPUの本体であり、CPUそのものだ。

順序回路と組み合わせ回路

我々は情報を記録したい。

ノートに数字を書き込むかのごとく、電子の力で回路に数字を書き込みたい。 しかし、例えばORゲートを考えてみると

入力が変わると出力も変化してしまう。 「記録」を回路の言葉に言い換えると、入力が変わっても出力は変わらないということだ。 ただのORゲートでは、入力が変わると出力も変わるので、情報は記録できない。

そこで、ORゲートの出力を入力に繋いでみると

時刻	入力	出力	イベント
0s	L	L	開始
3s	H	H	入力を上げたら、出力も上がった
6s	L	H	入力を下げたが、出力は変化なし

「入力電圧が高くなった(ことがある)」という情報が記録できている。嬉しい。

ここまでの話を強引にまとめると

• 出力が入力に戻らないと、情報は記録できない(組み合わせ回路)
• 出力を入力に繋げば、情報が記録できる(順序回路)

記憶素子の作り方が分かり嬉しいわけだが、、、しかし今導入したORのループ回路は不便すぎる。 一度情報を記録すると、(回路全体の電源を落とさない限り)上書きできない。 また入力を常に監視しており、「2秒後の状態を記録してほしい」のような記録タイミング指定機能もない。

もっと良い記憶素子がほしい。 そこで登場するのがDフリップフロップだ。

Dフリップフロップの概要

Dフリップフロップの回路図を見てみる。

ややこしすぎて泣きそうになる。完全に意味不明だと思うが、まず落ち着こう。 とりあえず確認すべきは、左上の入力Dと、左下の入力CLOCKと、右上の出力Qだ。 次に確認すべきは線がナナメになっている箇所。 NANDゲートの出力が入力に繋がっている。 ORゲートで見たように、こういう配線には情報記録の雰囲気がある。

回路図はややこしいので、下のタイムチャートを見よう。 このグラフは、各時刻におけるD(入力)、Q(出力)、クロックの電圧を表しており、右に行くほど新しい時刻になる。 クロックは未説明だが、要するに電圧のHとLが時間変動する素子に繋げば良い¹。 そしてここからが重要だが、時間経過を追うと

時刻	D(入力)	Q(出力)	クロック	イベント
0	L	L	L	開始
1	H	L	L	入力を上げたが、出力は変化なし
2	H	H	H	クロックが上がる瞬間に、入力が出力にコピーされた
3	H	H	L	クロックがLに戻ったが、出力は変化なし
4	L	H	L	入力を下げたが、出力は変化なし
5	L	L	H	クロックが上がる瞬間に、入力が出力にコピーされた

簡潔にまとめると

• クロックが上がる瞬間(タイムチャート黄色)に、出力が入力と同じ状態になる
• その瞬間以外(タイムチャート白色)は、入力をどれだけ変化させても出力は変わらない (タイムチャートの白色のところ)

さっきのORループ回路にはなかった記録タイミング指定機能と、上書き機能が搭載されていることが分かるだろう。

ここから先は、Dフリップフロップがなぜこのような挙動を示すのか、回路図から理解していく。

入力の遮断

回路図の分析に移ろう。 この回路にはNANDゲートが8個入っている。 よくみると左から順に四段構成になっていることが分かるだろう。

まず第一陣(左端)のNANDペアを見ると、クロックの反転電圧が入ってきている。 ここで、NANDは入力に(1つでも)Lが含れると、出力がHになることに注意しよう。 従ってクロックがHの時間帯は、入力によらず、第一陣の出力が両方Hに固定される。

次に第三陣(中央右)のNANDペアを見ると、クロックと同じ電圧が入ってきている。 従ってクロックがLの時間帯は、入力によらず、第三陣の出力が両方Hに固定される。

こうした事情により、クロックがHのときもLのときも、Q(出力)は一定になる。 入力をガチャガチャと変えても、出力は変化しない。 この結果を見ると、入力は出力に一切伝わらないと結論したくなる。 しかし後で(シンボリックな表現のところで)見るように、クロックが立ち上がる瞬間だけ、入力と出力がつながるのだ。

RSラッチ

今度は第二陣(中央左)のNANDペアと、第四陣(右端)のNANDペアを詳しく見ていこう。 よく見るとこいつらは同じ形をしている。 この2入力2出力回路はRSラッチと呼ばれている。

この動画を見ればRSラッチの仕組みと挙動はわかると思う²が、要するにどちらの入力を下げたか?という情報を保存する回路だ。 * 入力が両方Hの状況は、情報保持モード * 片方をLに変えると、情報が更新される。

シンボリックな表現

第一陣から第四陣までの説明を終えたが、これらを連結すると

白の4本の縦線は第一陣から第四陣までのNANDゲートを表している。 第一陣or第三陣の太線は、出力がHに固定された部分を表している。 第二陣と第四陣の色付きの玉は、RSラッチ保持された電圧情報を表している。

Dフリップフロップの仕組みが理解したければ、黙って5分間この動画を眺めるのが良いと思う³。 特に中央左寄りの、第二陣の玉を眺め続けるのだ。動作原理が理解できることを保証しよう。

重要なのはクロックがLからHになる瞬間で、CLOCK: H edge と書いておいた。 この瞬間、入力のDから出力のQまで一色になる。他の時間帯は入力と出力が切り離されている。

文章による説明

上のgifアニメをしっかり眺めたところで、もう一度回路図を見てみよう。

説明の前に、クロックが下がる直前にD(入力)の電圧は変化しないと仮定しよう⁴。

クロックがLからHに上がる瞬間

まず第一陣と第二陣のNANDゲートに着目する。

1. 動画ではクロックがLの時にD(入力)を変えているので、その電圧変化は第二陣の出力に伝わっている
2. クロックが上がると、第二陣のRSラッチの入力は両方共Hになり、情報保持モードに移る
3. つまりクロックが上がる直前と下がった後で、第二陣の出力は変化しない
4. クロックが上がった後に入力を変更しても、第二陣は以前の状態を保持し続ける

次に第三陣と第四陣のNANDゲートに着目する。

1. クロックがLの時、第三陣の出力は両方共Hなので、第四陣のRSラッチは情報保持モードになっている
2. つまり第四陣の出力は、前回の状態をキープしたまま動かない
3. 次にクロックが下がった後を考える
4. クロックが上がる直前と下がった後で、第二陣の出力は一定のまま変化しなかった
5. クロックが上がった後は、第二陣の出力が第三陣の出力に引き継がれ、更に第四陣の出力結果(Q)に引き継がれる

クロックがHからLに下がる瞬間

この時に出力は変化しないのだが、その理由は

1. クロックがHのとき、D(入力)の情報は第一陣で遮断されてしまう。
2. つまり記憶素子のRSラッチまで情報が届かない。
3. クロックが下がった後も、D(入力)の情報が第三陣で遮断されるので、Q(出力)には届かない

どうでもいい話

今日はDフリップフロップ(正式名称はマスタースレーブ式立上がりエッジトリガ型Dフリップフロップ回路)の仕組みに全力投球した。 正直、この記事を読んだ人がどれぐらい理解できるか心もとない。 仕組みが完全には理解できなくても

• クロックが上がる瞬間に、入力が出力にコピーされる
• その瞬間以外は、入力をどれだけ変えても出力は変わらない

という挙動さえわかれば、明日以降に支障はない。

Dフリップフロップは圧倒的超絶的に重要だ。 実は彼こそが、CPUの本体であり、CPUそのものなのだ。

明日はDフリップフロップを使い、1bitのCPUを作る予定。

---

1. 電圧が振動する素子は色々な作り方がある。例えばトランジスタとコイルで構成される非安定マルチバイブレータを元に作ることもできる。本格的なCPUでは水晶発振子が使われるらしい。↩

2. RSラッチの入力を両方Lにするのはヤバい行為として禁止されている。両方のNANDが切り替わる僅かな時間差に応じて、出力状態が変わるため、論理的に予測できない挙動が起きてしまう。Dフリップフロップでは、入力の片方は必ずHなので問題ない。↩

3. なぜ僕の作るgifアニメはキモい感じになるのだろう。↩

4. 仮定というか、そうなるように回路全体を構成する必要がある。↩

2日目: [半導体回路] トランジスタと論理ゲート

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の2日目の記事です。

今日はトランジスタのスイッチング機能と、それを用いた論理ゲートの実装をまとめる。

トランジスタ

この世には半導体と呼ばれる物質があり、n型とp型に分類されている。 n型半導体は電子をたくさん含み、p型半導体にはあまり含まれていない。

半導体と金属と絶縁体を以下のように接合したデバイスは、(nMOS型)トランジスタと呼ばれている。

一番目の図¹を見て欲しいのだが、これは3本の金属線の生えた半導体デバイスだ。 上段と下段の金属は、桃色で描かれたn型半導体に繋がっている。 2つのn型半導体の間にはp型半導体が存在するが、こいつは電子が少ない(あるいは、電子はp型半導体中に存在できない)ため、このままでは上段下段間に電子は流れない。 また中段の金属は絶縁体に繋がっているので、上下段と電子をやりとりすることは絶対にない。

二番目の図を見て欲しい。 中段の金属に正の電圧を印加した結果、絶縁体の裏側に電子が集まっている。 掃除機の先に布を被せて吸引すると、布にたくさんのホコリがひっつくのと同じ原理だ。

電子は中段の絶縁体の裏側に「存在する権利」を得たことになる。 こうなると、電子は上段下段間を自由に移動できる。 つまり上段と下段は、右の図のように導体で繋がったと見ることができる(三番目の図)。

仕組みをまとめると、

• 中段の電圧が零のとき: 上下は絶縁されている
• 中段の電圧が正のとき: 上下は繋がっている

言い換えると、上下の金属の間には制御機能付きのスイッチ(中段の金属のこと)がはさまっており、その電圧に応じてスイッチが切り替わるわけだ。²

トランジスタとNOT回路

以下の説明では、電圧が零の部分をL、電圧が正の場合をHと呼ぶことにする。 電圧の高低(H or L)を論理値(0 or 1)に対応させると、電気回路を用いて論理計算ができるようになる。 こうした用途の電子回路を論理回路と呼ぶ。

トランジスタを使って論理回路を作りたい。

しかしトランジスタは制御機能付きのスイッチでしかなかった。 論理回路を作るには、スイッチ機能を電圧のH or Lに変換する必要がある。 これは以下の回路で実現できる。

回路図の緑の部分は電圧正(H)、灰色の部分は電圧零(L)を表している。

両図の右端に描かれた、短い縦線と長い縦線からなるユニットがnMOS型のトランジスタだ。 よく見ると線が3本(上、左、下)生えていることが分かるだろう。 トランジスタの中段はスイッチ(白いナナメの線)とつながっており、その先は左図の場合L、右図の場合Hに繋がっている。

右図では電流が流れている。トランジスタの中段に正の電圧が掛かることで、トランジスタのスイッチがONになり、上段と下段が1つの導体として繋がったのだ。

ここでトランジスタの中段を「入力」と見立てて、右端にひょろっと出た電線の電圧を「出力」と見立てる。 入力と出力に関係ある部分だけを抜き出すと

入力1	出力
L	H
H	L

という変換を行っており、いわゆるNOTゲートだとわかる。 回路図をいちいち描くのは場所の無駄なので、今後は論理記号(MIL記号)で表す。

このMIL記号だけ見ると、「NOTゲートにゼロ電圧を入れると高い電圧が出て来る。無からエネルギーがわいた！すごい！」などと勘違いしそうになる。 言うまでもないが、MIL記号は「入力と出力」だけを表示しているのだ。 「働くのに必要な電力の確保」が描かれていないだけで、無からエネルギーがわいたわけではない。 この例のように、ちゃんと閉じた回路の一部を切り取って表示した回路は今後頻出する。 そういう回路の破片を見たときはHとLを他所から仕入れて、入力がその一方を選び、出力に渡していると考えるとよいと思う。

NANDゲート

NOTゲートのトランジスタを2つに増やしてみる

トランジスタの増加に伴い、入力が2つになった。出力は1つのままだ。

入力1	入力2	出力
L	L	H
H	L	H
L	H	H
H	H	L

Lを論理値の0、Hを論理値の1とすると、これはNANDゲートだ。MIL記号は、ANDの前方に否定を表す丸印がついたマーク

他の論理素子

ANDとORとXORを、NOTとNANDで構成しておこう。

AND回路

OR回路

XOR回路

これで基本的な論理ゲートが揃った。

どうでもいい話

今日はまずトランジスタの性質を説明し、それを用いてNOTとNANDを作った。 その後NOTとNANDだけを用いてANDとORとXORを構成したが、そこにトランジスタは登場しなかった。 NOTとNANDによって存在が覆い隠されたのだ。 この隠蔽は、情報分野における抽象化の連鎖の起点だと(僕は勝手に)思っている。

ところで、物理学と情報科学の違いを考えたところ、情報は抽象化の回数がやたらと多い気がした。 ここで言う抽象化は、扱いやすい量を定義して、低層構造を隠蔽するみたいな感じ。 物理でもくりこみ群を考えたり量子論と古典力学の対応を考えることで、この世界のレイヤー間の関係性を探ろうとするけど、層の数はそれほど多くないと思う。 情報はそれどころじゃないぞ。 電子回路図に始まり、MIL記号、加算器やマルチプレクサ、RTL、HDL、機械語、ニーモニック、カーネル、C言語、apache、php、webフレームワーク、プラグイン、、、といった具合に果てしなく高い塔が建設されており、今なお成長中という印象がある。

回路図を描くのに使ったのはこのサイト。 ここで遊べば回路がなんとなく分かるようになる。かも。

明日は順序回路、特にエッジトリガ型のD-Flip-Flopの動作原理を書くつもり。 残り23日、頑張ろう。

---

1. 図を見れば分かると思うが、僕には絵心やデザインセンスが全くない。↩

2. トランジスタに関する雑な説明だったが、本質は外してないと思う。半導体の詳細は全然知らんのだが、トランジスタの挙動を簡単な議論で(手計算で)知りたければ、周期ポテンシャル下のシュレディンガー方程式の固有値スペクトル(バンド構造)から出発して、量子統計(フェルミディラック分布)と半古典的な輸送方程式(ボルツマン方程式)を用いて伝導度を求め、ドープされた半導体界面付近の空乏層で輸送係数がどうなるか計算する必要がありそう。特に電圧によるスイッチングを真面目に計算するには、電圧伝導度間の非対角応答を見たいので久保公式が必要かも?バンド構造が簡単なら積分実行できそうやけど、詳細は知らん。実際のSi半導体に関する物性を定量的に予測したければ、計算機で密度汎関数法やるしかなさそう。↩

1日目: 方針

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の1日目の記事です。

自己紹介

はじめまして。都内のIT屋で働いている解答略という者です。

去年の冬まで物理系の大学院博士課程に在籍していて、情報系とは無縁でした。 大学を離れる間際に、何の知識も無いままIT業界に入ると怖い人に怖い事を言われると思い、情報科学科の後輩を訪ねたところ「低レイヤを知れ」というアドバイスをもらい、 大急ぎでエミュレータとコンパイラとCPUを作りました。

時系列で振り返ると

• 2017年1月下旬、1週間弱かけてx86のニーモニックを調べ、しょぼいエミュレータを作った
• 次の2週間でC言語のサブセットのしょぼいコンパイラを作った
• その後、3月上旬までFPGAと格闘し、マジでしょぼいCPUを作った

大急ぎで作ったのでマジでくそしょぼいやつしかできませんでしたが、「PCの動作原理の雰囲気は掴んだ」という実感がわいたので、まぁええかと思いました。

作る前は、、、フリップフロップ、マルチプレクサ、キャリーフラグ、HDL、RTL、FPGA、ニーモニック、オペランド、BNF、抽象構文木、シンボルテーブル、スタックマシンなどの単語は聞いたことすらありませんでした。 そんな有様から出発したわけですが、一ヶ月ぐらいでなんとかなるものです。 低レイヤに関する知識を持たない読者の方も、敬遠する必要は無いと思います。 原理原則だけであれば、想像よりはるかに簡単だと思います。

本題

このAdvent Calendarの目標はただ一つ、目の前のPCがどのように動いてるのか理解することです。

しかし現代のPCは極度に複雑なシステムで、全てを完全に理解するのは多分不可能です。 そこで今回はCPUの挙動にフォーカスし、電子回路からC言語に至る一本の道筋を提示しようと思います。 言い換えると、普段目にする抽象的なプログラムコードから、CPU内の電圧変動が想像できるようになりたい。 こうした能力を身につければ、PCの仕組みを(なんとなく)理解した(ような雰囲気になれる)と思います。

一年前の僕はそんなことを考えながら、せっせと低レイヤの環境を自作していました。 あれから日が経って知識を忘れつつあるので、今のうちに当時のメモを再編集して公開しようと思いました¹。 今後の予定をざっくり書くと

第一週目:回路素子とCPU

• トランジスタと電子回路
• フリップフロップと1bitのCPU
• 機能追加していい感じのCPUにする
• FPGAでCPUを作る

第二週目:x86

• レジスタの種類
• 数値の扱い
• 命令セット
• エミュレータの作成

第三週目:コンパイラ

• 字句解析
• 解析木
• 抽象構文木
• シンボルテーブル
• コード生成

第四週目:完動

• コンパイラの吐いた機械語がx86エミュレータ上で動く
• FPGAのCPU上でも動く

抽象化の階段を一歩づつ登る形式です。 順序は大きく変わらないと思いますが、各パートの分量が未知数なので予定通りに進むかは微妙です。 ただ、頓挫することだけはないように頑張りたいと思います。

我々の敵

なにぶん初心者なので、難しいことは手を出さないようにしていました。 しかし教科書読んで終わりというのも違う気がしたので、以下の点に気をつけていました。

敵1: 概論

高校や大学教養学部の情報の授業は「メモリーは机だよ～」的なフワフワした概論に終始し、嫌悪感を覚えていました。 そこで、全部自分で作れば必然的に全ての概念と向き合うことになると思い、何でもかんでも自作しようと考えました。 そして完成品の質が低かったとしても、とりあえず動くという結果だけは譲らないことにしました。 概論だけで終わらないようにします。

敵2: 最適化

PCの動作原理を理解するのが目的なので、基本に忠実にいきたいと思います。 なので最適化は後回しです。 つまり実行効率が悪かろうととりあえず動けば勝ちの精神でいきます。 最適化は理解の敵だと思っています。

敵3: x86から逃げる

ひとくちにCPUと言っても沢山の種類あるのですが、僕達が普段使うパソコンにはx86というタイプのCPUが入っています。 x86の仕様はややこしい(らしい)のですが、しかし今回はCPUからエミュレータからコンパイラまで、全てをx86ベースで製作することにしました。 理由は、他のCPUをベースにすると目の前のPCを理解した気にはなれないと思ったからです。 x86を基軸にすれば、自作しながら普段使ってる環境がどうなってるのか学べるので面白いと思います。

敵4: 完成度の向上

例えばx86の命令セットを完全にカバーするような不毛な作業はしません。最低限の命令だけを雑に実装します。 上位レイヤーのコンパイラ氏にとって不都合がなければ、それでOK。 機能も完成度も貧弱ですが、その代わりCPU、エミュレータ、コンパイラの全てが協調して動くことに全神経を注ぎたいと思います。

敵5: 周辺機器

IO周り(つまりマウスやキーボード)の取扱いがひどい(というか、ほぼない)ので、気になる方が多いと思います。 ブート処理についても首を傾げる方が多いと思います。

偏った意見で恐縮ですが、PCの動作原理を理解するためには、まずCPUとメモリだけからなる系を考えるのが良いと僕は思うのです。 周辺機器の割込処理やブート処理については、その後OSを自作することで身につけるのが良いと思っています。 そういう思想に毒された人間ですので、周辺機器の扱いについては「仮想メモリにうまいことマップされる」程度でお茶を濁しています。

その他諸々

重要なことですが、初心者が適当に書く記事なので誤った内容が多々あると思います。ミスだらけの前提で読んでください。 尚、僕がミスに気づいた場合には面倒くさいので注釈とかいれずに勝手に直すことを了承下さい²。 はてブやtwitterでミスを指摘していただいたら、記事の最下段で言及すると思います(時間があれば)。

特に専門用語に関してですが、「とりあえず動く」という状況を達成する上で用語の厳密な定義はほとんど必要なかったので、使い分けの不適切な箇所が多々あると思います。 例えばCPUとMPUとコアとプロセッサの違いとか、シミュレータとエミュレータとデバッガの違いとか、ラッチとフリップフロップの違いとか、僕は全然知りません。 変なことを書いてたら遠慮なく指摘して下さい。直しますので。

また昔の自分に言い聞かせるつもりで書くので、随所に失礼な表現があり読者を腹立たせるかもしれません。 明日からは敬語じゃなくて「OOはXXだ。」みたいな文章を書くと思います。 私的なメモ帳をのぞき見るつもりで読んでいただければ幸いです。

それでは、明日から23日間よろしくおねがいします。

---

1. アドベントカレンダーに登録すれば、怠惰な自分でも復習するだろうと思って登録したら、予想外にバズってビビりました↩

2. 正確な情報が欲しい人は、こんな個人的なメモではなくちゃんとした教科書を読むべきです。ブログをあてにしてはいけません。↩