nand2tetrisを実装する(3)第3章順序回路-前編- - セキュリティ・キャンプキャンパー育成枠の活動録

記事が長くなると判断し、本記事では第3章のレジスタの部分を前編として書いていきます。メモリ以降の部分は後編をお待ちください。

第3章順序回路

本章はフリップフロップ回路(実装済み)と既存の回路を使い、いわゆる記憶素子を実装していきます。

背景

記憶するという行為は時間に依存→「前に記憶したものを今思い返す」という行為が記憶
情報を記憶するための回路を構築するには、時間経過を表す方法を考案しなければなりません。

クロック

コンピュータでは継続的に変化する信号をマスタクロックが送信することで時間の経過を表現します。
ハードウェアでの実装はオシレーター(発振回路)に基づくのが一般的です。オシレーターは0/1などのふたつのフェーズを絶え間なく行き来します。0の始まりから0の終わりまでを周期と呼ぶ。この1周期を単位時間としてモデル化されます。
ハードウェアの回路網を使って、信号はプラットフォームの隅から隅まで、すべての順序回路に送られます。

ハードウェアに関しては専門外なのですが、本書の解説はとてもわかりやすいので理解しました。

フリップフロップ

応用情報技術者試験を受験した方や回路図に慣れ親しんでいる方であれば下図のような回路図は見たことがあるでしょう。
このフリップフロップについての詳細です。
f:id:RunshoesCS:20181204114021p:plain

フリップフロップ回路はコンピュータの中で基本となる回路です。フリップフロップ回路はいくつか種類がありますが、本書ではD型フリップフロップと呼ばれるタイプを用います。
D型フリップフロップ(DFF):インターフェースは1ビットのデータ入力(クロック入力？)と1ビットのデータ出力。クロック入力はマスタクロックから信号が絶えず送られます。データ入力とクロック入力が合わさることで、本回路は「時間に基づく振る舞い」が可能になります。時間に基づく振る舞いの式は、out(t)=in(t-1) inとoutはゲートの入出力値を、tは現在のタイムユニットを表します。つまり、本回路はひとつ前のタイムユニットの入力値を出力しているだけです。
コンピュータで状態を保つために用いられる装置(レジスタ、RAMなど)はこの基本となる振る舞いによって形成されます。

この回路自体は1つ前の状態を出力するだけで、後述の装置を実装していくうえで必要な回路となるということだと判断しました。

レジスタ

レジスタとは、データを格納・呼び出しする記憶装置です。out(t)=out(t-1)(ひとつ前のタイムユニットの出力値を出力する？)を実現します。
DFFは前述のout(t)=in(t-1)を実現します。
そのため、DFFの出力を入力に送信すればうまくいくのでは？←これではうまくいきません。なぜなら、新しいデータの値をこの回路(レジスタ)に読み込む方法が明らかでないからです。どのタイミングでinからのデータを読み込み、どのタイミングでoutからデータを読み込むのかをDFFに指示する方法が存在しないからです。回路設計において、一般的には、ひとつのソースだけから入力データが送られるようにする必要があります。
以上から、入力の曖昧さを回避するにはマルチプレクサを導入するのが自然です。さらに、マルチプレクサへの「選択ビット」はレジスタ回路への「読み込みビット」の役割も狙えます。レジスタに新しい値を保持させたい場合、その値を入力inに入れて、「読み込みビット」のloadに1を設定すればいいです。内部の値をレジスタに保持させたい場合、loadの値を0にすればよいです。
任意の幅のレジスタを実装する場合は、1ビットレジスタを必要な数だけそろえて、それらを配列上に並べて構築できます。多ビットレジスタは幅をパラメータとして考えなければなりません。(値の候補としては16，32，64など)多ビットのレジスタの持つ値は一般的にワードと呼ばれます。

レジスタの実装時には、マルチプレクサを使うことで、新しい値を保持するか、内部の値を保持するかを選択できることで、正しい実装ができる。
また、レジスタを複数並べることで、多ビットレジスタができるということです。

仕様と実装

レジスタ

ビット(2値素子)

背景の説明と設計通り、マルチプレクサを使うことで実装できます。
実装

// 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/03/a/Bit.hdl

/**
 * 1-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 *                 else out does not change (out[t+1] = out[t])
 */

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:
    // Put your code here:
    
    // if(load==0)ならば読み込み
    // if(load==1)ならば書き込み
    Mux(a=fo,b=in,sel=load, out=w1);
    DFF(in=w1, out=out,out=fo);
    
}

レジスタ(16ビット)

こちらも背景の説明と同様に、Bit回路を並べていくことで完成します。
実装

// 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/03/a/Register.hdl

/**
 * 16-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 * else out does not change
 */

CHIP Register {
    IN in[16], load;
    OUT out[16];

    PARTS:
    // Put your code here:
    Bit(in=in[0],load=load, out=out[0]);
    Bit(in=in[1],load=load, out=out[1]);
    Bit(in=in[2],load=load, out=out[2]);
    Bit(in=in[3],load=load, out=out[3]);
    Bit(in=in[4],load=load, out=out[4]);
    Bit(in=in[5],load=load, out=out[5]);
    Bit(in=in[6],load=load, out=out[6]);
    Bit(in=in[7],load=load, out=out[7]);
    Bit(in=in[8],load=load, out=out[8]);
    Bit(in=in[9],load=load, out=out[9]);
    Bit(in=in[10],load=load, out=out[10]);
    Bit(in=in[11],load=load, out=out[11]);
    Bit(in=in[12],load=load, out=out[12]);
    Bit(in=in[13],load=load, out=out[13]);
    Bit(in=in[14],load=load, out=out[14]);
    Bit(in=in[15],load=load, out=out[15]);
    
}

以上で第3章前編のレポートを終わります。
次回は第3章後編、メモリ以降の内容です。