RustでRAMの動作原理をシミュレートする

頭おかしいタイトルですね。何を言っているんだお前は。

本記事は CADDi とは何の関係もありませんし、実用的価値も一切ありません。その点はご了承を。

あ、Rust が分からないからといって帰る必要はありません。この記事はほとんどRustと無関係です。なんらかのプログラム言語に親しんでいる方であれば雰囲気で読める程度の機能しか使っていないのでご安心ください。

nand2tetris

先日、こちらの記事が話題になっていました。 Nand2Tetris(コンピュータシステムの理論と実装)でCPUからOSまで一気通貫で作るのが最高に楽しかった話

この記事にあるように、O'Reilly Japan - コンピュータシステムの理論と実装 、またの名を nand2tetris と呼ばれる本があります。NAND素子を出発点として簡単なゲームを作るまで(何故か作るのは名前に反してテトリスではない…)を一気通貫に説明してくれる本です。

上の記事の方は完走されたそうで、すごいですね。私は根気が続かず、途中でやめてしまいました…。お恥ずかしい。

しかしながら、やはりこの本が最高に楽しいのは前半のハードウェアのところではないかと思っています。私は本書に沿って、ハードウェアの動作をシミュレートするプログラムをRustで書いてみました。

やったのはずいぶん昔なのですが、上記の記事で思い出したので紹介してみます。キッカケを作ってくれた記事に感謝です。

NANDとフリップフロップ

NAND

pub fn nand(a: bool, b: bool) -> bool {
    !(a && b)
}

言わずとしれたNAND素子です。 論理ゲートの入出力は電圧による 0/1 ですから、これを bool 型でシミュレートすることにします。この形式の関数で、2つの入力と1つの出力を持つ論理ゲートがシミュレートできることがわかると思います。

実装には &&! といった演算子が使われていますね。こういった「高度な」演算子を使うのはここだけで、他の箇所では一切使いません。NAND素子を最もプリミティブな要素として、それを組み合わせて && のような論理演算をシミュレートしていくというのが目的なのですから、こういった演算子を使ってしまっては意味がありません。一方、nand() 関数だけはブラックボックスとして与えられるプリミティブな素子ですから、この実装だけはズルをするしかない、というわけです。

フリップフロップ

nand2tetrisの紹介で「NAND素子を出発点として」と書きましたが、実はもうひとつ「フリップフロップ」も所与のものとして与えます。

コンピュータの状態遷移はクロック信号によって駆動されます。従って、コンピュータやそれを構成する部品は、次のようなクロック信号のループに駆動されて動くというモデルで考えていきましょう。

loop {
    hardware.clock(...);
}

これを踏まえて、フリップフロップを次のようなコードでモデル化します。

pub struct Flipflop { bit: bool }

impl Flipflop {
    pub fn new() -> Self {
        Self { bit: false }
    }
    pub fn out(&self) -> bool {
        self.bit
    }
    pub fn clock(&mut self, a: bool) {
        self.bit = a;
    }
}

フリップフロップは1bitの状態を持っています。 入力 in が変化しても、すぐには出力 out には反映されず、内部で持っている bit の値を出力し続けます。そしてカシャッと clock が入力されたタイミングで、入力の値が内部に取り込まれます。

これをRustでシミュレートしたものが上記のコードです。out() 関数は単に self.bit を返す関数であり、clock() 関数によって内部状態を入力値に置き換えます。

clock() の実装において、値(状態)の代入という「高度な」操作が使われています。しかしこれ以降、Flipflop の内部以外では一切、mutable な状態変数への代入という操作は行いません。コンピュータは状態遷移機械であり、その「状態」を保持するための最もプリミティブな機構がこのフリップフロップです。それをシミュレートするのが目的ですから、Rust言語が備えている状態保持の機能を使ってしまっては意味がありません。フリップロップだけは、NAND素子と同様にブラックボックスとして与えられるものですから、その実装では「ズル」をしています。しかしこれ以降は、「状態」はすべてフリップフロップを組み合わせて表現していくことになります。

