Haskellでいってみよう

日曜プログラマにも満たないレベルでもHaskellで何かソフトウェアを作りたい!

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

そのまんまだが。。。入力された文字列をtoBitsBinの配列にし、 足りなければ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個を取り出しているがこれには以下が含まれている。

  • carryフラグ(1 bit)
  • Aレジスタ(4 bit)
  • Bレジスタ(4 bit)
  • 出力ポート値(4 bit)
  • プログラムカウンタ(4 bit)

これで"評価ボード"(?)ができた。早速ダミーの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サイクルの最終段階でレジスタを更新(もしくは保持)している。 この部分だけを作ってみよう。前回示したブロック図では一番右端にある部分だ。

f:id:eijian:20160504150006p:plain

コードは以下。

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関係にするか、新しいネタにするか、、、。

(ここまでのソース)