nand2tetrisを実装する(4)第3章 順序回路-後編-
前回の続きです。メモリ以降について記述します。
背景
メモリ
第3章にしてメモリを実装していきます。
レジスタでワードを表現できたので、任意の長さのワードを記憶する「メモリ」へ進みます。
レジスタをたくさん積み重ねることで、RAM(Random Access Memory)ユニットを構築することができます。ランダムアクセスメモリの名前の由来は、ランダムに選ばれたワードに対して、そのワードが位置する場所に制限を受けることなく、書き込み/読み込みができることからです。メモリ内のワードは物理的な場所に関係なく同じ場所で直接アスセスできなければなりません。
この要件を満たすために、RAMの各ワードに対して、重複しないユニークな番号をアドレスとして割り当てます。次に、jという数字に対してアドレスがj番目のレジスタを個別に選択できる論理ゲートを構築します。「アドレス」とは、物理的な位置を意味せず、論理的な意味でアドレスを実現します。
・RAMが受け取る3つの入力
- データ入力(in)
- ロードビット(load)
- アドレス入力(address)
アドレス入力によって、現時刻で、RAMのどのレジスタにアスセスするかを指定します。メモリ操作が読み込み(load=0)の場合、選択されたレジスタの値が出力され、書き込み(load=1)の場合、次のサイクルで、選択されたメモリのレジスタの値が送られます。
RAMを設計する場合、基本的なパラメータとして、幅とサイズを指定する必要があります。幅は各ワードの幅で、サイズはRAMに存在するワードの個数です。今回実装する幅は16ビット(のはず)ですが一般的なコンピュータでは、32もしくは64ビット幅のRAM を用います。サイズは100万を超えます。※今回実装するものは約16000(のはず)
レジスタを集合させたものがRAMとなり、このコンピュータの記憶装置となります。
カウンタ(プログラムカウンタ)
プログラムカウンタはレジスタの1種で、次に実行すべき命令を保持する機能を持っています。
カウンタは順序回路であり、タイムユニットが進むごとに、out(t) = out(t-1) + cとなるように、整数が加算されます。(cは通常１が用いられます。)デジタルアーキテクチャ(恐らくコンピュータアーキテクチャの意味)において、カウンタは重要な役割を持ちます。一般的にはCPUにはプログラムカウンタが含まれ、プログラムカウンタの出力は次に実行されるプログラム演算のアドレスとして解釈されます。
カウンタ回路はレジスタに定数を加算することで、実装できます。一般的なカウンタは、追加機能として、カウンタの値をゼロにする・新しいカウンタ値を読み込む・加算の代わりに減算を行うなどの機能を持ちます。
時間
要約していくのが難しかったため、説明が冗長となっています。
本章でこれまで取り上げた回路はすべて順序回路でした。順序回路とは、一つ以上のDFF回路が、直接または、間接的に組み込まれている回路です。また、順序回路の機能(状態を保つ or 状態を操作する)はDFF回路によってもたらされています。技術面の話では、順序回路内のフィードバックループによって先の機能はもたらされます。
一方、組み合わせ回路は、時間という概念はモデル化されていないため、フィードバックループを導入するには問題があります。なぜなら、出力は入力だけに依存しますが、もし入力がその回路自身に依存するとしたら、出力も出力自身に依存することになり、矛盾が生じるからです。対照的に、順序回路は出力を同じ回路の入力に送信することに対しては、問題は生じません。なぜなら、DFFは「時間遅延」という性質を内在するからです。DFFによってt-1の出力がその回路自身に影響をあたえるということです。この性質のおかげで、制御不能の「データレース」(組み合わせ回路でフィードバックループに伴う現象)と呼ばれる現象を防止できます。
組み合わせ回路は、入力値が変われば、その出力値は時間に関係なく変わります。対照的に、順序回路アーキテクチャ内にDFFが組み込まれると、出力値が変わるタイミングは、現在のクロック周期から次のクロック周期に移行した時点で、同じクロック周期では変化しません。順序回路の出力が”離散化”される性質は、思わぬ結果・重要な結果をもたらします。それは、コンピュータアーキテクチャ全体を同期させることができるということです。例えば、ALUにx + yを計算するように指示したとします。ここで、ｘは近くにあるレジスタに格納された値で、yは遠くにあるレジスタに格納された値と仮定します。さまざまなブ地理的規約により、xとyの電気信号がALUまでに到達する時間は異なることになるでしょう。しかし、ALUは組み合わせ回路なので、時間という概念がありません。どのような信号であれ、その入力に入ってきたとしたら、即座にその加算が求められます。そのため、ALUの出力が正しい「x + y」の値に落ち着くには、わずかな時間が必要です。その時間に達するまでALUは”ゴミ”を出力していることになります。
この問題を解決するには、ALUの出力は順序回路を常に通過させることです。これにより、この問題を考える必要は全くありません。作り手がやるべきことは、クロックを作成するときに、クロック周期の間隔を適切に決めるだけです。(アーキテクチャ内で最も距離が遠い回路間を移動するのに必要な時間を調べ、それより少し長い時間を間隔とすることです。)このようにすれば、順序回路が状態を更新するまでにはALUから受け取る値は常に正しいことが保証されます。これにより、それぞれ独立したハードウェアのコンポーネントを、調整が図られたシステムとして同期させることができます。
※これについては5章で詳しく見ていくことにします。
仕様と実装
メモリ
この章では、メモリ幅は16ビットで固定し、サイズの異なるメモリをいくつか組み立てます。
RAM8
この後のRAMを設計するのに、基本となるRAMです。
実装
// 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/RAM8.hdl
/**
* Memory of 8 registers, each 16 bit-wide. Out holds the value
* stored at the memory location specified by address. If load==1, then
* the in value is loaded into the memory location specified by address
* (the loaded value will be emitted to out from the next time step onward).
*/
CHIP RAM8 {
IN in[16], load, address[3];
OUT out[16];
// どのレジスタにアクセスするかをアドレス(address)で選択し、
// そのレジスタに読み込むか、書き込むかを「読み込みビット」(load)
// の値に応じて選択し、書き込みの場合はinの値(word)を次のサイクルで
// そのレジスタに値を入力し、読み込みはoutによって出力される。
PARTS:
// Put your code here:
DMux8Way(in=load,sel=address, a=a,b=b,c=c,d=d,e=e,f=f,g=g,h=h);
Register(in=in,load=a, out=r1);
Register(in=in,load=b, out=r2);
Register(in=in,load=c, out=r3);
Register(in=in,load=d, out=r4);
Register(in=in,load=e, out=r5);
Register(in=in,load=f, out=r6);
Register(in=in,load=g, out=r7);
Register(in=in,load=h, out=r8);
Mux8Way16(a=r1,b=r2,c=r3,d=r4,e=r5,f=r6,g=r7,h=r8, sel=address, out=out);
}
RAM64
RAM8を応用して作ります。
実装
// 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/RAM64.hdl
/**
* Memory of 64 registers, each 16 bit-wide. Out holds the value
* stored at the memory location specified by address. If load==1, then
* the in value is loaded into the memory location specified by address
* (the loaded value will be emitted to out from the next time step onward).
*/
CHIP RAM64 {
IN in[16], load, address[6];
OUT out[16];
// addressの4～６ビット目でどのRAM8を操作するのかを決める。
PARTS:
// Put your code here:
DMux8Way(in=load,sel=address[3..5], a=a,b=b,c=c,d=d,e=e,f=f,g=g,h=h);
// addressの1～3ビット目で各RAM8内のどのRegisterを操作するのかを扱う。
RAM8(in=in,load=a,address=address[0..2], out=r1);
RAM8(in=in,load=b,address=address[0..2], out=r2);
RAM8(in=in,load=c,address=address[0..2], out=r3);
RAM8(in=in,load=d,address=address[0..2], out=r4);
RAM8(in=in,load=e,address=address[0..2], out=r5);
RAM8(in=in,load=f,address=address[0..2], out=r6);
RAM8(in=in,load=g,address=address[0..2], out=r7);
RAM8(in=in,load=h,address=address[0..2], out=r8);
Mux8Way16(a=r1,b=r2,c=r3,d=r4,e=r5,f=r6,g=r7,h=r8, sel=address[3..5], out=out);
}RAM512以降は、RAM64と記述が酷似しているので、コードを省略します。尚、RAM16KだけはRAM4Kとサイズが4倍となっているので、注意してください。
カウンタ
背景で説明されたものを実装します。インクリメンタ・マルチプレクサ・レジスタを使い、実装します。
実装
// 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/PC.hdl
/**
* A 16-bit counter with load and reset control bits.
* if (reset[t] == 1) out[t+1] = 0
* else if (load[t] == 1) out[t+1] = in[t]
* else if (inc[t] == 1) out[t+1] = out[t] + 1 (integer addition)
* else out[t+1] = out[t]
*/
CHIP PC {
IN in[16],load,inc,reset;
OUT out[16];
PARTS:
// Put your code here:
Inc16(in=fb, out=w1); // アドレスの値を加算
Mux16(a=fb,b=w1,sel=inc, out=w2); // inc == 1 ならば加算したアドレスを出力
Mux16(a=w2,b=in,sel=load, out=w3); // load == 1 ならばinの値を出力
Mux16(a=w3,b=false,sel=reset, out=w4); // reset == 1 ならば記憶しているアドレスをリセット
Register(in=w4,load=true, out=out,out=fb); // アドレスを出力し、fbにアドレスを記録
}
