『コンピュータシステムの理論と実装』第5章 CPUを作ったよ

個人的に進めてる『コンピュータシステムの理論と実装』の実装メモを書きますよ。
今回はCPUを作るのが山場でした。

「第5章　コンピュータアーキテクチャ」ではHackコンピュータというこの本オリジナルのコンピュータを作ります。前章まででALU、レジスタやプログラムカウンタなんかは作ってあるので、それらを組合せてなんとかします。

命令メモリ、CPU、データメモリを合体させるとHackコンピュータになるらしい（P.105、5.3.3）。メモリは前章のRAMを利用すればすぐ作れるので、問題はCPUを作ることです。


P.102に概略図が載ってるのでそのとおりに作るんですが、詳細が省かれてるので実際にHDLで書こうとすると大変でした。この本は実践に重きを置いているので、詳細を省いているのはたぶん意図的です。実装を通じて学んで欲しいということでしょう。

下に私の考えた実装コードを載せますけど、本の思想に忠実に自分で考えたいというひとはネタバレ注意です。（GW中にやったけどハマった部分があって3日ぐらいかかってしまったｗ）










HDLコード
nand2tetris/CPU.hdl at master · deltam/nand2tetris

	// 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/05/CPU.hdl
	/**
	* The Central Processing unit (CPU).
	* Consists of an ALU and a set of registers, designed to fetch and
	* execute instructions written in the Hack machine language.
	* In particular, functions as follows:
	* Executes the inputted instruction according to the Hack machine
	* language specification. The D and A in the language specification
	* refer to CPU-resident registers, while M refers to the external
	* memory location addressed by A, i.e. to Memory[A]. The inM input
	* holds the value of this location. If the current instruction needs
	* to write a value to M, the value is placed in outM, the address
	* of the target location is placed in the addressM output, and the
	* writeM control bit is asserted. (When writeM=0, any value may
	* appear in outM). The outM and writeM outputs are combinational:
	* they are affected instantaneously by the execution of the current
	* instruction. The addressM and pc outputs are clocked: although they
	* are affected by the execution of the current instruction, they commit
	* to their new values only in the next time unit. If reset=1 then the
	* CPU jumps to address 0 (i.e. sets pc=0 in next time unit) rather
	* than to the address resulting from executing the current instruction.
	*/
	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 into M?
	addressM[15], // Address in data memory (of M)
	pc[15]; // address of next instruction
	PARTS:
	// Put your code here:
	// decode
	Not(in=instruction[15], out=instA); // 1=A命令
	Not(in=instA, out=instD); // 1=D命令
	// A命令
	And(a=instA, b=instA, out=loadAReg); // 1=ARegisterを書き換える
	// D命令
	And(a=instD, b=instruction[12], out=readMem); // 1=ALUにinMを入力
	// cmp
	Mux(a=instruction[9], b=false, sel=readMem, out=zyALU);
	// dest
	And(a=instD, b=instruction[5], out=saveARegTmp);
	Or(a=saveARegTmp, b=loadAReg, out=saveAReg); // ALU計算結果をAレジスタに保存
	And(a=instD, b=instruction[4], out=saveDReg); // ALU計算結果をDレジスタに保存
	And(a=instD, b=instruction[3], out=saveM); // ALU計算結果をMemory[A]に保存
	// jmp
	And(a=instD, b=instruction[2], out=j1);
	And(a=instD, b=instruction[1], out=j2);
	And(a=instD, b=instruction[0], out=j3);
	// ARegister
	Mux16(a=outALU, b[15]=false, b[0..14]=instruction[0..14], sel=loadAReg, out=toAReg);
	ARegister(in=toAReg, load=saveAReg, out=fromAReg,
	// addressM
	out[15]=false, out[0..14]=addressM);
	// DRegister
	DRegister(in=outALU, load=saveDReg, out=fromDReg);
	// ALU
	Mux16(a=fromAReg, b=inM, sel=readMem, out=toALU);
	ALU(x=fromDReg, y=toALU, zx=instruction[11],
	nx=instruction[10],
	zy=zyALU,
	ny=instruction[8],
	f= instruction[7],
	no=instruction[6],
	zr=zrALU,
	ng=ngALU,
	out=outALU, out=outM);
	// writeM
	And(a=instD, b=saveM, out=writeM);
	// jump condition
	Not(in=ngALU, out=notNgALU);
	Not(in=zrALU, out=notZrALU);
	And(a=notNgALU, b=notZrALU, out=gt); // 0 < outALU
	Not(in=gt, out=notGt);
	// jmp命令のチェック
	DMux8Way(in=true, sel[2]=j1, sel[1]=j2, sel[0]=j3, a=jnull, b=jgt, c=jeq, d=jge, e=jlt, f=jne, g=jle, h=jmp);
	// jnull
	And(a=jnull, b=false, out=jnullVal);
	// jgt
	And(a=notNgALU, b=notZrALU, out=jgt1);
	And(a=jgt, b=gt, out=jgt2);
	And(a=jgt1, b=jgt2, out=jgtVal);
	// jeq
	And(a=notNgALU, b=zrALU, out=jeq1);
	And(a=jeq, b=notGt, out=jeq2);
	And(a=jeq1, b=jeq2, out=jeqVal);
	// jge
	Or(a=gt, b=zrALU, out=jge1);
	And(a=jge, b=notNgALU, out=jge2);
	And(a=jge1, b=jge2, out=jgeVal);
	// jlt
	And(a=ngALU, b=notZrALU, out=jlt1);
	And(a=jlt, b=notGt, out=jlt2);
	And(a=jlt1, b=jlt2, out=jltVal);
	// jne
	Or(a=ngALU, b=gt, out=jne1);
	And(a=jne1, b=notZrALU, out=jne2);
	And(a=jne, b=jne2, out=jneVal);
	// jle
	Or(a=ngALU, b=zrALU, out=jle1);
	And(a=jle, b=notGt, out=jle2);
	And(a=jle1, b=jle2, out=jleVal);
	// jmp
	And(a=jmp, b=true, out=jmpVal);
	// jumpする条件か
	Or8Way(in[0]=jnullVal, in[1]=jgtVal, in[2]=jeqVal, in[3]=jgeVal, in[4]=jltVal, in[5]=jneVal, in[6]=jleVal, in[7]=jmpVal, out=doJump);
	// program counter
	Not(in=doJump, out=doInc);
	PC(in=fromAReg, load=doJump, inc=doInc, reset=reset, out[15]=false, out[0..14]=pc, out[0..14]=pcVal);
	}