1bit レジスタを作る

ではいよいよ、レジスタを作っていきましょう。まずは最も簡単な、1bitだけを保持するレジスタです。こんな形をしています。 フリップフロップと比較すると、load という入力が増えていることが分かります。clock のタイミングで内部の状態が遷移するという点はフリップフロップと同じです。

この構造をRustのコードにすると、次のようになります。

pub struct BitRegister { flipflop: Flipflop }
impl BitRegister {
    pub fn new() -> Self {
        Self { flipflop: Flipflop::new() }
    }
    pub fn out(&self) -> bool {
        self.flipflop.out()
    }
    pub fn clock(&mut self, input: bool, load: bool)  {
        ...
    }
}

BitRegister 型は、内部にフリップフロップを1つ保持しています。そして out()フリップフロップout() をそのまま返しています。 問題は clock() の実装です。この関数で、inputload という2つの入力に応じて内部の状態が遷移します。

実現したいのは次のような動きです。

impl BitRegister {
    pub fn clock(&mut self, input: bool, load: bool)  {
        self.flipflop.clock(if load { input } else { self.out() })
    }
}

要するに loadtrue の場合のみ input が取り込まれて、loadfalse の時には状態は遷移しない、というわけですね。

しかし、上記は if 式を利用しています。これはズルです。物理デバイスif を直接実現するものはありません。ですから、NANDを組み合わせて if に相当する回路を組まなくてはなりません。if すら使ってはいけないプログラミング、相当頭おかしい感じがしますが、やっていきましょう。

1bit レジスタを実現する回路は、下図のようなものです。(※ DFF と書かれているのは Data Flipflop の略で、要するに上で定義した Flipflop 型です。) Mux という素子が登場しています。これは multiplexor と呼ばれる素子で、if に相当する機能を担うものです。Rust で表現すると次のような動作をします。

pub fn mux(a: bool, b: bool, sel: bool) -> bool {
    if sel { b } else { a }
}

Mux は a, b, sel の3つの入力を持ち、sel の値に応じて a または b を出力します。上のコードは if を使ってズルをした実装になっていますが、これはあとで直すとして、まずはこの mux() を使って BitRegister::clock() の実装を書き換えてみましょう。

impl BitRegister {
    pub fn clock(&mut self, input: bool, load: bool)  {
        // self.flipflop.clock(if load { input } else { self.out() })
        self.flipflop.clock(mux(self.out(), input, load))
    }
}

上の回路図と見比べると、きちんと対応していることが分かるでしょう? これで BitRegister から if を取り除くことが出来ました。あとは mux() の実装のズルを取り除いて、全てNANDの組み合わせで実現できれば完了です。

mux() は次のように書き換えることが出来ます。

pub fn mux(a: bool, b: bool, sel: bool) -> bool {
    // if sel { b } else { a }
    (a && !sel) || (b && sel)
}

あとは &&, ||, ! という3つの論理演算子nand() で表現できればOKです。 どん!答えは下記のとおりです。

pub fn not(a: bool) -> bool {
    nand(a, a)
}

pub fn and(a: bool, b: bool) -> bool {
    not(nand(a, b))
}

pub fn or(a: bool, b: bool) -> bool {
    nand(not(a), not(b))
}

pub fn mux(a: bool, b: bool, sel: bool) -> bool {
    or(and(a, not(sel)), and(b, sel))
}

これで1bitのレジスタの完成です。

それにしても load という入力はどう役に立つのでしょうか? それは後ほどのお楽しみ。

16bit レジスタを作る

16bit を 1 word とするレジスタを作りましょう。まず Word を次のように定義しておきます。

pub type Word = [bool; 16];

[bool; 16] というのは長さ16(固定長)のboolの配列型を意味しています。

ところで、「配列」を使うのはズルではないのでしょうか。我々は if&& すら使ってはいけないプログラミングに取り組んでいます。「配列」は使ってはいけない「高度な」機能ではないのでしょうか。

