Nand2tetrisを実装する ~ハードウェア編(1 ~ 5章)~
1.はじめに
「コンピュータの中では何が起こっているのか？」
近年、ソフトウェア開発を取り巻く技術は急速に発展し、ほとんどの人にとって、コンピュータの内部構造はブラックボックス化しているのではないでしょうか。かくいう私もその一人。コンピュータの内部構造を知らずとも、「技術の使い方」さえ知っていれば、プロダクションレベルのアプリケーションが実装できてしまう時代です。
しかし、仮にもソフトウェアエンジニアを名乗るのであれば、基本的な構造くらいは理解しておきたいもの。そう思った私は、低レイヤーの勉強のために、書籍「コンピュータシステムの理論と実装」が提供するNand2tetrisというプロジェクトに取り組みました。以下は実装したリポジトリです。
そして、本記事は「コンピュータシステムの理論と実装」の1章から5章に該当するハードウェア編の実装に関する記事です。
2.コンピュータシステムの理論と実装(Nand2tetris)
本章では「コンピュータシステムの理論と実装」という書籍、またその書籍が提供するプロジェクトであるNand2tetrisについて簡単に説明していきます。
本書の目的はコンピュータシステムを実際に作り、その作業を通して、コンピュータシステムを深く理解すること。Nand2tetrisというプロジェクト名はNANDゲートを最小素子として、機械語が動作するようなハードウェアを構築し、アセンブラやコンパイラを実装し、最終的にはテトリスが動作するようなコンピュータを構築するという特徴から名付けられています。
そして、本記事で紹介するハードウェア編では、NANDゲート・Dフリップフロップといったシンプルで単純な回路を組み合わせて、CPUやALUといった複雑な回路をボトムアップに構築していき、最終的には機械語が動作するようなノイマン型コンピュータの実装を行います。
3.ハードウェア編(1 ~ 5章)
3.1.ハードウェア記述言語(HDL)
さて、それではここから、ハードウェアを実装していくわけですが、実装する際は実物の回路を導線で繋ぎ、組み立てていくわけではありません。
デジタル回路の設計をする際に用いられる、ハードウェア記述言語(HDL)を使って、回路の設計・構成を記述します。以下はNand2tetrisが提供するHDLの文法です(ANDゲートの実装)。
CHIP And {
IN a, b;
OUT out;
PARTS:
Nand (a=a,b=b,out=out1);
Not(in=out1,out=out);
}
そして、一般的なHDLと同様、回路に対するシミュレーターも、Nand2tetrisの公式サイトで提供されています.これによって、自分が実装した回路が意図した動作をするかどうかを検証することが可能です。このような開発環境でハードウェアの実装に取り組んでいきました。
3.3.組み合わせ回路の実装
それでは早速、回路の実装に取り組んでいきましょう。といっても、いきなりCPUやコンピュータといった複雑な回路の構築を行うわけではありません。まずはファーストステップとして、Nandゲートを配線し、ORやANDといった比較的シンプルな組み合わせ回路を実装していきます。
さて、具体的な実装に移っていく前に、そもそも「組み合わせ回路」とはなんでしょうか？
組み合わせ回路とは一言で言うと、「状態を持たず、入力によってのみ、出力が決まる回路」です。例としては、AND,ORといった基本的な論理回路、加算器やマルチプレクサといった回路も「状態を持たず、入力によってのみ出力が決まる」という条件を満たしているため、組み合わせ回路に当たります。
そして、当然ですが、Nandゲート自身も「状態を持たず、入力によってのみ、出力が決まる回路」という条件を満たしているため、組み合わせ回路の一つです。ここで、最小素子となるNandゲートを理解するために、入力をX,Y,出力をoutとした下図のようなNandゲートとその真理値表を見てみましょう.
上に示すように、組み合わせ回路は真理値表によって全ての入力パターンとそれに対する出力を示すことが可能です。本書では、ハードウェア実装のファーストステップとして、上の図に示した様なNandゲートから、複数の組み合わせ回路の実装に取り組みます。
実装した組み合わせ回路を一つ一つ説明していたら長くなるので、ここでは一例として、NandゲートとNotゲート(すでに実装済みと想定)によるAndゲートの実装を見てみましょう。
CHIP And {
IN a, b;
OUT out;
PARTS:
Nand (a=a,b=b,out=out1);
Not(in=out1,out=out); // Nandゲートの出力(out1)を反転させる。
}
AndゲートはNandゲートの出力の補集合なので、Nandゲートの出力out1をNotで反転させることによって実装することが可能です。
このようにして、Nandゲートを最小素子とした組み合わせ回路の実装に取り組みました。実装した組み合わせ回路について、詳細には説明しませんが、実装に興味がある方は、リポジトリのnand2tetris/hardware/bool_gate以下のHDLファイル(*.hdl)を見てみてください。
3.4.ALU(算術論理演算器)の実装
前章では複数の組み合わせ回路を実装しました。そして本章では、組み合わせ回路の集大成とも言える算術論理演算器・ALUの実装を行います。
ALUの実装を見ていく前に、ALUに関する説明です。
「ALUとは何か?」についてですが、書籍「コンピュータの構成と設計」(通称・パタヘネ本)には次のように記載されています。
ALU(arithmetic logic unit)はコンピュータの筋肉にあたり、加算や減算などの算術演算やANDやORなどの論理演算を行うものである。
パタヘネ本の説明にもあるとおり、ALUは算術演算・論理演算といった、コンピュータにおけるデータの演算処理を行う非常に重要な回路です。
ここで、今回実装したALUの構造は、簡略化したものではありますが、以下の通りになります。
x,yという16bitの二つの入力に対して、どのような演算を施すか？というのを6bitのALU操作ビット(zx,nx,zy,ny,f,no)によって決定しています。
それでは、HDLによるALUの実装を見てみましょう。
CHIP ALU {
IN
// 16bit input
x[16], y[16],
// 6bit ALU operation
zx, // zero the x input?
nx, // negate the x input?
zy, // zero the y input?
ny, // negate the y input?
f, // compute out = x + y (if 1) or x & y (if 0)
no; // negate the out output?
OUT
out[16], // 16-bit output
zr, // 1 if (out == 0), 0 otherwise
ng; // 1 if (out < 0), 0 otherwise
PARTS:
// out x
Mux16(a=x,b=false,sel=zx,out=outzx);
Not16(in=outzx,out=notoutzx);
Mux16(a=outzx,b=notoutzx,sel=nx,out=outx);
// out y
Mux16(a=y,b=false,sel=zy,out=outzy);
Not16(in=outzy,out=notoutzy);
Mux16(a=outzy,b=notoutzy,sel=ny,out=outy);
// out fx
Add16(a=outx,b=outy,out=addoutxy);
And16(a=outx,b=outy,out=andoutxy);
Mux16(a=andoutxy,b=addoutxy,sel=f,out=outfx);
// out no
Not16(in=outfx,out=notoutfx);
Mux16(a=outfx,b=notoutfx,sel=no,out=outval);
And16(a=outval,b=true,out=out);
// ng
IsNegative16(in=outval,out=ng);
// zr
Or16Way(in=outval,out=notzr);
Not(in=notzr,out=zr);
}
6bit(zx,nx,zy,ny,f,no)のALU操作を表すbitに応じて、X,Y に対して適切な演算を施すような実装がされています。
こちらに関しても実装物がリポジトリのnand2tetris/hardware/aluに存在するので、興味がある方はぜひチェックしてみてください。
3.5.順序回路の実装
前章までで、組み合わせ回路およびALUの実装に取り組みました。ここまでで実装した回路はコンピュータの「演算」という重要な役割を担いますが、「その出力は入力にのみ決定し、回路自体は状態を持たない」、すなわち、「値の記憶ができない」という重大な欠点があります。
そこで、時間が経過してもデータが保持されている記憶素子、順序回路の実装を本章では行います。組み合わせ回路の実装ではNandゲートが最小素子でしたが、本章ではDフリップフロップ(以後,DFF)を最小素子として様々な順序回路の実装に取り組みます。
さて、ここで最小素子となるDFFの仕組みを理解するために、入出力の関係を示しておきます。時刻tにおける出力を
式を見るとわかるとおり、Dフリップフロップは1クロック前の入力(
本章では、DFFを用いて、大きく分けて以下の3つの回路の実装に取り組みました。
- レジスタ
- メモリ
- カウンタ
これらについても実装の詳細はここでは触れませんが、実装物がリポジトリのnand2tetris/hardware/sequential_circuitに存在するので、興味がある方はぜひチェックしてみてください。
3.6.CPU(中央演算処理装置)の実装
それでは、3.4で実装したALUと3.5で実装した複数の順序回路を組み合わせて、中央演算処理装置・CPUを実装していきましょう。
CPUは機械語で書かれたプログラムを実行し、演算処理を行ったり、演算結果のメモリ(RAM)への書き込みを行ったりする、コンピュータにおけるいわば中心的な存在です。
今回実装したCPUは以下のような構造をしています。
ここで入出力をよりわかりやすくするため、簡易化したCPUの図を以下に示します。
それではHDLによる実装を見てみましょう。
CHIP CPU {
IN inM[16], // M value input (M = contents of RAM[A])
instruction[16], // Instruction for execution
reset; // Signals whether to re-start the current
// program (reset==1) or continue executing
// the current program (reset==0).
OUT outM[16], // M value output
writeM, // Write to M?
addressM[15], // Address in data memory (of M)
pc[15]; // address of next instruction
PARTS:
// flag for ARegister
Not(in=instruction[15], out=isA);
Not(in=isA, out=isC);
And(a=isC, b=instruction[5], out=ALUtoA);
// Mux previous ARegister
Mux16(a=ALUout,b=instruction,sel=isA,out=outMu);
// ARegister
Or(a=ALUtoA,b=isA,out=loadA);
ARegister(in=outMu,load=loadA,out=A,out=out);
// Define mnemonic(A or M)
Mux16(a=A,b=inM,sel=instruction[12],out=AM);
// DRegister
And(a=isC, b=instruction[4], out=loadD);
DRegister(in=outMu,load=loadD,out=D);
// ALU
ALU(x=D,y=AM,zx=instruction[11],nx=instruction[10],zy=instruction[9],ny=instruction[8],f=instruction[7],no=instruction[6],out=ALUout,zr=zr,ng=ng);
// outM. not output directly from ALU,because of internal pin
Or16(a=false,b=ALUout,out=outM);
// writeM
And(a=isC,b=instruction[3],out=writeM);
// addressM
Or16(a=false,b=A,out[0..14]=addressM);
// PC
// Calc isPositive
Not(in=zr,out=nZr);
Not(in=ng,out=nNg);
And(a=nZr,b=nNg,out=isPositive);
// JGT
And(a=isPositive,b=instruction[0],out=JGT);
// JEQ
And(a=zr,b=instruction[1],out=JEQ);
// JLT
And(a=ng,b=instruction[2],out=JLT);
// loadPc = JGT || JLT || JEQ
Or(a=JGT,b=JLT,out=JNE);
Or(a=JNE,b=JEQ,out=isJump);
And(a=isC,b=isJump,out=loadPc);
PC(in=A,load=loadPc,inc=true,reset=reset,out[0..14]=pc);
}
以上がCPUの実装になります。
3.7.ノイマン型コンピュータの実装
さて、ハードウェア編の最後ではいよいよノイマン型コンピュータを実装します。ここで実装するノイマン型コンピュータは
- 命令メモリ(ROM・ROM32K):16bitの機械語で書かれた命令を保存したメモリ
- データメモリ(RAM・Memory):プログラムで扱うデータを格納したメモリ
- CPU:中央演算処理装置。3.6で実装。
という既に実装済み(記事では触れていませんが)の3つのパーツを以下のように配線します。
CPUの実装は複雑でしたが、コンピュータの実装は、それを構成するパーツの実装ができていれば非常にシンプルです。それでは、HDLによる実装を見てみましょう。
CHIP Computer {
IN reset;
PARTS:
ROM32K(address=pc,out=instruction);
CPU(inM=inM,instruction=instruction,reset=reset,outM=outM,writeM=writeM,addressM=addressM,pc=pc);
Memory(in=outM,load=writeM,address=addressM,out=inM);
}
以上がノイマン型コンピュータの実装になります。
4.最後に
本記事ではNand2tetrisのハードウェア編(1 ~ 5章)の実装に関する説明を行いました。今回実装したCPU、ノイマン型コンピュータは簡易的なものですが、それでも構成する要素が多く、かなり省略してしまった部分があります。実装の詳細が気になる方はリポジトリのnand2tetris-golang/hardwareをチェックしてみてください。
1 ~ 5章で16bitの機械語が動作するようなハードウェアの実装はできました。しかし、機械語を直接記述するというのは、効率が悪いですし、人間的な作業とも言い難いです。そこで、次の記事では、nand2tetrisが提供するアセンブリを機械語に変換するアセンブラ(nand2tetris-golang/assembler)の実装をGolangで行います。興味がある方はぜひそちらもチェックしてみてください。
5.参考文献
Discussion