view raw CPU.hdl hosted with ❤ by GitHub

苦労したところはジャンプ命令のパースでした。ぜんぶ論理回路でやらないといけないので慣れないとどこから手を付ければいいのか分からないです。
ジャンプ命令パース部分の論理回路を部分的に書いてみました。



まず命令コードのジャンプ命令部分をデマルチプレクサのselに入力して何の命令なのかはっきりさせます（該当するジャンプ命令のビットだけ1が立つ）。
ALUなどの論理回路を作ったときの経験から学んだコツとして"必要な値は最初に全部作っておいて、必要なときに組み合わせる"というのがあります。
ジャンプ命令はALUの出力値の大小によって分岐するので、条件判断に必要な次の値とその否定を全部作っておきます。

• zr − ALUの出力が0と等しい
• ng − ALUの出力が0未満
• gt − ALUの出力が0より大きい（zrとngから作る）

つぎにそれぞれのジャンプ命令に必要な論理回路を作って条件判断させておきます。
最後にデマルチプレクサの出力値とAndして（該当命令の条件判断だけが残る）、全体をORでまとめればジャンプ命令がパースできたことになります。

このロジックというか、考え方を思いつくのに苦労しました。CPU作るのって大変ですねー。



苦労したけど、エミュレータでサンプルコードがちゃんと動くのを確認できたときはかなりの達成感でした。「やったぜ！　俺はコンピュータを作ったぞ！」www


次の第6章はこのHackコンピュータ用のアセンブラを実装します。ここから先はソフトウェアの世界になるので少し楽になるんじゃないかなーと思ってます（コンパイラ、OSの実装とかあるけど）。