CPUの創りかた(9): CPUはじめました
さあ、前回までで必要なモジュールは出揃った。今回はそれらを組み立てて 動くCPUを作ってしまおう! 一気に最終形はしんどいので少しずつピースを埋めていく感じで進めていきたい。
なお、しつこいようだがここで作っているCPUは以下の本で解説されている
TD4という名前のオリジナル4bit CPUだ。説明中にtd4
と出てくるのは
その名前である。
ステップ 0: 電源、クロックジェネレータ(に相当するところ)
これまで論理回路の細かいところやCPU内の各種モジュールを作ることばかり やってきて、実行できるプログラムにする部分には目を瞑っていた。 しかしさすがに今回は「プログラム」を動かしたいのでそうはいかない。
そこでステップ0として完動させるための周辺部分を作っていこう。 電子工作では電源モジュールだとかクロックジェネレータとかその他の アナログ回路部分に相当するだろうか。
まず仕様を列挙しよう。
- 「プログラム」は標準入力から投入する。
- 「プログラム」は'0'と'1'の連続した文字列とする。また間にホワイトスペースが いくつ入ってもよい。
- 「プログラム」におけるビット並びは(慣れているので) MSB...LSB の順とする。
- プログラムカウンタが4 bit なので「プログラム」は16 bytes = 128文字。 ただしそれより少ない場合は'0'で補填する。多い場合は切り捨てる。
- コマンドライン引数は順に"クロック間隔"と"入力ポート"の2つ。省略可能だが、 クロック間隔だけを省略することはできない。
- クロック間隔の単位は秒、小数も使える。デフォルト値は1.0秒。入力ポートは
4桁の二進数でデフォルト値は"0000"。
- 例) td4 0.5 0101 < program
ではこの仕様に基づいて作っていこう。
main :: IO () main = do pg <- getContents opts <- getArgs let (clock, iport) = parseOpts opts putStrLn ("clock " ++ (show clock) ++ " sec; I/P " ++ toStr iport) -- CLR(1),CF(1),A(4),B(4),OP(4),PC(4) let stat = toBits "011000010011000010" loop 0 clock lc_td4 stat iport (createRom pg)
getContents
で標準入力を読み、getArgs
でコマンドライン引数を取り込む。
どちらも標準で用意されている関数だ。parseOpts
でオプションを解析している。
parseOpts
は次の通り。
コマンドライン引数の数に応じてその値を読み込んだりデフォルト値を
使ったりしている。
defClock :: Double defClock = 1.0 -- default clock time = 1 sec defInput :: [Bin] defInput = toBits "0000" -- default value of Input port parseOpts :: [String] -> (Double, [Bin]) parseOpts [] = (defClock, defInput) parseOpts (x:[]) = ((read :: String -> Double) x, defInput) parseOpts (x:y:_) = ((read :: String -> Double) x, toBits y)
次は「プログラム」の整形についてだ。上記仕様ではビットの並びは
MSB...LSBだが、これまで作ってきた論理回路モジュールでは、
入力(Binの配列)が全てLSB...MSBの順だ。そこで前もって順序を入れ替えておこう。
それを行っているのがcreateRom
。
createRom :: String -> [Bin] createRom rs = concat $ map reverse $ split8 rs' where rs' = take 128 (toBits rs ++ repeat sLO) -- 128 bits = 16 bytes
そのまんまだが。。。入力された文字列をtoBits
でBin
の配列にし、
足りなければsLO
(=0)を付け加えて、先頭から16 bytes取り出している。
このような大雑把な記述が可能なのはHaskellの遅延評価のおかげだなぁ。
ちなみにtoBits
は0と1以外の文字は無視するので、間にスペースや
改行があっても問題ない。あとは8 bits単位に切り出してそれぞれを
逆順に並べ替えれば完成だ。
さあ、いよいよCPUモジュールを駆動する(呼び出す)ところだ。これは
「クロックの立ち上がり」のたびに関数を呼び出す無限ループである。
前回までに解説したように状態はCPUの外で管理することにしたので、
入力はCPUの状態+ROMの内容、出力はCPUの最新状態だ。
それをループにしたいのだ。出力値を次の入力値(の一部)に使うので、
再帰呼び出しが良さそうだ。ということで次のようなloop
関数を作ってみた。
loop :: Int -> Double -> LogicCircuit -> [Bin] -> [Bin] -> [Bin] -> IO () loop s w lc st ip pg = do let os = lc (st ++ ip ++ pg) putStatus s os threadDelay $ floor (w * 1000 * 1000) -- set CLR to HI and take status from output let st' = [sHI] ++ (take 17 os) loop (s+1) w lc st' ip pg
クロックの度に状態を画面に出力したいので、ループの数(=ステップ数s
)を
引数の最初に入れている。次はクロック間隔w
、3番目(lc
)がCPUを表す関数
(以後、CPU関数と呼ぼう)だ。
CPU関数への入力は「状態」「入力ポート値」「ROM」の3つ。
関数を呼び出して得た出力を画面に表示(putStatus
)し、クロック間隔だけ待ち
(threadDelay
)、状態を更新して次のステップを呼び出す。この繰り返し。
次回の入力値を作っている少々奇妙な部分について。
let st' = [sHI] ++ (take 17 os)
入力の最初の値が「リセット信号」を表しており、これがLOだとリセットが かかるようになっている。だから一番最初の呼び出し以外はHIにしないといけない。 あと、出力値から先頭の17個を取り出しているがこれには以下が含まれている。
これで"評価ボード"(?)ができた。早速ダミーのCPU関数で動かしてみよう。 中身は何もせず入力を出力に回すだけ。
lc_td4_st0 :: LogicCircuit lc_td4_st0 xs = concat [cf, a, b, op, pc] where [_, cf, a, b, op, pc, _, _] = splitInput xs splitInput :: [Bin] -> [[Bin]] splitInput xs = [cl, cf, a, b, op, pc, ip, rom] where (cl, xs0) = splitAt 1 xs (cf, xs1) = splitAt 1 xs0 (a , xs2) = splitAt 4 xs1 (b , xs3) = splitAt 4 xs2 (op, xs4) = splitAt 4 xs3 (pc, xs5) = splitAt 4 xs4 (ip, rom) = splitAt 4 xs5
splitInput
で分割して必要なものを取り出して並べているだけ。
さあコンパイルして実行してみよう。
$ cabal configure Resolving dependencies... Configuring mkcpu-0.1.0.0... $ cabal build Building mkcpu-0.1.0.0... Preprocessing executable 'td4' for mkcpu-0.1.0.0... [7 of 7] Compiling Main ( src/Main-td4.hs, dist/build/td4/td4-tmp/Main.o ) Linking dist/build/td4/td4 ... $ echo "0000" | dist/build/td4/td4 clock 1.0 sec; I/P 0000 step 0; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 1; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 2; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 3; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 4; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 5; [CF:1][A:0001][B:0010][OP:0011][PC:0100] ^C
レジスタなどの状態が表示されている。ちなみにその適当な値は、
実はmain
の中で指定してある。
-- CLR(1),CF(1),A(4),B(4),OP(4),PC(4) let stat = toBits "011000010011000010" loop 0 clock lc_td4_st0 stat iport (createRom pg)
このstat
だ。A、B、OP、PCの値はそれぞれ1、2、3、4にセットしてあるのだ。
先述の通り一番最初のビットはリセット(CLR)であり、最初だけは'0'に
してある。が、この何もしないダミーCPUではリセット信号が使われないので
Aレジスタなどは初期値が入ったまま(のように見えるの)だ。
兎にも角にも、まずはCPUを駆動する周辺回路に相当する部分は一応 動いたようだ。これを使ってCPUを最終形まで組み立てていこう。
ステップ 1: レジスタの使用
CPUは本来状態を保持したり更新したりして処理を進めていくものだ。 状態はレジスタに保持されているのだが、以前の回で書いたように、CPUの 1サイクルの最終段階でレジスタを更新(もしくは保持)している。 この部分だけを作ってみよう。前回示したブロック図では一番右端にある部分だ。
コードは以下。
lc_td4_st1 :: LogicCircuit lc_td4_st1 xs = concat [cf', a', b', op', pc'] where [cl, cf, a, b, op, pc, _, _] = splitInput xs v0 = toBits "0000" cf' = take 1 $ lc_dff_cp (cl ++ [sHI] ++ cf) a' = lc_register4 (cl ++ [sHI] ++ a ++ v0) b' = lc_register4 (cl ++ [sHI] ++ b ++ v0) op' = lc_register4 (cl ++ [sHI] ++ op ++ v0) pc' = lc_counter4 (cl ++ [sHI] ++ pc ++ v0)
入力を切り出す部分は同じ。v0
はダミー値だ。
フラグやレジスタの入力値をそれぞれレジスタモジュールやカウンタモジュールへ
入れているだけだ。またリセット信号(cl
)もそれぞれに入れている。
実行してみよう。
$ echo "0000" | dist/build/td4/td4 clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0000][B:0000][OP:0000][PC:0001] step 2; [CF:0][A:0000][B:0000][OP:0000][PC:0010] step 3; [CF:0][A:0000][B:0000][OP:0000][PC:0011] step 4; [CF:0][A:0000][B:0000][OP:0000][PC:0100] step 5; [CF:0][A:0000][B:0000][OP:0000][PC:0101] ^C
ステップ0の結果とはだいぶ変わっている。まず、リセット信号が入ったため、 Aレジスタなどの初期入力値は一旦クリアされて0になっているのがわかる。 さらに、ステップが進む毎にプログラムカウンタ(PC)がカウントアップされて いる!カウンタモジュールは前に作ってテストしているから当然こうなるの だが、実行プログラムとしてこの出力になるのはちょっと嬉しい! (CPUが動いているぞ、という感じがする)
ステップ 2: 加算器の追加
次に加算器を取り付けよう。加算器には入力が2つ必要だが、状態を確認する ためにAレジスタの値を使う。もう一方の値はROMから無理やり取り出そう。 ROMにはプログラムカウンタをつないで0番地から順に値を取り出すようにする。 取り出した8bitから下4bitを使ってAレジスタに足し、結果がAレジスタ入るように 配線する。もちろんcarryフラグも更新する。プログラムはこうだ。
lc_td4_st2 :: LogicCircuit lc_td4_st2 xs = concat [cf', a', b', op', pc'] where [cl, _, a, b, op, pc, _, rom] = splitInput xs rdata = lc_rom16 (pc ++ rom) -- get data addressed by PC v0 = toBits "0000" im = take 4 rdata (s0, c0) = splitAt 4 $ lc_adder (a ++ im) cf' = take 1 $ lc_dff_cp (cl ++ [sHI] ++ c0) a' = lc_register4 (cl ++ [sLO] ++ a ++ s0) b' = lc_register4 (cl ++ [sHI] ++ b ++ v0) op' = lc_register4 (cl ++ [sHI] ++ op ++ v0) pc' = lc_counter4 (cl ++ [sHI] ++ pc ++ v0)
4行目でROMの現在番地の値から下4bitを取り出し、5行目(lc_adder
のある行)で
Aレジスタと足しあわせている。それをs0, c0にしてそれぞれAレジスタと
carryフラグへ入れている。
Aレジスタの方は引数の2つ目(レジスタのLD入力)をHIではなくLOにしている。
これは保持している値ではなく外から入った値(s0)をセットするためだ。
プログラム(とは言えないが)は下4桁に加算したい数字を記載している。 上から、1,2,3,4,5,1である。
$ cat program 00000001 00000010 00000011 00000100 00000101 00000001
実行してみよう。
$ dist/build/td4/td4 < program clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0001][B:0000][OP:0000][PC:0001] step 2; [CF:0][A:0011][B:0000][OP:0000][PC:0010] step 3; [CF:0][A:0110][B:0000][OP:0000][PC:0011] step 4; [CF:0][A:1010][B:0000][OP:0000][PC:0100] step 5; [CF:0][A:1111][B:0000][OP:0000][PC:0101] step 6; [CF:1][A:0000][B:0000][OP:0000][PC:0110] ^C
1から5まで足すとAレジスタが最大値の15になり、 そこに1を足せばcarryフラグが立ってAが0になるという寸法だが、CPUの 出力も確かにそうなっているのがわかる。
ちなみに、ここまでスラスラ進んでいるように書いているが、実際は 入力値の区切り位置を間違っていたり、入力と出力のパラメータの順序を 間違っていたりして、何度も出力が予想外になってバグ取りが大変だった。 実際の電子工作では「配線間違い」に相当するのだろうか。。。
ステップ3の前に(オペランドの選択)
いよいよ全体を組み上げるわけだが、その前に加算器への入力(ブロック図の 左側に並ぶA,Bレジスタと入力ポート値、および0)を切り替える部分を考えよう。 これには以前作ったmultiplexerが使える。入力値は4bitなので、multiplexerを 4つ、入力値の各桁用に並べればよい。
selectInput :: [Bin] -> [Bin] -> [Bin] -> [Bin] -> [Bin] -> [Bin] selectInput s a b ip z = concat $ map (\x -> lc_multiplexer4ch (s ++ x)) mi where mi = buildMultiplexerInput [a, b, ip, z] buildMultiplexerInput :: [[Bin]] -> [[Bin]] buildMultiplexerInput xs = map (\i -> pickBit i xs) [0..3] pickBit :: Int -> [[Bin]] -> [Bin] pickBit i xs = map (!!i) xs
最初の引数sでどの入力値を使うかを指定する。あとは入力値の各桁を 集めてきてmultiplexerへ入れてやれば、sが選択する入力値を出力してくれる。 テストは以下。うまくいっているようだ。
>>> let a = toBits "1000" >>> let b = toBits "0110" >>> let ip = toBits "0001" >>> toStr $ selectInput [sLO, sLO] a b ip zero "1000" >>> toStr $ selectInput [sHI, sLO] a b ip zero "0110" >>> toStr $ selectInput [sLO, sHI] a b ip zero "0001" >>> toStr $ selectInput [sHI, sHI] a b ip zero "0000"
いよいよ最後の組み立てを残すのみ。
ステップ 3: CPUの組み立て
さあ、最終段階にきた。ROMから読み込んだ命令を命令デコーダへ入れ、 入力値を選択し、加算器を通して結果をどこに書き出すかを 命令デコーダに指示させればよいのだ。以下が最終のCPUのコードだ。
lc_td4 :: LogicCircuit lc_td4 xs = concat [cf', a', b', op', pc'] where [cl, cf, a, b, op, pc, ip, rom] = splitInput xs rdata = lc_rom16 (pc ++ rom) (im, inst) = splitAt 4 rdata [sa, sb, ld0, ld1, ld2, ld3] = lc_inst_decorder (inst ++ cf) (s0, c0) = splitAt 4 $ lc_adder ((selectInput [sa, sb] a b ip zero) ++ im) cf' = take 1 $ lc_dff_cp (cl ++ [sHI] ++ c0) a' = lc_register4 (cl ++ [ld0] ++ a ++ s0) b' = lc_register4 (cl ++ [ld1] ++ b ++ s0) op' = lc_register4 (cl ++ [ld2] ++ op ++ s0) pc' = lc_counter4 (cl ++ [ld3] ++ pc ++ s0)
ROMから取り出した命令をデコーダに入れ、その結果を加算器と各レジスタへ つないでいる。ステップ2との差はそれぐらいだが、これで完成だ。意外と あっけなく出来上がった。
さすがに各命令の処理をテストしておく必要があるだろう。以下がテスト用 コードの一部だ(ADD A,Im と MOV A,B)。 具体的な命令コードを与え結果を想定と比較する、これまで作ってきた 論理回路モジュールと同じだ。
>>> let rom0 = take ((16-1) * 8) $ repeat '0' >>> -- ADD A,Im (A=1, Im=4 -> A=5, CF=0) >>> toStr $ lc_td4 $ toBits ("10 1000 0000 0000 0000 0000 00100000" ++ rom0) "01010000000001000" >>> -- ADD A,Im (A=13, Im=4 -> A=1, CF=1) >>> toStr $ lc_td4 $ toBits ("10 1011 0000 0000 0000 0000 00100000" ++ rom0) "11000000000001000" >>> -- MOV A,B (A=13, B=3 -> A=3) >>> toStr $ lc_td4 $ toBits ("10 1011 1100 0000 0000 0000 00001000" ++ rom0) "01100110000001000"
さあ、実際にプログラムを走らせてみよう! 本に記載されているラーメンタイマーを実行してみよう。うまくいけば、 下記のように出力ポートが変化するはずだ。
[0111] -> [0110] -> [0100](点滅) -> [1000]
本には"ニーモニック"しか書いていないのでハンドアセンブルした結果が これ。
10110111 00000001 11100001 00000001 11100011 10110110 00000001 11100110 00000001 11101000 10110000 10110100 00000001 11101010 10111000 11111111
これをファイル(program.ramen)に書いてtd4に食わせればよい。
$ dist/build/td4/td4 < program.ramen clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0000][B:0000][OP:0111][PC:0001] step 2; [CF:0][A:0001][B:0000][OP:0111][PC:0010] : step 31; [CF:0][A:1111][B:0000][OP:0111][PC:0001] step 32; [CF:1][A:0000][B:0000][OP:0111][PC:0010] step 33; [CF:0][A:0000][B:0000][OP:0111][PC:0011] : step 63; [CF:0][A:1111][B:0000][OP:0111][PC:0011] step 64; [CF:1][A:0000][B:0000][OP:0111][PC:0100] step 65; [CF:0][A:0000][B:0000][OP:0111][PC:0101] step 66; [CF:0][A:0000][B:0000][OP:0110][PC:0110] : step 96; [CF:0][A:1111][B:0000][OP:0110][PC:0110] step 97; [CF:1][A:0000][B:0000][OP:0110][PC:0111] step 98; [CF:0][A:0000][B:0000][OP:0110][PC:1000] : step 128; [CF:0][A:1111][B:0000][OP:0110][PC:1000] step 129; [CF:1][A:0000][B:0000][OP:0110][PC:1001] step 130; [CF:0][A:0000][B:0000][OP:0110][PC:1010] step 131; [CF:0][A:0000][B:0000][OP:0000][PC:1011] step 132; [CF:0][A:0000][B:0000][OP:0100][PC:1100] : step 192; [CF:0][A:1111][B:0000][OP:0100][PC:1100] step 193; [CF:1][A:0000][B:0000][OP:0100][PC:1101] step 194; [CF:0][A:0000][B:0000][OP:0100][PC:1110] step 195; [CF:0][A:0000][B:0000][OP:1000][PC:1111] :
命令種やビット数に制限があり正確に3分とはいかないが、ちゃんと想定したとおりの 動きをしているようだ。これだけでも意外にうれしいものだ!
まとめ
やっとCPUが完成した!機能的にはかなり低レベルではあるが、本当に 論理回路の組み合わせだけでCPUという複雑な仕組みが成り立っていて 動くのを確認できた。最初に考え出した人は本当にすごい!
ところで、今回のプログラミングは「Haskellならでは」というのがあまり
なかったなあと思う。論理的な処理は論理ゲートとその配線で決まるので、
Haskellらしさは「配線」に相当する処理ぐらいだ(複数の配線を
map
で一括処理するとか)。それもあってか、プログラミング的には
淡々と並べただけに終わった気もする。Haskellのもっと高度な
機能を使えば、今よりエレガントな記述ができるのかもしれないが、それは
もっと"使える"ようになってから考えよう。
さてこの先だが、
- 8bit化: レジスタや加算器で1bitの部品を4個から8個に増やせばよい。 プログラム的には繰り返し回数を増やすだけなのでかなり簡単なはず。
- 加算以外の命令: 本にも記載があるが本格的なALUを用意すればもっと いろいろできることが増える。
- i4004の製作: 回路図がわかれば今回と同様になんでも製作できそうだ (山のように時間があれば)。ならば実在する有名どころを作ってみるのも 楽しそう。
などは手がつけられそうだ。こういった拡張は頭で考えるだけでも楽しいものだ。
次回だが、このネタのおまけで何かCPU関係にするか、新しいネタにするか、、、。
(ここまでのソース)
CPUの創りかた(8): すべては足し算だった
CPUの製作もいよいよゴールが近づいてきた。残る主要な部品は 命令デコーダ(instruction decorder)のみ。その前にCPUの全体構造を 確認しておきたい。そうすれば命令デコーダをどう作ればいいかがよく 分かると思う。次に命令デコーダを考えよう。
CPUのブロック図と命令デコーダ
CPU(TD4)を入力、処理、出力に分けて考えると次のようなブロック図に なると思う。
この図では、入力値(入力ポート(I/P)、A,Bレジスタ、直値)は加算器 (adder)に入り、結果は全て加算器から出てきて出力ポート(O/P)やレジスタの いずれかへ書き込まれるような構成になっている。 前回作った加算器では、入力は二つの4 bit値、出力は一つの4 bit値とcarry フラグだった。ということは、加算器に入れる値をいくつかの候補から選択する 必要がある。それが図のSelector INだ。 一方、加算結果を書き出す先も選択する必要があるが、これはSelector OUTの 仕事だ。
では、どれを足してどこに結果を書くかはどう決まるのかというと、もちろん 命令(operation code)で決まるわけだ。ここまでくると命令デコーダの やっていることが見えてくる。このCPU(TD4)においては、 「命令を解釈して、どの値を足して、どこへ書き出すかを決める」 ということをやっているわけだ。ROMから命令デコーダへ入っている矢印が 「命令」を、命令デコーダからSelector IN/OUTへ伸びている矢印が どれを選択するかを表す情報というわけだ。
すべては足し算
さて、上記の図と説明を見て「あれ?」と思っただろうか? そう、TD4の構造では全ての命令(処理)は加算器を通る。それはつまり「足し算しか できない」ということだ。しかしCPUの処理というものは、代入とかポートの 入出力とか、ジャンプとかいろいろあるわけで、それはどこへ行ったんだ、 となる。
これについては例の本(CPUの創りかた)を読むとよくわかる。一見全く別の 命令に見えたものが、実は「全部足し算で表現できる」のだ。次の表を 参照してほしい。これは命令コード(opcode)とニーモニック、それに 対応する足し算を並べたものだ。
opcode | mnemonic | equation |
---|---|---|
0000xxxx | ADD A,Im | A ← A + Im |
00010000 | MOV A,B | A ← B + 0000 |
00100000 | IN A | A ← I/P + 0000 |
0011xxxx | MOV A,Im | A ← 0000 + Im |
01000000 | MOV B,A | B ← A + 0000 |
0101xxxx | ADD B,Im | B ← B + Im |
01100000 | IN B | B ← I/P + 0000 |
0111xxxx | MOV B,Im | B ← 0000 + Im |
10010000 | OUT B | O/P ← B + 0000 |
1011xxxx | OUT Im | O/P ← 0000 + Im |
1110xxxx | JNC Im | PC ← 0000 + Im (cf=0) |
1111xxxx | JMP Im | PC ← 0000 + Im |
確かに全部足し算で表現できている!恥ずかしながら、今までCPUの内部でこういう処理を しているとは知らなかった。。。代入は足し算を使って(片方を0にして) 実現しており、出力ポートへの書き出しとは書き込む先がポートになっている、 ただの代入だ。ジャンプは飛び先アドレスをPCへ代入しているだけだ。
式中のプラス記号の左と右を比べてほしい。プラス記号の左側はSelector INから 来るもの、右側はROMから直接入ってくるものだ。左側には図に書かれていない '0000'もある。これも実際に作るときにはSelector INの入力の一つと してつくり込む必要がある。一方、右側は直値(Im)か0だ。それをどうやって 使い分けているか、は簡単だ。命令コードの下4 bitがそれで、 0を入れる時は命令コードの下4 bitが0なのだ。
もちろん一般のCPUはもっと複雑な構造をしているので、 こんな単純に全部足し算で処理しているのではなく、ALU内で複雑な処理を しているのだろう。とはいえそれも、加算器とか乗算器とか、論理演算 などを処理する部分にどういったものを入力するか、それらから出てくる 結果をどこへ書き出すかを命令デコーダが選択すればよいのだろうから、 大差無いだろう。
「命令を解釈する」と言われると、なんとなく神秘的でとても高度なことを しているというイメージがあったのだが。 今回の製作でその辺のカラクリが見えたのは収穫だ。 (知っている人にとっては当たり前すぎて、バカバカしいと思われるだろうが)
命令デコーダ
では、最後の大物(?)にとりかかろう。先述の通り、このCPUの命令デコーダは 「命令を解釈してSelector IN/OUTを適切に制御する」ものだ。 ではSelectr IN/OUTは何者かということになる。まあ本に書いてあることだが、
- Selector IN: 4chマルチプレクサを4 bit分並べたもの。一つのマルチプレクサで 1 bit分が選択できるので4つ必要。
- Selector OUT: どのレジスタやポート(実体はFlip Flop)の
Load
を有効に するかを指定する。実体があるわけではなく命令デコーダの一部と言える。 (わかりやすくするためSelector OUTと表現しているが)
ということだ。結局命令デコーダは、Selector IN/OUTに必要な 「選択するための情報」を作り出せばいいのだ。
さて、命令デコーダの入力は命令コード(上4 bit、OP0-OP3)とcarryフラグ(CF)だ。 Select INへは(SA、SBの)2 bit、4種類の情報を与えてやれば良い。 Selector OUTについては、4つある出力先(Flip Flop)のどれか一つの'Load'を 有効に、それ以外を無効にする必要があるので、4 bitの情報で表す(LD0-LD3)。 まとめると、入力は5 bit(OP0-OP3,CF)、出力が6 bit(SA,SB,LD0-LD3)だ。
SA,SBの値と、選択される入力値の対応は下表のとおり。
SA | SB | input |
---|---|---|
0 | 0 | A register |
1 | 0 | B register |
0 | 1 | input port |
1 | 1 | value '0000' |
LD0-LD3と出力先の対応は下表のとおり。
LOAD | output |
---|---|
LD0 | A register |
LD1 | B register |
LD2 | output port |
LD3 | program counter |
これらを踏まえ入出力を真理値表にまとめたものがp.242にある。さらに カルノー図などで分析した結果、各出力は次のように表現できる。
非常に簡潔になった、素晴らしい。もちろん偶然ではなく、この本の著者は こういう単純な回路になるように綿密に考えて、命令コードを割り振っているわけだ。 ここまでくればコードに落とすのは簡単だ。
{- | instruction decorder IN : [OP0,OP1,OP2,OP3,CF] OUT: [SA,SB,LD0,LD1,LD2,LD3] OPn: operation code (upper 4 bit) CF : carry flag SA : Select A SB : Select B LDn: LOAD0 - LOAD3 -} lc_inst_decorder :: LogicCircuit lc_inst_decorder (op0:op1:op2:op3:c:_) = [sa, sb, l0, l1, l2, l3] where sa = op0 |> op3 sb = op1 nop0 = (!>) op0 nop2 = (!>) op2 nop3 = (!>) op3 l0 = op2 |> op3 l1 = nop2 |> op3 l2 = op2 |> nop3 l3 = nop2 |> nop3 |> (nop0 &> c)
なんと命令デコーダの小さいことか!わずか12行だ!
各opcodeについてテストを書いてみる。
>>> toStr $ lc_inst_decorder $ toBits "00000" -- ADD A,Im "000111" >>> toStr $ lc_inst_decorder $ toBits "10000" -- MOV A,B "100111" >>> toStr $ lc_inst_decorder $ toBits "01000" -- IN A "010111" >>> toStr $ lc_inst_decorder $ toBits "11000" -- MOV A,Im "110111" >>> toStr $ lc_inst_decorder $ toBits "00100" -- MOV B,A "001011" >>> toStr $ lc_inst_decorder $ toBits "10100" -- ADD B,Im "101011" >>> toStr $ lc_inst_decorder $ toBits "01100" -- IN B "011011" >>> toStr $ lc_inst_decorder $ toBits "11100" -- MOV B,Im "111011" >>> toStr $ lc_inst_decorder $ toBits "10010" -- OUT B "101101" >>> toStr $ lc_inst_decorder $ toBits "11010" -- OUT Im "111101" >>> toStr $ lc_inst_decorder $ toBits "01110" -- JNC(C=0) Im "111110" >>> toStr $ lc_inst_decorder $ toBits "01111" -- JNC(C=1) Im "111111" >>> toStr $ lc_inst_decorder $ toBits "11110" -- JMP Im "111110"
ちゃんとテストも全部通る。これは嬉しい。 (本の真理値表とはビット順序がいくらか違っているので混乱しないように)
さあ、部品が出揃った!いよいよCPUとして全体を組み上げる頃合いだ! が、続きは次回。
まとめ
今回は最後の重要なモジュールである命令デコーダを作った。 次回はCPUを組み上げて簡単な命令の実行を試そう。うまく動くかな?
(ここまでのソース)
CPUの創りかた(7): 加算器を作る
今回はCPUの中でも「純粋に」計算するところ、加算器を作ろう。ALUを作る!と 行きたいところだが、残念ながらTD4(しつこいようだが下記の本で実装されるCPU) では加算器しかないので今の所は諦めよう。
1 bit 全加算器
ものの本では半加算器から説明されるようだが、どうせ使わないので 最初から全加算器を作る。まずは1 bitから。
入力は、2つの値$A$と$B$、あとくり上がり$C_i$(carry)の3つ、出力は加算の結果 $S$と上の桁へのくり上がり$C$だ。
真理値表は次のようになるだろう。以下の説明では従来のHI、LOの代わりに 1と0を使うことにする。
$A$ | $B$ | $C_i$ | $S$ | $C$ |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 0 |
1 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
例によって、これをSとCについてそれぞれカルノー図を描いて考えると、 最終的に以下のように表される(面倒なので途中の計算は省略する)。
コードはこの式をそのまま表してみた。
{- | 1 bit full adder IN : [Ci,A,B] OUT: [S,C] Ci : carry in A,B : value S : answer C : carry out -} lc_adder1 :: LogicCircuit lc_adder1 (ci:a:b:_) = [s, c] where a_xor_b = a <+> b s = ci <+> a_xor_b c = (a &> b) |> (ci &> a_xor_b)
全加算器は大した回路ではないので、テストもすんなりと通った。
>>> lc_adder1 [sLO, sLO, sLO] == [sLO, sLO] True >>> lc_adder1 [sLO, sLO, sHI] == [sHI, sLO] True >>> lc_adder1 [sLO, sHI, sLO] == [sHI, sLO] True >>> lc_adder1 [sLO, sHI, sHI] == [sLO, sHI] True >>> lc_adder1 [sHI, sLO, sLO] == [sHI, sLO] True >>> lc_adder1 [sHI, sLO, sHI] == [sLO, sHI] True >>> lc_adder1 [sHI, sHI, sLO] == [sLO, sHI] True >>> lc_adder1 [sHI, sHI, sHI] == [sHI, sHI] True
4 bit 加算器
1 bit 全加算器ができたので、これを数珠つなぎにすれば$n$ bitの加算器を 作ることができる。本CPU(TD4)はレジスタが4 bitなので4 bit 加算器を作ろう。 言わずもがなだが、全加算器を次のようにつなげれば良い。入力$A_n$、$B_n$ および$C_i$、出力が$S_n$と$C$だ。
よって、先に作った全加算器(lc_adder1
)をこの図のとおりにつなげて
計算すればよいのだが、数珠つなぎだからこれは再帰で表現できそうだ。
まず再帰処理の本体から考える。入力は$n$ bitの$A$と$B$だが、それらの同じ桁の
値を組にしたリストを用意しよう。これを順に加算器に入れ、各桁の結果$S_i$を
求めたい。大雑把には次の通り。
[(a0,b0), (a1,b1), ... , (an,bn)] → [s0,s1, ... , sn]
ただし、くり上がり(carry)があるので少々複雑になる。くり上がりも含め
計算するために、その桁に足し込みたいcarryも引数で与える。さらに、
計算結果$S$を次に渡していくので、これも引数にする。これらを踏まえると、
つぎのような関数adder_n
ができる。
{- IN : Ci, [Si], [(Ai,Bi)] OUT: [Si,C] Ci : carry in Ai, Bi: value Si : Answer C : carry out -} adder_n :: Bin -> [Bin] -> [(Bin, Bin)] -> [Bin] adder_n ci ss [] = [ci] ++ ss adder_n ci ss ((a, b):ds) = adder_n c (s:ss) ds where [s, c] = lc_adder1 [ci, a, b]
$A$と$B$の各桁の組のリストを先頭から一組取り出して、
carryと合わせて加算する。残りのリストと計算結果を使ってadder_n
を
呼出す(再帰)。処理するリストがなくなったら、$S$の前に最後の
くり上がりを追加して終わり。この関数では「最後の桁」が先頭に来るから、
出来上がった$S$のリストは逆順にしないといけない。加算器の出力は、
$S_n$,$C$の順にしたいので、再帰の終端で最後のくり上がりを「先頭に追加」
したわけだ。逆順にしたら最後になるように。結局出力は以下のようになる。
[s0,s1, ... , sn, c]
あとは、このadder_n
を呼び出す「外側」の関数を作れば良い。
lc_adder
とする。
{- | n bit full adder IN : [A,B] OUT: [S,C] A,B : value S : answer C : carry out -} lc_adder :: LogicCircuit lc_adder ds = reverse $ adder_n sLO [] $ zip a b where l2 = length ds `div` 2 a = take l2 ds b = drop l2 ds
加算器のビット数を明示的に与えていないことに注意。ビット数は、 入力(リスト)の長さの半分とした。$A_n$と$B_n$が繋がったリストで入力される 前提だ(4 bitなら要素は8個のはず)。奇数個だったら余りは無視される。 これで$n$ bit加算器の完成だ。テストも上々だ(長くなるので割愛)。
まとめ
今回は少々軽めの内容だったが、「一番計算機らしい回路」と言えなくもない(?) 加算器を作った。先述の通りこのCPUは加算器しか持たないので乗算器などに 手は出さないが、将来CPUをパワーアップするとしたら要検討かもしれない。
これでCPUで必要となる論理回路のモジュールがほぼ出揃った。あと残すは 「本丸」の命令デコーダのみだ。だが次回はその前にCPUの全体構成を 確認したいと思う。その方が命令デコーダの作り方がよく分かるとおもうから。
(ここまでのソース)
CPUの創りかた(6): プログラムカウンタ
前回はレジスタを作ったが、その流れでプログラムカウンタを作ろう。 なぜ「その流れ」かというと、プログラムカウンタはレジスタに少し 手を加えたものだからだ (ということを知ったのは最近なので偉そうなことは言えないが)。
便利な二項演算子
プログラムカウンタの前に一つ。
今更感たっぷりだが、これまで論理演算はlc_and
とかlc_or
など
論理ゲートの処理をする関数で記述してきた。これらの関数は多入力に
対応し結果もリストで返すので、複雑な論理回路の関数(lc_decorder
とか)
との整合性が取りやすかった([Bin]
を取り[Bin]
を返すから)。
しかしlc_and
など関数名が長く、ビット値をいちいちリストに変換
しないといけないため、論理式が判別しにくく長くなってしまう欠点がある。
(例) d' = lc_and ([c] ++ lc_or (lc_not [p] ++ [d])) x2' = lc_nand ([sHI] ++ x1' ++ x3)
パッと見てどんな論理式かさっぱりだ。そこでよりすっきり書けるよう、 二項演算子を定義しよう。ついでに優先度も。ちなみにNOTは単項演算子だが 気にしない。 (それにしても、すでに他で使われておらず、わかりやすくて短い演算子を 考えるのはなかなか難しい)
-- NOT (!>) :: Bin -> Bin (!>) a = head $ lc_not [a] -- AND (&>) :: Bin -> Bin -> Bin a &> b = head $ lc_and [a, b] -- OR (|>) :: Bin -> Bin -> Bin a |> b = head $ lc_or [a, b] -- NAND (!&>) :: Bin -> Bin -> Bin a !&> b = head $ lc_nand [a, b] -- NOR (!|>) :: Bin -> Bin -> Bin a !|> b = head $ lc_nor [a, b] -- XOR (<+>) :: Bin -> Bin -> Bin a <+> b = head $ lc_xor [a, b] infixr 8 !> infixr 7 &> infixr 7 !&> infixr 6 |> infixr 6 !|> infixr 6 <+>
これらを使うと、先の例は次のようにすっきり。
(before) d' = lc_and ([c] ++ lc_or (lc_not [p] ++ [d])) (after ) d' = c &> ((!>) p |> d) (before) x2' = lc_nand ([sHI] ++ x1' ++ x3) (after ) x2' = (!>) (sHI &> x1' &> x3)
記述量と視認性がかなりあがった! (・・・と思う) ただし例の2つ目は、NANDがANDとNOTに代わっている。NANDの場合、二項演算子を 組み合わせても3入力NANDにならないから。。。
命令の実行とクロック(立ち上がり)のタイミング
プログラムカウンタの前にもう一つ。
この記事はコードを少しずつ作りながらその状況を書いているのだが、 それでも全体構成だとか、先々のロジックとかもちらほら考えながら 進めている。その時にどうしても腑に落ちなかったのが、 「プログラムのワンステップは電子回路のどこから始めてどこで終わるのか」 ということだった。
全体の流れは、1命令について「入力があって、命令の処理をして、出力をして」 というのを繰り返すのだろうが、はじめにCPUのどの構成部品に入力値を 放り込んで処理を進めていくのか、というところで混乱していた。 (文字で書くとなかなか説明しづらいのだが)
だが、どうすればいいか最近やっとわかった。要は、クロックのタイミングに ついて完全に誤解していたのだ。レジスタはクロックの直後に更新される、 でもクロックが処理の発端だよねぇ、と悩んでいたわけだ。
以下に、一つの命令(ワンクロック命令とする)の処理について、これまで 想像していた流れと実際の流れを示す。 (クロック=クロックの立ち上がり、結果出力=レジスタ更新など)
* これまでの想像 [クロック] => (フェッチ) => (デコード) => (実行) => (結果出力) * 実際の流れ (フェッチ) => (デコード) => (実行) => [クロック] => (結果出力)
というわけで、一つの命令はほとんど最後まで処理されて最後の「締め」の ためにクロックを待っているのだ。クロックの瞬間に結果が固定される。 さらに(個人的に)驚きなのは、レジスタ値が更新されてめでたしめでたし と思っていたら、勝手に次の命令をどんどん処理していて結果も出ていて、 あとはレジスタなどへの書き込み待ち、というところまでノンストップで 進めてしまっていること。。。
コンピュータやCPUに詳しい方には至極当然のことだろうが、うーん、 この歳になって目から鱗だった。
プログラムカウンタ
本題に入ろう。CPUの構成要素にプログラムカウンタ(以後PCとする)がある。これは、 次に実行する命令の番地を記憶しておく場所だ。普通、命令が一つ実行されると PCが1(もしくは命令長に応じた分だけ)カウントアップされる。次の命令を 指すようになるわけだ。 ちなみにジャンプ(分岐)命令は、PCの値を強制的に別の値(番地)に変更するもの。
さて、PCに必要な機能は次の通り。(ちなみにTD4の命令は全て1バイト)
- 命令が実行される(=クロックが入る)と次の番地を指す
- 外から番地を指定することもできる
一方で前回作ったレジスタはどうだったかというと、
- クロックが入ると前の値を保持し続ける
- 外から値を指定することもできる
という動作をする。つまりPCとは、「保持する値がクロックのたびに1ずつ 増えていくレジスタ」であることがわかる。こうなればどのように作れば良いか 見えてくる。
1ずつ増えていくのだから、入力に対し1増えた値を出力すればよい。 4 bitのPCの場合、入力を$A_n$、出力を$Q_n$とすると真理値表は次の通り。 数を強調するため、HI/LOではなく1/0で表す。なお、これまでと同じく $A_0$($Q_0$)がLSB、$A_3$($Q_3$)がMSBとする。
$A_3$ | $A_2$ | $A_1$ | $A_0$ | $Q_3$ | $Q_2$ | $Q_1$ | $Q_0$ |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
この表から、各$Q_n$を$A_n$で表せばいいわけだ。カルノー図を描いて ごにょごにょ式変形すると、結果として下記の式を得る。
ちなみに$\oplus$は排他的論理和(XOR)だ。これを使わずAND/ORで構成している 回路図もあったが、XORを使うほうがすっきりして解りやすいと思う。 最初の回で作った論理ゲートにXORは無いので、以下の通り追加しよう。 ただし他のゲートと違い、このXORゲートは2入力に限定する。 ついでに二項演算子も定義。
lc_xor :: LogicCircuit lc_xor (a:b:_) = [(a &> b') |> (b &> a')] where a' = (!>) a b' = (!>) b (<+>) :: Bin -> Bin -> Bin a <+> b = head $ lc_xor [a, b] infixr 6 <+>
さて、先に書いたようにPCとレジスタはかなり似ている。 繰り返しになるが、レジスタだと「前の(同じ)値を記憶する」ところを 「値が1増える」ようにすればPCになるのだ。であれば、レジスタの入力の ところにちょっと追加してやって「次の値」が入るようにすればいい。 前の値からどのように作るかは上記の$Q_n$の式のとおりだ。というわけで、 PCの回路図は次の通りとなるだろう。
ラッキーなことに(?)、Flip Flopの回で書いたように順序回路の「記憶」は
関数の外で管理することにした。出力値を次の入力に回すことにした、というアレ。
だから、出力された値をそのまま次の入力に回す代わりに、「ちょっといじった値」
にして入力してやれば、レジスタ(関数lc_register4
)がそのまま使える
ということだ!
なのでPCは簡単に作れてしまった・・・。
{- | Program Counter (4 bit) IN : [!CLR,!LD,A0,A1,A2,A3,B0,B1,B2,B3] OUT: [Q0,Q1,Q2,Q3] An: current count value Bn: count value set by outer Qn: next count value -} lc_counter4 :: LogicCircuit lc_counter4 (c:l:ds) = lc_register4 ([c, l, d0, d1, d2, d3] ++ b) where bw = 4 [a0, a1, a2, a3] = take bw ds b = take bw $ drop bw ds d0 = (!>) a0 d1 = a1 <+> a0 d2 = a2 <+> (a1 &> a0) d3 = a3 <+> (a2 &> a1 &> a0)
テストをするとちゃんと1つカウントアップした値が出てくる! 論理回路とは、げに不思議なものだ(笑)。
まとめ
今回で「記憶」に関わる部分はあらかた出来上がったと思う (キャリーフラグが残っているが、単なるD-FFだし)。 次回からいよいよ計算(命令)のロジックに入ろうと思う。
(ここまでのソース)
CPUの創りかた(5): 4 bitレジスタ
今回は、前回作ったD Flip Flop(以下D-FF)を使ってレジスタを作ろう。 対象のCPU(TD4)は4 bitのレジスタを2つ持っている。これを実装したいわけだ。
1 bitレジスタ
最初から複雑なものを作るのは大変なので、まず簡単なところから1 bitレジスタを 考えることにする。今回作るレジスタの基本構造は次の通り。
レジスタは基本的に値を保持し続けるものだ。しかし前回作ったD-FFはクロックの 立ち上がり時点の入力値がそのまま出てくるだけだ。 だからD-FFの出力をぐるりと回してきて入力に戻してやる。そうすれば、 クロックが入るたびに出てきたものをまた入力するので同じ値がぐるぐる回る、 というわけだ(入力A)。
でもそれだけだと値が変わらず何の役にも立たないので、外からの入力値(入力B)も 受け入れられるようにする。その値と保持している値のどちらを新しい値とするかを スイッチで切り替えるのだ。スイッチには、以前作ったMultiplexerが使える。
なお、前回のD-FFは出力値を強制的にHIにセットするPR入力と反転した出力 $\overline{Q}$を持っているが、使わないので割愛する(PRには常にHI(無効)を 入力、出力は$Q$だけ取り出す)。早速コードにしてみよう。
-- c: !CLR -- l: !LD (LO -> select a, HI -> select b) -- a,b: input value (A and B) lc_register1 :: LogicCircuit lc_register1 (c:l:a:b:_) = take 1 $ lc_dff_cp ([c, sHI] ++ d) where d = lc_multiplexer2ch [l, a, b]
リセットしたい時はCLRをLOにする。LDは負論理なのでHIのときは値を保持(Aを採用)、 LOで外からの入力値をセット(Bを採用)だ。前回書いたように、値を内部的に 保持することはせず、回路の外で管理することにした。なので保持したい値 (上記ではA)を毎回入力してやる必要があるのだ。
テストコードは以下。
>>> lc_register1 [sLO, sLO, sHI, sHI] == [sLO] -- clear True >>> lc_register1 [sHI, sHI, sHI, sLO] == [sHI] -- select A True >>> lc_register1 [sHI, sHI, sLO, sHI] == [sLO] -- select A True >>> lc_register1 [sHI, sLO, sHI, sLO] == [sLO] -- select B True >>> lc_register1 [sHI, sLO, sLO, sHI] == [sHI] -- select B True
4 bitレジスタ
1 bitレジスタができれば4 bitも簡単だ。4つ並べればよい。ただし、CLRと LDは4つの1 bitレジスタで共通に使う。早速コードにしてみよう。
lc_register4 :: LogicCircuit lc_register4 (c:l:ds) where a = take 4 ds b = take 4 $ drop 4 ds procReg1 :: Bin -> Bin -> (Bin, Bin) -> [Bin] procReg1 c l (a, b) = lc_register1 [c, l, a, b]
入力データ部分(ds
)から、4 bitずつ2つの値A,Bを取り出している。
A,Bのリストから同じ桁の要素を組みにして先の1 bitレジスタに入れている
だけだ。とてもシンプルだ。
下記のような簡単なテストもしてみた。大丈夫そう。
>>> let d0 = toBits "0000" >>> let d1 = toBits "1111" >>> let d2 = toBits "0101" >>> let d3 = toBits "0011" >>> lc_register4 ([sLO, sLO] ++ d1 ++ d2) == d0 -- when CLR = ON True >>> lc_register4 ([sLO, sHI] ++ d1 ++ d2) == d0 -- when CLR = ON True >>> lc_register4 ([sHI, sHI] ++ d1 ++ d2) == d1 -- when LD = OFF True >>> lc_register4 ([sHI, sLO] ++ d1 ++ d2) == d2 -- when LD = ON True
CLRをLOにすればレジスタはリセットされるので入力によらず出力は"0000"。 HIにすればLDのOFF/ONによって、現在値Aか新規入力値Bが選択されている。
D-FFさえ用意してあれば、なんともあっけないものだ :-)
$n$ bitレジスタ
さて、先の4 bitレジスタのコードをあらためて見てみると'4'が散見される。 このようなマジックナンバーはいただけない。定数にしてまとめたらどうか? いや、このコードであれば別に4に限定する必要すらなさそうだ。ならばビット数を 引数で与えてやれば汎用的になるのではないか?
lc_register :: Int -> LogicCircuit lc_register w (c:l:ds) = concat $ map (procReg1 c l) $ zip a b where a = take w ds b = take w $ drop w ds procReg1 :: Bin -> Bin -> (Bin, Bin) -> [Bin] procReg1 c l (a, b) = lc_register1 [c, l, a, b]
これなら4 bitと言わず、8 bitでも64 bitでも行けそうだ!今回は使い道がないが…。
これを使って先のlc_register4
を置き換えよう(部分適用だな)。
lc_register4 :: LogicCircuit lc_register4 = lc_register 4
さっきと同じテストを実行し、エラーがないことを確認。
ところで引数のw
はビット数を表すが、チェックしなくていいのだろうか?
これまでは面倒くさいので目をつむっていたが、やはり入力値チェックは
しておいたほうがいいのだろうなと思う。さてw
の条件は何だろう?
ビット数だから1以上?でも内部で1 bitレジスタを呼んでいるから2以上で
ないと意味がない?
1だと無駄はあるが、結果は正しいので許容できる。0だと結果は0個=空リストに
なってしまうが、これはこれでありかもしれないと思い始めた。さすがに負の
ビット数はないので、w
は0以上にしよう。となると入力データのサイズも
気になる。現状値と新規入力値が必要なのでビット数x2だ。これらの条件を
満たさないならどうするか?HaskellならMaybe
型で返すのが真っ当な気がする。
が、あとあと大変な予感がするので、へなちょこながらとりあえず今の所は
error
で逃げることにする。
lc_register w (c:l:ds) | w < 0 = error ("bit width is invalid (" ++ show w ++ ")") | len < w * 2 = error ("no enough input (" ++ show len ++ ")") | otherwise = concat $ map (procReg1 c l) $ zip a b where len = length ds :
これで、入力値がまともでなければ処理が「止まる」。まあシステムがPANICを 起こしたと考えればいいか。
まとめ
前回のD-FFを用いてレジスタが準備できた。「状態」は別途管理しないと 行けないので完璧とは言えないが、まあよしとしよう。
次は何にするか? 加算器あたりかな?
(ここまでのソースはこちら)
CPUの創りかた(4): Flip Flop
今回こそ、CPU本体の製作に入ろう。本「CPUの創りかた」では、ROMの次に レジスタを作る流れになっている。
ただ、いきなりレジスタはしんどいので、今回はその手前のFlip Flopの話だ。
Flip Flopと状態保持
Flip Flopは順序回路の一つらしいが、状態を記憶することができるらしい (習った気はするがとっくに忘れた)。 だから「レジスタ」は値を保持できるというわけだ。
ではHaskellで「状態を記憶する」にはどうしたらいいのか? オブジェクト指向言語であれば、オブジェクト内に状態を持つなんてのは 普通にできるので簡単だが、Haskellである。「状態」って無いのでは?無理?
調べると、HaskellにはStateモナドなるものがあり、これを使うと何かできそうな 匂いはする。が、解説を読んでもちっともわからないのであきらめた。 仕方がないので全ての「状態」は外で管理することにしてしまおう。 ROMの時と同じく、毎回「状態」も入力し、出力には「状態」を含める。 その「状態」を次の入力にする。 面倒だがそうすることで「状態」は管理できるだろう。
という方針(?)に基づき、Flip Flopを作っていく。
S-R Flip Flop
まずは基本中の基本(?)のS-R Flip Flop(以下、SR-FFとする)から。 Flip Flopについては「CPUの創りかた」にも多少説明はあるのだがいまいち ピンとこない。もう少し詳しいことが知りたかったのでこの本も買った。
これによると、SR-FFの回路図は次のとおりである。
回路自体は単純だが、出力($Q$、$\overline{Q}$)がフィードバックしているところを
どう処置するかである。ただ、上述の通り今回は「状態」を関数などの内部に持たず
毎回入力するので、それほど悩まなくてもいいかもしれない。
なお、コード中では$\overline{Q}$のように上線が書けないため、'
で
代用している。
{- | SR-FlipFlop IN : [S,R,Q,!Q] OUT: [Q,!Q] -} lc_srff :: LogicCircuit lc_srff (s:r:q0:q0':_) = [q, q'] where q_ = head $ lc_nand [s, q0'] q' = head $ lc_nand [r, q_] q = head $ lc_nand [s, q']
一旦、$Q$について仮の出力を得て、それを$\overline{Q}$の方に回して
それを得る。
さらにそれを入力として、あらためて$Q$を得るわけだ。なおソース中の
q'
は$\overline{Q}$である。ちなみにこのSR-FFは負論理だ(セット/リセットの
時は$S$、$R$をLOにする)。
SR-FFの真理値表は次のようである。
$S$ | $R$ | $Q$ | $\overline{Q}$ | remarks |
---|---|---|---|---|
L | L | - | - | 禁止 |
L | H | H | L | セット |
H | L | L | H | リセット |
H | H | ? | ? | 変化しない |
幾つかのWebサイトで真理値表を確認したが、$S$と$R$を両方LOにするのは 「禁止」らしい。 実際にそうしたらどうなるか回路図で追いかけてみたら、$Q$も$\overline{Q}$も HIになり$Q=\overline{Q}$となってわけがわからなくなるようだ。 だが上記コードでは$S$、$R$ともにLOが入力されたらエラーとはせず、 回路図の通り$Q$も$\overline{Q}$もHIを出力することにした。入力・出力を どう扱うかは使う人が対応することだ(自分だが…・)。
以下はdoctestのコードだ。
>>> lc_srff [sLO, sLO, sLO, sLO] == [sHI,sHI] True >>> lc_srff [sLO, sHI, sHI, sLO] == [sHI,sLO] True >>> lc_srff [sHI, sLO, sHI, sLO] == [sLO,sHI] True >>> lc_srff [sHI, sHI, sHI, sLO] == [sHI,sLO] True >>> lc_srff [sHI, sHI, sLO, sHI] == [sLO,sHI] True -- あってはいけない(Q=!Q)状態を入力 >>> lc_srff [sHI, sHI, sLO, sLO] == [sHI,sLO] True >>> lc_srff [sHI, sHI, sHI, sHI] == [sLO,sHI] True
最後に、ここで作ったSR-FFの真理値表を示す。テストコードの最後の二つも 本来あってはいけないものだが、なんとなく値を返しているのはコードでの 処理の仕方によるものなので物理的な回路とは異なるかもしれないがご愛嬌。
$S$ | $R$ | old $Q$ | old $\overline{Q}$ | new $Q$ | new $\overline{Q}$ |
---|---|---|---|---|---|
L | L | ? | ? | H | H |
L | H | ? | ? | H | L |
H | L | ? | ? | L | H |
H | H | L | H | L | H |
H | H | H | L | H | L |
H | H | L | L | H | L |
H | H | H | H | L | H |
('?'はLO/HIどちらでもよいという意味)
エッジトリガ式 D Flip Flop
解説書などではS-Rの次は同期式S-RとかJK Flip Flopとか色々話が続くのだが、 どうやらCPUで実際に使われるのは「エッジトリガ式 D Flip Flop」だそうだ。 これは、clockの立ち上がり(or 立ち下がり)の瞬間の$D$の値を保持するらしい。 エッジトリガ式D Flip-Flopは長いので以後D-FFとし、値はクロックの 立ち上がり時に変化することとする。
ということで、D-FFはクロックの立ち上がり時の$D$の値を保持する=出力するの だから、真理値表は次のようになるだろう。
$D$ | $Q$ | $\overline{Q}$ |
---|---|---|
L | L | H |
H | H | L |
なんと単純な!これなら超簡単にコードにできる。
lc_dff :: LogicCircuit lc_dff (d:_) = [d, not d]
テストはこう。
>>> lc_dff [sLO] == [sLO,sHI] True >>> lc_dff [sHI] == [sHI,sLO] True
テストもちゃんと通る! 難関と思っていたD-FFがいとも簡単に実装できてしまった! いやいやいやいや、そういうわけにはいかない。これだと以前のdecorderと同じだ。 ここはやはり、ちゃんと論理回路をコードで表現して結果を得ないと。
D-FFの回路として、先の本(ゼロから学ぶディジタル論理回路)に記載されている 6NAND型 D Flip-Flopを採用しよう。回路図は以下の通り。
これをコードにしたいわけだがここで問題がある。クロックの立ち上がりなので $C$=HIであるから、$X_1$は$X_0$がわからないと決まらない。$X_0$は$X_1$と $X_3$が決まらないとわからない。ということで、結局入力$D$がHIかLOか 分かっていても$X_n$を決められない。さてどうするか。
今回、論理回路を表す関数はその呼出しの瞬間がクロックの立ち上がりと決めた。 であれば、その「直前」はクロック入力$C$=LOということだ。 そう考えて上の回路図を見直すと、$C$=LOだから$X_1$と$X_2$はHIと決まる。 $X_3$は$D$と$X_2$から決まる。$X_0$も$X_1$と$X_3$から決まるわけだ。 これで直前の状態が決まった。
次に$C$=HIとして各値を求めよう。すでに$X_n$は求めているからそれを使えば 新しい$X_1$と$X_2$が得られる。回路図の右半分はSR-FFそのままだから そいつに入力してやればよい。。。いや、本当にそうか? $\overline{S}$と$\overline{R}$がともにHIだったら「現状維持」となり、 そのためには「現状」がわからないとやっぱりダメだ。
うーん、とりあえずどういう状態になるか調べてみることにする。 $D$と$X_n$の真理値表を書いてみた。クロックの立ち上がり前後があれば わかりやすいので$C$もつけた。
$D$ | $C$ | $X_0$ | $X_1$ | $X_2$ | $X_3$ |
---|---|---|---|---|---|
L | L | L | H | H | H |
L | H | L | H | L | H |
H | L | H | H | H | L |
H | H | H | L | H | L |
$D$がLOのときにクロックが立ち上がる前と後の$X_n$を並べた。 SR-FFの入力は、$S=X_1$、$R=X_2$であるから、クロックの立ち上がり ($C$=HI)時のそれぞれの値を見てみると、$D$がHIでもLOでも $X_1=\overline{X_2}$である。であればSR-FFへの入力は常に値のセットもしくは リセットとなるため、過去の状態に関わらず必ず$Q$と$\overline{Q}$が 決まることになる!悩む必要はないわけだ。
上記を踏まえてコードに落としてみたのが以下。
lc_dff :: LogicCircuit lc_dff (d:_) = lc_srff (x1' ++ x2' ++ [sLO, sHI]) where -- before rising (C = LO) x1 = [sHI] -- because C = LO x2 = [sHI] -- because C = LO x3 = lc_nand (d ++ x2) x0 = lc_nand (x1 ++ x3) -- rising edge (C = HI) x1' = lc_nand ([sHI] ++ x0) x2' = lc_nand ([sHI] ++ x1' ++ x3)
先の論理回路を使わない方をlc_dff'
と改名して比較テスト。
>>> lc_dff [sLO] == lc_dff' [sLO] True >>> lc_dff [sHI] == lc_dff' [sHI] True
ちゃんとテストも通る!
ClearとPresetの追加
さて、D-FFを実際に使うとしたらClear()やPreset()ができないと だめだろう。特にClearはシステムの起動時のリセット処理で必要となる。 ということで、次のようなモジュールにしよう。ClearとPresetは ともに負論理とする。
このようなモジュールが入ったICもあるようだが、その論理回路はややこしい みたいなので勝手に仕様を決めてしまうことにする。
- Clearしたいときは=LOにする。その時はPresetや$D$の値によらず $Q$はLOにする。
- Presetしたいときは=HIかつ=LOにする。その時は$D$の値によらず $Q$はHIにする。
- ==HIなら、$D$の値を$Q$に出力する。
これを満足するように、、$D$の3つの値から、新たに$D'$を作ろう。 D-FFなので結果的に$D'=Q$である。上の仕様を真理値表にすると以下のようになる。 '?'はHI/LO両方を表す。
$D$ | $D’$(=$Q$) | ||
---|---|---|---|
L | ? | ? | L |
H | L | ? | H |
H | H | L | L |
H | H | H | H |
これを論理回路にしよう。、、$D$の3入力から$D’$を得る式を検討する。 結論を書くと次のようになる。ちなみに(超単純ではあるが)カルノー図を描いたのは 20年ぶりぐらいかな?
これを踏まえ、、付きのD-FFを次のように定義しよう。
lc_dff_cp :: LogicCircuit lc_dff_cp (c:p:d:_) = lc_dff d' where d' = lc_and ([c] ++ lc_or (lc_not [p] ++ [d]))
まあ、そのまんまなんだが。ついでにテストは以下。うまく動いているようだ。
>>> lc_dff_cp [sLO, sLO, sLO] == [sLO,sHI] True >>> lc_dff_cp [sLO, sLO, sHI] == [sLO,sHI] True >>> lc_dff_cp [sLO, sHI, sLO] == [sLO,sHI] True >>> lc_dff_cp [sLO, sHI, sHI] == [sLO,sHI] True >>> lc_dff_cp [sHI, sLO, sLO] == [sHI,sLO] True >>> lc_dff_cp [sHI, sLO, sHI] == [sHI,sLO] True >>> lc_dff_cp [sHI, sHI, sLO] == [sLO,sHI] True >>> lc_dff_cp [sHI, sHI, sHI] == [sHI,sLO] True
これで、やっとレジスタに使えるD-FFが得られた。
まとめ
今回はFlip Flop、特にCPUで使うエッジトリガ式D Flip Flopを作った。 次回はこれを多数並べて、いよいよレジスタを作ることにしよう。
(ここまでのソースはこちら)
CPUの創りかた(3): ROMをつくる
今回はROMをつくろう。ROMと言っても本(CPUの創りかた)ではディップスイッチで 代用している。つまり論理回路ではない。ということで、ここでも論理回路の シミュレーションは諦め(笑)、単純にHIかLOを出すような関数を作ろうと思う。
まずはROMの概要的な回路図を示す。今回つくっていく各関数がどこに当たるかも コメントしておく。
ROMモジュールの入出力
まずはこのROMモジュールの入力と出力を決めよう。ROMに対しては取り出したい アドレス(番地)を指定したらいいだろう。このROMは16 bytesなので0番地から 15番地まである。これを二進数で指定するため、4 bit分の入力値が必要だ。 これを下位の桁からA0,A1,A2,A3とする。
ところでROMの内容はどこに存在するのだろう?物理的なディップスイッチであれば、 スイッチを一つ一つカチカチやっていけばいいが、今回はどうしたものか。 "ROM"ということなら、haskellソース中に定数として定義してもいいのだが、 それだと「プログラム」を変更するのに毎回コンパイルし直さないといけないので 格好悪すぎる。実行時に読み込ませるようにしたい。それではRAMじゃないか というツッコミがあるかもしれないが、一度読み込んだら実行中に更新できない のでやっぱりROMだ。
読み込んだものを保管しておき、ROMモジュール内部でそれを参照する手も あるが、今回はROMモジュールへの入力として毎回指定する形にしたい。 これは、後でつくる"レジスタ"も同様だが、CPUの「状態」をモジュールの外で 管理しておこうと考えているからだ。 それが良い方法なのかどうかは疑問だが、あまりいい手が思い浮かばないので。
ということで、16 bytes分のROMデータも入力にする。0番地の最下位bit(D00)から 順に、15番地の最上位bit(Df7)までの128 bit(Dxxの2桁目が番地、3桁目が1 byte 中の位置)。もし入力が16 bytesに満たなかったら"LO"を補填して16 bytesになる ようにする。
出力はというと、これは簡単だ。A0-A3で指定した番地のROMの値(1 byte分)が モジュールから出てくる。Y0,Y1,..Y7だ。こちらも最下位bitから始まることに 注意する。
番地の指定
まずROMモジュールの中心となる関数lc_rom16
を示そう。
lc_rom16 :: LogicCircuit lc_rom16 xs = lc_not $ concat $ map (\x -> mergeBits x omem) [0..7] where adr = lc_decorder4 $ take 4 xs mem = split8 $ take (8*16) ((drop 4 xs) ++ repeat sLO) omem = map toSwitch (zip adr mem) -- out of switches (16 bytes)
先の回路図とこの関数中で使われているサブ関数を対応させながら
何をやっているか書いてみる。このモジュールの入力は、番地を指定する
4 bitと、ROMデータ128 bitの計132 bit分のBinのリストである。
まずは番地指定とROMデータとを分解する。番地は先頭の4要素であるから、
take 4 xs
で取り出せる。これにさらに前回作ったdecorder(4 bit)を
適用すれば、16要素のリストを得る。この中身は、指定した番地に該当する
要素だけがLO、他はHIとなるのだった(前回参照)。それが下記の部分だ。
adr = lc_decorder4 $ take 4 xs
回路図では左端の部分がこれにあたる。
ROMデータの整形
次は、後の処理をしやすくするため128 bitのROMデータを整形しよう。 具体的には、128 bitに足りない分を補填し、8 bit毎に区切った16要素の リストにする。
- まずROMデータだけを取り出す(
drop 4 xs
)。 - さらにその後ろに「無限に続くLO」を補填する(
++ repeat sLO
)。 - 続けて先頭から128個を取り出す(
take (8*16) ...
)。 - 最後に8個ずつに切り分けて16要素のリストにする(
split8 ...
)。
なお、split8
は次のように定義した。
split8 :: [Bin] -> [[Bin]] split8 [] = [] split8 xs |length xs < 8 = [take 8 (xs ++ repeat sLO)] |otherwise = l:(split8 ls) where l = take 8 xs ls = drop 8 xs
split8
内でも、念のため入力が8 bitに満たないときは後ろにLOを補填するように
している。これでROMデータを16番地分の"bytes列"に分けることができた。
各ディップスイッチからの出力
ディップスイッチの構造は8個の物理的スイッチの集まりと言える。 スイッチONで導通、OFFで不通だ。出力側をHIにぐとしたら、入力値と スイッチの状態との組み合わせは4パターンあるが、各パターンの出力は 下図の通りである。
これで分かるように、LOを入力した時だけスイッチの状態が出力されると いうことだ。アドレスの指定はdecorderを経て16個の出力になり、そのうち一つ だけがLO、あとはHIになるのだった。そう、これによりLOになった線につながる スイッチの出力「だけが有効」になるわけだ。
そのためdecorderの各出力線と各番地を結びつけるのだが、その処理は 次の部分だ。
omem = map toSwitch (zip adr mem) -- output from switches (16 bytes)
zip
により出力線と番地を組み合わせ、toSwitch
へ放り込んでいる。
その実装は次の通り。
toSwitch :: (Bin, [Bin]) -> [Bin] toSwitch (a, ms) = lc_dipswitch (a:ms) lc_dipswitch :: LogicCircuit lc_dipswitch (a:xs) | a == sHI = take 8 $ repeat sHI | a == sLO = take 8 ((lc_not xs) ++ repeat sHI)
単にタプルをリストに構成しなおしてスイッチlc_dipswitch
へ入力しているだけ。
回路図では真ん中の四角が縦に並んでいるところがこれにあたる。
スイッチlc_dipswitch
の処理は、最初の入力値(decorderからくる情報)によって
二種類に分かれている。HIの時はスイッチの状態(=ROMデータ)は無視して8 bit
全部がHIになる。LOの時は番地の情報を"反転"させて出している。後ろに
repeat sHI
が続いているが、これは入力が8個に満たなかった時の備えである。
普通HIを1、LOを0などで表すが、スイッチは導通がON、普通がOFFであり、
導通時にLOになるような回路にしたのだ。一方で関数lc_dipswitch
に与える
ROMデータは一般的な1=HI、0=LOとした。だから途中で反転させる必要がある。
出力値の統合
さて問題は各ディップスイッチからの出力を最終的にROMモジュールの 出力にするところだ。指定した番地のスイッチからは設定されたROMの 値が(反転して)出てくるが、他のスイッチからは全部HIの値が出てくる。 欲しいスイッチの出力だけを出力につなげられればいいが、そういうわけ にもいかない。例の本の回路図では単に全スイッチの同じbit位置の 出力を統合している(黒丸で示されている)。これは実際にはどのような値に なるのか考えてみる。
統合する出力線は16本だ。全てがHIならHIを出せば良い。しかし取り出したい 番地のスイッチからはHI/LOのどちらかが出てくる。この値は「そのまま」 取り出したい。だから16本のうち一つでも(一つしかないはずだが)LOなら LO、全部HIならHIが出るようにするようにしたい。そういう論理ゲートといえば、 ANDだ!
各スイッチからの出力の同じbit位置を取り出してANDでまとめる処理を
mergeBits
とした。回路図のスイッチの右側の部分である。
実装は次の通り。
mergeBits :: Int -> [[Bin]] -> [Bin] mergeBits n ms = lc_and $ map (!!n) ms
第一引数がbit位置(0から7)、第二引数は全番地からの出力のリスト(16 bytes分)。
map
でリストから始定位置の値を取り出すので、結果は16要素のリストになる。
これをlc_and
でまとめるわけだ。
最終結果!
最後は統合された値を正論理に戻してあげればよい。回路図のいちばん右の 部分に相当する。これはディップスイッチが負論理(?)であるからだ。 以下の部分だ。
lc_not $ concat $ map (\x -> mergeBits x omem) [0..7]
さあ、これでほしい番地のROMデータ値が取り出せる! 少しテストしてみたが、今の所思った通りに動いているようだ。
まとめ
今回はCPUというかコンピュータを構成する主要な要素であるROMを作った。 そうか、まだ本当にはCPUを創っていないのだ!というわけで、 次回はレジスタ‥の前段階のflip flop回路を考えてみようと思う。
※ ここまでのソースはGitHubに。