心配は無用です。16本の導線を束にすれば、ハードウェアで [bool; 16] を実現することが出来ます。もちろん可変長の配列を使うことは出来ませんが(ハードウェアで動的に導線が増減したら怖い)、固定長なら問題ありません。

というわけで、16bit レジスタは下記のコードになります。

pub struct Register { bits: [BitRegister; 16] }
impl Register {
    pub fn new() -> Self {
        Self { bits: [
            BitRegister::new(), BitRegister::new(), BitRegister::new(), BitRegister::new(),
            BitRegister::new(), BitRegister::new(), BitRegister::new(), BitRegister::new(),
            BitRegister::new(), BitRegister::new(), BitRegister::new(), BitRegister::new(),
            BitRegister::new(), BitRegister::new(), BitRegister::new(), BitRegister::new(),
        ] }
    }
    pub fn out(&self) -> Word {
        [ self.bits[ 0].out(), self.bits[ 1].out(), self.bits[ 2].out(), self.bits[ 3].out(),
          self.bits[ 4].out(), self.bits[ 5].out(), self.bits[ 6].out(), self.bits[ 7].out(),
          self.bits[ 8].out(), self.bits[ 9].out(), self.bits[10].out(), self.bits[11].out(),
          self.bits[12].out(), self.bits[13].out(), self.bits[14].out(), self.bits[15].out(),
        ]
    }
    pub fn clock(&mut self, input: Word, load: bool) {
        self.bits[ 0].clock(input[ 0], load);
        self.bits[ 1].clock(input[ 1], load);
        self.bits[ 2].clock(input[ 2], load);
        self.bits[ 3].clock(input[ 3], load);
        self.bits[ 4].clock(input[ 4], load);
        self.bits[ 5].clock(input[ 5], load);
        self.bits[ 6].clock(input[ 6], load);
        self.bits[ 7].clock(input[ 7], load);
        self.bits[ 8].clock(input[ 8], load);
        self.bits[ 9].clock(input[ 9], load);
        self.bits[10].clock(input[10], load);
        self.bits[11].clock(input[11], load);
        self.bits[12].clock(input[12], load);
        self.bits[13].clock(input[13], load);
        self.bits[14].clock(input[14], load);
        self.bits[15].clock(input[15], load);
    }
}

単に BitRegister を16個並べたものが Register です。動作は上のコードを読めばすぐに分かるでしょう。

それにしても Register::clock() の実装、これはひどいですね。for ループ使えや!と言いたくなります。 が、「ハードウェアに for ループはない!」という強い信念の元(?)、あえてループは使わずに実装しました。こうやってベタッと書いたほうが、回路図が透けて見える気がしませんか?

8ワード(16バイト)のRAMを作る

Register を8個並べてRAMを作りましょう。骨組みは下記のようなコードになります。

pub struct RAM8 { registers: [Register; 8] }
impl RAM8 {
    pub fn new() -> Self {
        Self { registers: [
            Register::new(), Register::new(), Register::new(), Register::new(),
            Register::new(), Register::new(), Register::new(), Register::new(),
        ]}
    }
    pub fn out(&self, address: [bool; 3]) -> Word {
        ...
    }
    pub fn clock(&mut self, address: [bool; 3], input: Word, load: bool) {
        ...
    }
}

Register とよく似ていますが、よく見ると out()clock()address: [bool; 3] という引数が新たに加わっています。address は要するに、ポインタです。レジスタは8個ですから、3bit のアドレスで一意に指定することが出来ます。out()address で指定されたアドレスのレジスタを読み取りますし、clock()address で指定されたレジスタの値を書き換えるというわけです。

RAM8::out()

実現したいのはこういう動作です。

impl RAM8 {
    pub fn out(&self, address: [bool; 3]) -> Word {
        match address {
            [false, false, false] => self.registers[0].out(),
            [true,  false, false] => self.registers[1].out(),
            [false, true,  false] => self.registers[2].out(),
            ...
            [true,  true,  true ] => self.registers[7].out(),
        }
    }
}

