DeepLearning(1): まずは順伝播(上)
さて、今回からは新たなネタとしてDeepLearningに取り組もう。 DeepLearningといえばすでにブームは去って、今は現実の課題に どんどん活用されている状況だ。使いやすく性能のいいツールや ライブラリがいろいろあり、ちょっと学べば簡単にその恩恵に 与ることができる(かもしれない)。
しかし、仕組みがわからないのをただ使うのは面白くないし 個人的に写真の自動分類をしたいというニーズもあるし、遅まきながら 自分で作ってみよう、というわけだ。
目標と参考資料
最終的には「一般物体認識」まで行きたい(というかそうでないと 写真の分類にならない)が、目標が高すぎると頓挫するのでここでは 以下の2つのステップまでとする。
「自分で作ってみよう」と大口を叩いていながら他の方の実装を写経する とは詐欺的だが、そこは当方素人なので。。。以後、yusugomoriさんのpython実装を 「yusugomori実装」と表記する。
作るのは、畳み込みニューラルネットワーク(Convolutional Neural Network, CNN)による画像認識プログラムとする。以下、参考にした書籍や Webサイトを列挙。
- 書籍
- Deep Learning with Java : yusugomoriさんの書籍、日本語版が9月に出る予定
- 深層学習 : 専門的な本、最初に買ったが予備知識なしではかなり難しかった
- 機械学習と深層学習 ―C言語によるシミュレーション : 具体的な実装のための理解には役立つ
- 初めてのデーィプラーニング : 理論の大枠をざっと理解するにはよかった
- Webサイト
ひとつの本やWebサイトだけでは理解が進まないので、多数に目を通して同じ概念を いろいろな説明で読むほうがよいと思う。
まずは型を考える
(ちゃんと理解できているとは言い難いが)CNNによる画像認識は 次の図のように「画像」を各層で変換していって最終的に分類結果 (どれに該当するかを確率で示す)を得るようだ。
そこでまずは「画像(Image)」型と「層(Layer)」型を定義しよう。
カラー画像だと、$X \times Y$二次元のドットで構成された平面(Plain)が
赤緑青の3色(チャネルとする)集まってできている。一般の画像ファイル
では各ドットを0-255の整数で表すことが多いが、CNNでは強さを実数で表すようだ。
畳み込み層の変換後のデータも多チャンネルの「画像」とみなせそうなので、
Image
は次のように定義した。実体はDouble
の3次元リストだ。
(Image.hs) type Plain = [[Double]] -- 2D: X x Y pixels type Image = [Plain] -- n channel
わざわざImage
をPlain
のリストにしたのは、Plain
ごとに処理することが
多そうだからだ。
あとついでに、「学習」の際に必要となる教師データも定義しておく。
(Image.hs) type Class = [Double] -- trainer vector type Trainer = (Image, Class)
実数のリストだが、教師データは要素のどれか一つが1.0、他が0.0となる。
次にレイヤを考える。CNNでは次のようなレイヤが使用される。
- 畳み込み層 (convolution layer)
- プーリング層 (pooling layer)
- 活性化層/活性化関数 (activation layer)
- 全結合層 (fully connected layer)
このうち、活性化層というのは一般的な表現かどうかよくわからない。
最初は型クラスとしてLayer
を定義し各層を型としてやればいいと考えた。
が、各層をつなげて一連の変換処理を表現するのに「リスト」を使いたかったので
(私の知識範囲では)うまい方法が思いつかなかった。
ということで、Layer
型を次のように代数データ型で定義することにした。
(LayerType.hs) data Layer = NopLayer | ConvLayer Int [FilterC] | MaxPoolLayer Int | ActLayer ActFunc | HiddenLayer [FilterH] | FlattenLayer (Image -> Image)
NopLayer
は何も変換しないダミーの層(テスト用)、
プーリング層は実用上Max Poolingだけでよいと考えてMaxPoolLayer
、
全結合層は隠れ層ということでHiddenLayer
としている。
各行に出てくる引数の型はそれぞれ以下のように定義してある。
ActFunc
は活性化関数、FilterC
は畳み込み層のためのフィルタ、
FilterH
は全結合層(隠れ層)のためのフィルタ、をそれぞれ表す型だ。
(LayerType.hs) -- for Activation Layer type ActFunc = [Double] -> [Double] -- filter for Convolution Layer type Kernel = [[Double]] type Bias = Double type FilterC = (Kernel, Bias) -- filter for Hidden Layer type FilterH = [Double]
学習用プログラム
deep learningで画像認識させるためのステップは大雑把には以下の手順を踏む 必要があると思っている。
- 大量のサンプル画像を用意し、それらを分類する。
- サンプル画像から「教師データ」を作成する。
- 教師データを使って「学習」を行う。(学習とは、各層で使われるフィルタを 教師データを元に調整していくこと、と理解)
- 画像を調整済みフィルタを使って分類する(各分類の確率を計算する)。
1と2はプログラム以前の準備段階だ。が、yusugomori実装では教師データと 学習状況の確認に使うテストデータをプログラム内で生成している。 最終的には学習データとテストデータは外から与える形にしたいが、 まずは同じようにプログラム内で生成するようにしよう。
教師データの生成
ゆくゆく教師データを外から与えることも考え、「画像データの集合」
の型??Pool
を作ろう。これらの集合から幾つかの画像を取り出して
学習に使いたい。そこで、データに追番をつけてMap
に登録
することにした。とりあえずはオンメモリで処理できれば良いので
以下のようにプール(オンメモリ版、MemPool
)を定義した。
(Pool.hs) class Pool p where getImages :: p -> Int -> Int -> IO [Trainer] nSample :: p -> Int newtype MemPool = MemPool { m :: Map.Map Int Trainer }
yusugomori実装に倣って教師データを生成する関数も用意した。
(Pool.hs) initSamplePool :: Int -> (Int, Int) -> Int -> Double -> Int -> IO MemPool initSamplePool c (sx, sy) o p n = do s0 <- forM [0..(n-1)] $ \i -> do let cl = i `mod` o -- class of this image -- Image data s1 <- forM [1..c] $ \j -> do s2 <- forM [0..(sy-1)] $ \y -> do let p' = if y `div` st == cl then p else (1-p) s3 <- forM [1..sx] $ \x -> do a <- pixel p' return a return s3 return s2 -- Trainer data e1 <- forM [0..(o-1)] $ \j -> do return $ if j == cl then 1.0 else 0.0 return (s1, e1) return (MemPool (Map.fromList $ zip [0..] s0)) where st = sy `div` o pixel :: Double -> IO Double pixel p = do v <- MT.randomIO :: IO Double let v' = if v < p then 0.5 else 0.0 return v'
結構ごちゃごちゃしているが、以下のような3種類の画像データを生成してプール として返しているのだ。
実際は上記のようなキッチリした画像ではなく、灰色部分に一定割合で白が 混ざっていて、白色部分は逆に灰色が混ざっている。教師データではその 割合を5%、テストデータは10%としている。
つぎに、プールから指定枚数の画像を取り出す関数getImages
とプール内の
画像総数を返す関数nSample
を示そう。
(Pool.hs) {- getImages IN : pool epoch number batch size -} instance Pool MemPool where getImages p@(MemPool m) e b = do let s = nSample p o = (e-1) * b `mod` s mx0 = o + b - 1 mx2 = mx0 - s mx1 = if mx2 < 0 then mx0 else s - 1 im0 = mapMaybe (\x -> Map.lookup x m) [o..mx1] im1 = mapMaybe (\x -> Map.lookup x m) [0..mx2] return (im0 ++ im1) nSample (MemPool m) = Map.size m
getImages
は若干ややこしいが、要は教師データを満遍なく学習させたいので
epoch毎に違う画像を取り出すようにしている(最初のepochで1番目から10個
取り出したら次のepochでは11番目から10個取り出す)。
ゆくゆくは順番に取り出すのではなくランダムに取り出すオプションも実装したい。
main関数(全体の流れ)
ここで、全体の流れを説明しておきたいのでmain
関数の話をしよう。
大雑把には次のような流れだ。
- パラメータ定義(
main
以前):フィルタの大きさとかバッチサイズとか (将来的にパラメータを設定ファイルから読み込むようにしたい) - 教師データ、テストデータの準備
- 各レイヤの初期フィルタの生成
- レイヤの組み立て
- 学習の繰り返し
まずパラメータの説明から。画像は3種類に分類する(k)。教師データが 50x3=150個、テストデータが10x3=30個だ。画像サイズ、フィルタは 先に示した各レイヤの仕様どおり。なおバッチサイズは教師データが少ないので 毎回全教師データを学習するために150個としている。
(Main-cnn.hs) -- PARAMETERS -- training/test dataset k = 3 -- number of class n = 50 -- number of teacher data for each class m = 10 -- number of test data for each class train_N = n * k test_N = m * k -- image size image_size = [12, 12] channel = 1 -- filter specs n_kernels = [10, 20] kernel_sizes = [3, 2] pool_sizes = [2, 2] n_hidden = 20 n_out = k -- loop parameters epochs = 200 opStep = 5 epoch0 = 1 batch = 150 -- others learning_rate = 0.1
次にメインルーチンだ。教師データとテストデータは次のように生成 している。説明はいらないだろう。
(Main-cnn.hs) main :: IO () main = do putStrLn "Building the model..." poolT <- initSamplePool 1 (12, 12) 3 0.95 train_N -- trainer data pool poolE <- initSamplePool 1 (12, 12) 3 0.90 test_N -- test data pool sampleE <- getImages poolE 1 test_N
次はレイヤの定義だ。まずフィルタを初期化してからレイヤを複数並べる。
(Main-cnn.hs) fc1 <- initFilterC 10 1 12 12 3 2 fc2 <- initFilterC 20 10 5 5 2 2 fh1 <- initFilterH n_hidden (2*2*20) fh2 <- initFilterH n_out n_hidden let layers = [ConvLayer 3 fc1, ActLayer relu, MaxPoolLayer 2, ConvLayer 2 fc2, ActLayer relu, MaxPoolLayer 2, FlattenLayer flatten, HiddenLayer fh1, ActLayer relu, HiddenLayer fh2, ActLayer softmax]
ここでは、畳み込み層1(活性化関数ReLU)→プーリング層1→
畳み込み層2(活性化関数ReLU)→プーリング層2→隠れ層(活性化関数ReLU)→
出力層(活性化関数softmax) という多層構造にした。
なお、FlattenLayer
は畳み込み+プーリングの処理から全結合へデータ形式を
変換する処理である。
最後が学習の繰り返しだ。
(Main-cnn.hs) tm0 <- getCurrentTime putStatus 0 tm0 [([0.0], 0.0)] layers loop is tm0 layers batch poolT sampleE
時間の記録と学習前の状態をダミーで表示したあと、繰り返し学習する
loop
を呼んでいる。loop
の詳細は次の通り。
(Main-cnn.hs) loop :: Pool p => [Int] -> UTCTime -> [Layer] -> Int -> p -> [Trainer] -> IO () loop [] _ _ _ _ _ = putStr "" loop (i:is) tm0 ls b pt se = do teachers <- getImages pt i b ops <- mapM (train ls) teachers let (_, dls) = unzip ops ls' = updateLayer ls dls -- dls = diff of layers if i `mod` opStep == 0 then putStatus i tm0 (evaluate ls' se) ls' else putStr "" loop is tm0 ls' b pt se
大したことはやってなくて、epoch毎に繰り返しloop
を呼び、
epoch番号がなくなったら(空リストになったら)、繰り返しを終了する。
中身は、学習する教師データをプールから取り出して、それぞれ学習をし、
各層を学習結果を使って更新する。とはいえ、まだ「学習」は実装しておらず、
この部分はダミーである。
ここまでがmain関数だ。
長くなってしまったので、各層(レイヤ)の処理については次に 回すことにする。
まとめ
今回はCNNの画像認識プログラムの初回として以下に取り組んだ。
- CNNで使われるいろいろな型を定義した。
- 入力値を変換するいろいろな「層」を定義した。
- これらを使って順伝播の処理を実装した。
次回は各層についての説明。
(ここまでのソースはこちら)
CPUの創りかた(10): おまけ、アセンブラ
CPU自体は前回までで完成したので、次のネタに行ってもよかったのだが、
- CPU(の実行プログラム)に与えるのがマシンコードだと、いちいち ハンドアセンブルするのが面倒くさい。
- 別件でパーサを書く必要がありParsecライブラリに興味を持っていたので そのうち勉強したいと思っていた。
という理由により、今回はおまけとして簡易アセンブラを作ってみよう。
まずは文法の定義から
このCPU(TD4)は命令数が非常に少ないので、何となれば、単純な文字列 変換でもよかったのだが、Parsecの勉強も兼ねているからそこはちゃんと 文法の定義から入らなければなるまい。
文法定義とくればBNFだろう。大学時代に、わからないなりに適当な文法を 定義して遊んでいたのを思い出す。その頃の記憶を頼りにBNFで書き始めたのだが、 どうやら世間には EBNF というのがあるようなのでどうせならこちらにしよう、BNFの問題を 解決しているということだし。
ところでアセンブリ言語(ニーモニック?)の文法はどのように定義したら いいのだろう? と調べたら、 こういうの が見つかった。作りたいのはこれよりだいぶ簡素なものなので、ありがたく 参考にさせていただいた。EBNFはこれが初めてなので書き方が間違っているかも しれないが、とりあえず次のように定義してみた。
# EBNF for TD4 assembler program = instcode , { instcode } ; instcode = ( code2 | code1 ) , linefeed ; code2 = inst2, space, operand2 ; code1 = inst1, space, operand1 ; inst2 = 'add' | 'mov' ; inst1 = 'in' | 'out' | 'jnc' | 'jmp' ; operand2 = register , "," , operand1 ; operand1 = register | imdata ; register = 'a' | 'b' ; imdata = 4 * digit2 ; digit2 = "0" | "1" ; space = white space , { white space } ; white space = '\x20' | '\x09' ; linefeed = '\x0a' | ( '\x0d' , '\x0a' ) ;
2オペランド命令のANDとMOV、それ以外のは1オペランド命令なので定義が異なる。 あとはレジスタとか直値とかを定義していけばよさそう。ひとまず形になった 気がするので先に進もう。
パーサの前に
どうもParsecを使えば、EBNF(BNF)の定義からある程度容易にパーサの プログラムに落とし込める、という話があるらしい。ならEBNFができている のだから簡単に作れるよね、と思ったのは甘すぎだった。
まず参考となるWebサイトをいろいろ読んでみて、こう作ればよさそうという 感触を得たかったのだが、ちっとも理解できなかった。今なら何を理解できて いなかったのか分かるが、当初は本当にわからなかったのだ。
要は、ソースをパーサが字句解析したあと、それをどのようにして次の処理 (意味解析、コード生成)に結びつけたらいいのかイメージが湧かなかったため。 Web上でありがちな例は、"add 1,2"みたいなのが入力されたら、"add"を 解析して「"add"という文字列を返す」みたいなやつだ。文字列を解析したい のに解析結果が文字列ならそれをさらに解釈する処理が必要で堂々巡りに 思えてしまった。転機はこの記事。 この記事では明快に「返す値を型で定義している」。
つまりパーサからは「解析木」かそれに類する構造化されたデータが出力されるのだ。 それをまず考えて(定義して)おかないとパーサが書けるわけがない。 ではどのような構造のデータがあればマシンコードに変換できるかを考えてみる。
TD4の命令は、命令コードと1つまたは2つのオペランドからなる(オペランドなしの 命令は無い)。そこで、これらを組で表すことにする。最終的にはこう。
data Inst = Add | Mov | In | Out | Jnc | Jmp deriving (Enum, Show) data Operand = RegA | RegB | Imdata String deriving Show type Mnemonic = (Inst, (Operand, Maybe Operand))
Mnemonic
は二重の組だ。命令コードとオペランドの組からなる。
オペランドの組は、一つ目は必ず存在するので普通にOperand
で、
二つ目は無いかもしれないのでMaybe
型とした。オペランドはA,Bレジスタか
直値の三種類しかない。パーサはソースを解析してMnemonicを命令の数だけ
リストにして返してくれればよいのだ(以後、解析リスト、とする)。
パーサを書く
ではパーサを書いてみようと思う。何となくだが末端から作って積み重ねて 行った方がわかりやすそうなので、個々のオペランドから始める。まずは 直値(immediate data)から。
-- EBNF -- imdata = 4 * digit2 ; -- digit2 = "0" | "1" ; imdata :: Parser Operand imdata = do im <- count 4 (oneOf "01") return $ Imdata im
先に定義したように、直値もOperand
型の一つなのでパーサの型が
Parser Operand
になっている。直値は二進数だけを扱うことにし、
かならず4桁と決めた。なので、oneOf
で0か1に限定し、それを4つ
連続して取り出したら返すようにした。EBNFの定義と見比べると、
決めた通りにプログラムを書けばよいのがわかる。
同様に、A,Bレジスタはこうなる。
-- EBNF -- register = 'a' | 'b' ; register :: Parser Operand register = do rg <- (regA <|> regB) return rg regA :: Parser Operand regA = do rg <- string "a" return $ RegA regB :: Parser Operand regB = do rg <- string "b" return $ RegB
AかBかの区別をつけるため、それぞれ別にパーサを定義し、それを<|>
で
合わせてレジスタのパーサとした。
あとは同様に、EBNFをもとに以下のようなパーサを作った。
program :: Parser [Mnemonic] program = do pg <- many1 $ instcode return pg instcode :: Parser Mnemonic instcode = do cd <- code2 <|> code1 many1 $ oneOf "\r\n" return cd code2 :: Parser Mnemonic code2 = do in2 <- inst2 many1 space op2 <- operand2 return (in2, op2) code1 :: Parser Mnemonic code1 = do in1 <- inst1 many1 space op1 <- operand1 return (in1, (op1, Nothing)) inst2 :: Parser Inst inst2 = do i2 <- (string "add" <|> string "mov") let i = if i2 == "add" then Add else Mov return i inst1 :: Parser Inst inst1 = do i1 <- (string "in" <|> string "out" <|> try (string "jnc") <|> (string "jmp")) let i = case i1 of "in" -> In "out" -> Out "jnc" -> Jnc "jmp" -> Jmp return i operand2 :: Parser (Operand, Maybe Operand) operand2 = do op2 <- register char ',' op1 <- operand1 return $ (op2, Just op1) operand1 :: Parser Operand operand1 = do op1 <- (register <|> imdata) return op1
EBNFの定義と見比べれば、それぞれ何をしているかは分かると思う。 ではテストしてみよう。テスト用プログラムはざっと以下のような感じ。
module Main where import Control.Applicative hiding ((<|>)) import Data.Char import Text.Parsec import Text.Parsec.String import Text.Parsec.Char (型、パーサ定義は省略) main :: IO () main = do parseTest inst2 "add" parseTest inst2 "mov" parseTest inst2 "abc" parseTest register "a" parseTest register "b" parseTest register "c" parseTest imdata "0100" parseTest imdata "10100" parseTest imdata "1012" parseTest operand1 "aa" parseTest operand2 "a 1100" parseTest code2 "add a,b" parseTest code2 "mov a,0011" parseTest code1 "jmp 1011" parseTest code1 "in b" parseTest code1 "in a" parseTest code1 "in 0110" parseTest instcode "add a,b\n" parseTest instcode "add a,b\r\n" parseTest instcode "add a,a" parseTest instcode "jmp 1100\r\n"
このように、パーサに食わせてみたい文字列とそれを処理するパーサ関数を 組みにして与えればいいようだ。パーサの解析に失敗した(=文法にそぐわない) 場合はエラーが返るのですぐわかる。ざっとみたところうまく動いている ように・・・見えなかった!
文法定義のやり直し
うまくいったと思っていたのに実はいけていなかった。add a,a
とか
in a
という命令はTD4には存在しないがパーサを通ってしまうのだ。
文法定義が甘かったわけだ。2オペランド命令と1オペランド命令を
分けるだけでは個々の命令の細かい制限(Bレジスタしか指定できない等)が
表現できていなかった。
ということで、EBNFの定義を見直す。
EBNF for TD4 assembler (revision 1) program = line , { line } ; line = instcode , linefeed ; instcode = inst_add | inst_mov | inst_in | inst_out | inst_jump ; inst_add = 'add' , space , register , "," , imdata ; inst_mov = 'mov' , space , ( op_mov1 | op_mov2 | op_mov3 ) ; inst_in = 'in' , space , register ; inst_out = 'out' , space , ( reg_b | imdata) ; inst_jump = ( 'jnc' | 'jmp' ) , space , imdata ; op_mov1 = register , "," , imdata ; op_mov2 = reg_a , "," , reg_b ; op_mov3 = reg_b , "," , reg_a ; register = reg_a | reg_b ; reg_a = 'a' ; reg_b = 'b' ; (imdata以降は同じなので割愛)
ポイントは、個々の命令ごとにオペランドのパターンを記述したこと。 結局オペランドが共通なのはジャンプ命令だけだった。これに沿って パーサも書き直す。
instcode :: Parser Mnemonic instcode = do cd <- inst_add <|> inst_mov <|> inst_in <|> inst_out <|> inst_jump return cd inst_add :: Parser Mnemonic inst_add = do in1 <- string "add" many1 space rg1 <- register char ',' im1 <- imdata return (toInst in1, (rg1, Just im1)) inst_mov :: Parser Mnemonic inst_mov = do in1 <- string "mov" many1 space op <- try (op_mov1) <|> (try op_mov2 <|> op_mov3) return (toInst in1, op) inst_in :: Parser Mnemonic inst_in = do in1 <- string "in" many1 space rg <- register return (toInst in1, (rg, Nothing)) inst_out :: Parser Mnemonic inst_out = do in1 <- string "out" many1 space op <- regB <|> imdata return (toInst in1, (op, Nothing)) inst_jump :: Parser Mnemonic inst_jump = do in1 <- try (string "jnc") <|> (string "jmp") many1 space im <- imdata return (toInst in1, (im, Nothing)) op_mov1 :: Parser (Operand, Maybe Operand) op_mov1 = do rg <- register char ',' im <- imdata return (rg, Just im) op_mov2 :: Parser (Operand, Maybe Operand) op_mov2 = do op1 <- regA char ',' op2 <- regB return (op1, Just op2) op_mov3 :: Parser (Operand, Maybe Operand) op_mov3 = do op1 <- regB char ',' op2 <- regA return (op1, Just op2) toInst :: String -> Inst toInst s = case s of "add" -> Add "mov" -> Mov "in" -> In "out" -> Out "jnc" -> Jnc "jmp" -> Jmp
先ほどと同じテストを流してみると・・・ちゃんとmov a,a
やin a
が
エラーになっている! パーサが出来上がった!
(Applicativeスタイルへの対応はまた今度。上記の書き方だけでも
まだ全然理屈を咀嚼できていない)
コード生成
さて、パーサはソースプログラムの解析をするだけなので、そこから 目的のマシンコードを作り出す処理が必要だ。次はコード生成部分を作ろう。 と言っても、パーサがきちんと解析リストを生成してくれれば あとは簡単だ。AならBというふうに対応するマシンコードを返せば良い。 TD4は命令数が非常に少ないので、全部列挙することにした。
generate :: Either ParseError [Mnemonic] -> [String] generate (Left s) = [show s] generate (Right []) = [] generate (Right (x:xs)) = (translateOne x):(generate $ Right xs) translateOne :: Mnemonic -> String translateOne (Add, (RegA, Just (Imdata s))) = "0000" ++ s translateOne (Mov, (RegA, Just RegB)) = "00010000" translateOne (In , (RegA, Nothing)) = "00100000" translateOne (Mov, (RegA, Just (Imdata s))) = "0011" ++ s translateOne (Mov, (RegB, Just RegA)) = "01000000" translateOne (Add, (RegB, Just (Imdata s))) = "0101" ++ s translateOne (In , (RegB, Nothing)) = "01100000" translateOne (Mov, (RegB, Just (Imdata s))) = "0111" ++ s translateOne (Out, (RegB, Nothing)) = "10010000" translateOne (Out, (Imdata s, Nothing)) = "1011" ++ s translateOne (Jnc, (Imdata s, Nothing)) = "1110" ++ s translateOne (Jmp, (Imdata s, Nothing)) = "1111" ++ s translateOne _ = error "no such mnemonic"
最後の行は保険だ。パーサがきちんと解析できていれば定義されていない 命令の解析リストが入力されることは無いだろうから。コンパイルして実行 してみる。
$ cabal build td4asm : $ echo "mov a,b" | dist/build/td4asm/td4asm 00010000
おお!正しく変換されている!ちなみに、入力の最後に改行が無いとエラーになる。
$ echo -n "mov a,b" | dist/build/td4asm/td4asm "TD4 asm" (line 1, column 8): unexpected end of input expecting new-line
構文解析で、命令行の最後は改行で終わるように定義しているからだ・・・。 これぐらいの制約は多めに見てもらおう。
再びラーメンタイマーの実行
前回はラーメンタイマープログラムのマシンコードを手で作ってCPUに入れていた。 今回はアセンブラにアセンブリ言語のソースを入れてマシンコードを生成させて CPUへ入れたいと思う。アセンブラは生成したマシンコードを標準出力に出すので そのままパイプでCPUへつないであげればいいのだ。
* 見やすくするため実際には指定しているディレクトリなどは省いている * $ cat ramen.a out 0111 add a,0001 jnc 0001 add a,0001 jnc 0011 out 0110 add a,0001 jnc 0110 add a,0001 jnc 1000 out 0000 out 0100 add a,0001 jnc 1010 out 1000 jmp 1111 $ td4asm < ramen.a | 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:0111][PC:0001] step 2; [CF:0][A:0001][B:0000][OP:0111][PC:0010] ^C
ちゃんと動いている! やはりハンドアセンブルより断然楽ちんだ。
まとめ
さて、今回で本当に"CPU回"はおしまい。記事を細切れにしたせいもあって 10回にもなってしまった。長丁場だったが、CPUネタは面白い取り組みだったなあ。 どこかにi4004の回路図落ちてないかな :-)
(ここまでのソース)
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を用いてレジスタが準備できた。「状態」は別途管理しないと 行けないので完璧とは言えないが、まあよしとしよう。
次は何にするか? 加算器あたりかな?
(ここまでのソースはこちら)