もちろん match 式は「ズル」ですから、これを使わずに論理回路で分岐を実現しなくてはなりません。 1bit レジスタのときには、if 式を mux() に置き換えたのでした。ここでも mux() を組み合わせて拡張していきます。

まず次のような動作をする mux16() というものを作ります。

pub fn mux16(a: Word, b: Word, sel: bool) -> Word {
    if sel { b } else { a }
}

ほとんど mux() と同じに見えますが、入出力が bool から Word (16bit)に拡張されていることに注意してください。 これは、次のように mux() をひたすら16個ならべることで実装できます。

pub fn mux16(a: Word, b: Word, sel: bool) -> Word {
    [
        mux(a[ 0], b[ 0], sel), mux(a[ 1], b[ 1], sel), mux(a[ 2], b[ 2], sel), mux(a[ 3], b[ 3], sel),
        mux(a[ 4], b[ 4], sel), mux(a[ 5], b[ 5], sel), mux(a[ 6], b[ 6], sel), mux(a[ 7], b[ 7], sel),
        mux(a[ 8], b[ 8], sel), mux(a[ 9], b[ 9], sel), mux(a[10], b[10], sel), mux(a[11], b[11], sel),
        mux(a[12], b[12], sel), mux(a[13], b[13], sel), mux(a[14], b[14], sel), mux(a[15], b[15], sel),
    ]
}

続いて、次のような動作をする mux4way16() というものを作ります。

pub fn mux4way16(a: Word, b: Word, c: Word, d: Word, sel: [bool; 2]) -> Word {
    if sel[1] { mux16(c, d, sel[0]) } else { mux16(a, b, sel[0]) }
    /* 次のコードと等価
    match sel {
        [false, false] => a,
        [true,  false] => b,
        [false, true ] => c,
        [true,  true ] => d,
    }
    */
}

これは下記の実装で実現できることがすぐ分かるでしょう。

pub fn mux4way16(a: Word, b: Word, c: Word, d: Word, sel: [bool; 2]) -> Word {
    mux16(mux16(a, b, sel[0]), mux16(c, d, sel[0]), sel[1])
}

同様にして mux8way16() を作ることが出来ます。

pub fn mux8way16(
    a: Word, b: Word, c: Word, d: Word,
    e: Word, f: Word, g: Word, h: Word,
    sel: [bool; 3]
) -> Word {
    mux16(
        mux4way16(a, b, c, d, [sel[0], sel[1]]),
        mux4way16(e, f, g, h, [sel[0], sel[1]]),
        sel[2]
    )
}

これを使って、RAM8::out() は次のように実装できます。

impl RAM8 {
    pub fn out(&self, address: [bool; 3]) -> Word {
        mux8way16(
            self.registers[0].out(), self.registers[1].out(), self.registers[2].out(), self.registers[3].out(),
            self.registers[4].out(), self.registers[5].out(), self.registers[6].out(), self.registers[7].out(),
            address)
    }
}

以上で、指定された addressレジスタを読み取る回路が作れました。

RAM8::clock()

address からの読み取りは出来ましたから、今度は address への書き込みを実装しましょう。実現したいのはこういう動作です。

impl RAM8 {
    pub fn clock(&mut self, address: [bool; 3], input:Word, load: bool) -> Word {
        match address {
            [false, false, false] => self.registers[0].clock(address, input, load),
            [true,  false, false] => self.registers[1].clock(address, input, load),
            [false, true,  false] => self.registers[2].clock(address, input, load),
            ...
            [true,  true,  true ] => self.registers[7].clock(address, input, load),
        }
    }
}

しかし、ちょっとこれは無理があります。このコードは address の値に応じてクロック信号を入力するレジスタを切り替える書き方になっていますが、クロック信号は常に全ての素子に入力し続けなくてはなりません。

ですので、こんなふうな方針に切り替えます。

impl RAM8 {
    pub fn clock(&mut self, address: [bool; 3], input:Word, load: bool) -> Word {
        let load8: [bool; 8] = match address {
            [false, false, false] => [load, false, false, false, false, false, false, false],
            [true,  false, false] => [false, load, false, false, false, false, false, false],
            [false, true,  false] => [false, false, load, false, false, false, false, false],
            ...
            [true,  true,  true ] => [false, false, false, false, false, false, false, load],
        };
        self.registers[0].clock(input, load8[0]);
        self.registers[1].clock(input, load8[1]);
        self.registers[2].clock(input, load8[2]);
        self.registers[3].clock(input, load8[3]);
        self.registers[4].clock(input, load8[4]);
        self.registers[5].clock(input, load8[5]);
        self.registers[6].clock(input, load8[6]);
        self.registers[7].clock(input, load8[7]);
    }
}

常に全てのレジスタにクロック信号が入力されていることが一目瞭然ですね。 input も常に全てのレジスタに入力されています。

ではどうやって指定された address だけに書き込む制御をしているかというと、ここで load ビットが活躍します。指定された addressレジスタだけ loadtrue を入力することで、この制御をしています。BitRegister で仕込んだ load 入力の伏線を、ようやくここで回収することが出来ました。

では今までと同様に、ifmatch を使っている箇所(load8 を求めている箇所)を論理回路に置き換えていきましょう。

まず DMux (Demultiplexor)という素子を作ります。これは次のような動作をするものです。

pub fn dmux(input: bool, sel: bool) -> [bool; 2] {
    match sel {
        false => [input, false],
        true  => [false, input],
    }
}

これは次のような論理回路で実現できます。

pub fn dmux(input: bool, sel: bool) -> [bool; 2] {
    [and(input, not(sel)), and(input, sel)]
}

これを組み合わせて、次の動作仕様の dmux4way() dmux8way() を作ります。

pub fn dmux4way(input: bool, sel: [bool; 2]) -> [bool; 4] {
    match sel {
        [false, false] => [input, false, false, false],
        [true,  false] => [false, input, false, false],
        [false, true ] => [false, false, input, false],
        [true,  true ] => [false, false, false, input],
    }
}

pub fn dmux8way(input: bool, sel: [bool; 3]) -> [bool; 8] {
    match sel {
        [false, false, false] => [input, false, false, false, false, false, false, false],
        [true,  false, false] => [false, input, false, false, false, false, false, false],
        [false, true,  false] => [false, false, input, false, false, false, false, false],
        ...
        [true,  true,  true ] => [false, false, false, false, false, false, false, input],
    }
}

これらから match 式を除去して論理回路としてどう実装できるか、考えてみて下さい。

これを使うと、RAM8::clock() は次のように実装できます。

impl RAM8 {
    pub fn clock(&mut self, address: [bool; 3], input: Word, load: bool) {
        let load = dmux8way(load, address);
        self.registers[0].clock(input, load[0]);
        self.registers[1].clock(input, load[1]);
        self.registers[2].clock(input, load[2]);
        self.registers[3].clock(input, load[3]);
        self.registers[4].clock(input, load[4]);
        self.registers[5].clock(input, load[5]);
        self.registers[6].clock(input, load[6]);
        self.registers[7].clock(input, load[7]);
    }
}

おわりに

このあとは、RAM8 を8個並べて組み合わせて RAM64 を作り、RAM64 を8個並べて RAM512 を作り…、と続けてRAMを大きくしていきます。

そして、CPUを論理ゲートとレジスタの組み合わせから構成し、CPUとRAMを繋げて、ROMから機械語コードを読み出して実行するようにしていきます。

これが組み上がって動いたとき、何とも言えない感動を覚えたものです。特にレジスタやRAM周りの仕組みにワクワクしました。コンピュータというのは、クロック信号でカチカチと動いていく壮大なピタゴラ装置なんだということが実感できました。

書いたコードはここに置いてあります。ドヤァ! https://github.com/u1roh/nand2tetris

…と思ったら、あれ?これ動かないっすね…。 ディスプレイをシミュレートするところを glium という OpenGL ラッパーで作ったのですが、久しぶりに動かそうとしたら動かない…。

今ちょっと原因を調べる時間も取れないので、すんません、ダサい感じの終わり方になりましたが、以上です。