どうも，めぶきぶです．
この記事は，大学生の春休みに8クイーン問題が解けるCPUをVerilogHDLで作成した，その記録になります．
1．8クイーン問題とは
8クイーン問題について軽く説明します．
8クイーン問題とは，チェスの盤上にクイーンを8つ配置するのですが，そのそれぞれのクイーンが自分以外のクイーンの攻撃範囲に入っていないように，配置することはできるのかという，一種のパズルみたいなものです．
詳しくは以下のWikipediaを参照してください．
2．完成したもの
完成したものを載せます．（私のツイートです）
スレッドにしてしまったため，見にくいですが，「8クイーン問題を解ける～」と書いてある方を見てください．
8クイーン問題を解けるCPU、遂に完成！！
— めぶきぶ (@MebuKibu) March 20, 2022
動画は計算終了5秒前です。 pic.twitter.com/Vd8yt83a9j
ツイートにもある通り，8クイーン問題を解いている様子の動画になります．
動画では5秒ほどですが，実際には1分程度かかっています．
作成したコードの全てをgithubに載せましたので，そのURLを載せます．
しかし．コメント等何もしていないので，見られたものではないと思います．
GitHub - mebukibu/mcpu: 8クイーン問題が解けるCPUを作る
3．作成したシステムの概要
ここからは作成したシステム概要についてです．
システムは以下の図の通りです．
一応，言葉でも説明すると，
- ① 8クイーン問題を解くプログラムをC言語で作成します．
- ② 自作コンパイラ(?)でコンパイルします．アセンブリが出力されます．この時のアセンブリは 64bit Linux環境で動作します．
- ③ アセンブリを自作アセンブリに変換します．このアセンブリは自作CPU用のものです．
- ④ 自作アセンブラで機械語に変換します．VerilogHDLで作成したRAMに書き込めるような形式で出力します．
- ⑤ 自作CPUで実行します．
- ⑥ CPUで計算した解をドットマトリクスで表示します．
というような流れで，8クイーン問題を解き，表示します．
4．作成したシステムの個々の説明
ここでは，作成したシステム①~⑥を1つずつ説明していきます．
① 8クイーン問題のソルバー
8クイーン問題を解くプログラムをC言語で作成します．
ただし，ここのC言語は自作コンパイラ(?)でコンパイルできる文法に限られます．
ざっくりいうと，構造体やfloat,double型，ヘッダの利用等ができません．
どんな感じで実装したかを説明すると，クイーンが他のクイーンの攻撃範囲に入らないように，1つずつ置いていって，クイーンが置けなかったら1つ前に置いたクイーンの位置を変えて，8つ置けるまで繰り返すといった感じです．
② 自作コンパイラ(?)
ここまでの記事で自作コンパイラ(?)と，(?)が付いているのが気になった人もいると思います．
これは，自作コンパイラ(?)は自作したものではなく，以下の記事を写経したものだからです．
この記事のステップ28までのコンパイラを使用しています．ただし，int型の大きさを8byteから4byteに変更しています．
(2週間くらいかけてしっかり勉強したので，自作(?)くらいは許してください)
ステップ28までのコンパイラでは，C言語のうち，以下のものに対応しています．
・符号付き整数 ・四則演算 ・比較演算 ・ローカル変数 ・return文
・if-else, for, while文 ・関数 ・ポインタ ・sizeof 演算子 ・配列
こう見ると，かなり多くのものに対応していると思います．
③ アセンブリを自作アセンブリに変換
②で出力されるアセンブリは，64bit Linux環境で動作します．
8クイーン問題が解けるCPUは，②で出力されるアセンブリが動作すればよいことが分かります．
しかし，②で出力されるアセンブリは割と単純ではなく，複雑です．
次の文を例を挙げます．
この文の時のCPUの動作は，RSP(スタックポインタ)の値を8引いて，スタックにRAXレジスタの値を保存します．引き算と保存という2つの行動をします．
2つ行動ができるようなCPUを作るのは難易度が高いと思ったので，以下の文に変換することにしました．
PUSH RAX
更に，例を出します．
push アドレス
push 整数(4byte)
このように，pushは3種類の引数をとることができます．
この3種類にどうやって対応しているのか分からなかったため，以下のように全て区別することにしました．
push アドレス → PUSHA アドレス
push 整数(4byte) → PUSHN 整数(4byte)
PUSH以外の命令も全て区別しています．
これらの変換をすることが，③の役目になります．
④ 自作アセンブラ
機械語は，
命令 ＋ 1個以上の引数
の形式になっています．これをここでは
オペコード ＋ オペランド
とも呼ぶことにします．
命令は，1byteで一応ルールも決まっています．その図を示します．
例としてPUSH系の3命令を挙げると，
PUSHA → 00000110
PUSHN → 00000101
となります．
まず，PUSH系は演算命令ではないので，7bit目は「0」です．
次に，6bit~2bitまでが命令本体となり，「00001」となっています．
そして，引数がレジスタか，アドレスか，整数かで下位2bitが変わります．
引数がレジスタの場合は，対応するレジスタの番号が1byte続きます．
引数がアドレスの場合は，アドレス値が8byte続きます．
引数が整数の場合は，整数値が4byte続きます．
引数が1つの命令は，この3パターンのみです．
引数が2つの命令(例えばmov，演算命令等)は，
レジスタ，整数値
のパターンがあります．
レジスタ，レジスタの場合は，対応するレジスタの番号が2つ続くので，結果として2byte続きます．
レジスタ，整数値の場合は，レジスタ番号(1byte)と整数値(4byte)で5byte続くことになります．
④ではこれらの変換を行い，VerilogHDLで作成したRAMの初期値として代入できる形で出力するところまで行います．
⑤ 自作CPU
ここがこの記事のメインになります．
まず，作成したCPUの回路図を示します．
この後は，モジュール1つ1つを説明して，それからどんな感じで命令を実行しているのかについて説明します．
・モジュールの個々の説明
回路図の左上から順に説明します．
また，selectorとdecoder以外のモジュールは全てクロックに同期しており，立ち上がりエッジ で動作します．
selectorとdecoderは組み合わせ回路です．
・flag ･･･ フラグレジスタ
演算命令が実行される度に更新されます．2bitレジスタです．
flag[0]は，演算結果が0であるとき，「1」を保持します．
flag[1]は，演算結果が負であるとき，「1」を保持します．
・state ･･･ ステートマシン
ステートマシンです．状態は9種類あります．
・IDLE ･･･ 待機状態，外部の入力 run＝1のとき，OPCFTに移行します．
・OPCFT ･･･ opcode fetch，オペコードを読み込み，OPLRDに移行します．
・OPLRD ･･･ opland read，オペランドを1byteずつRAMから読み保持します．読み終えたらOPLFTに移行します．
・OPLFT ･･･ opland fetch，オペランドを読み込み，ADRDに移行します．
・ADRD ･･･ address read，RAMからの読み込みが必要な命令か判断します．読み込みが不要な場合，EXEに移行，必要な場合，EXERDに移行します．
・EXERD ･･･ excute read，実行に必要なデータを1byteずつRAMから読みます．読み終えたらEXEに移行します．
・EXE ･･･ excute，命令を実行します．命令がHLTのときのみIDLEに移行します．それ以外はLDRDに移行します．
・LDRD ･･･ load read，RAMへの書き込みが必要な命令か判断します．書き込みが不要な場合，OPCFTに移行，必要な場合，LOADに移行します．
・LOAD ･･･ load，データをRAMに1byteずつ書き込みます．書き込みが終了したときOPCFTに移行します．
見にくくて申し訳ないです．
・cotrol ･･･ 制御線のコントローラ
回路図において太字でないものが制御線です．ほとんどのものに矢印がついています．
命令または，状態によって，バスを使用するモジュール等が変わるのでそれをコントロールします．
これは，モジュールとして独立に存在するわけではなく，モジュール同士を接続する際に作成しています．
・pc ･･･ プログラムカウンタ
現在実行している命令の位置(アドレス値)を保持します．
pcincに入力する値によって，いくつ足すのか，または足さないのかをコントロールできます．
・ramloader ･･･ RAMへの書き込みを担当
作成したRAMは，1byteずつしか読み書きができないので，一度，dbus(データバス)から8byte分のデータを保持して，1byteずつ書き込みを行います．
・ram ･･･ メインメモリ
216bit = 65536 バイトのメモリ領域があります．
1byteずつしか読み書きできません．
メモリの仕様を複雑にすれば，もっと上手くできたのですが，論理合成の時間を短縮するためにこのような仕様にしました．
・ramreader ･･･ RAMからの読み込みを担当
作成したRAMは，1byteずつしか読み書きができないので，1byteずつ読み込んでから，dbusにデータを流します．
・selector ･･･ registersに流すデータを選択
registersに流すデータをオペコードに基づいて，選択します．
フラグレジスタの値を使用するときは0埋めを行います．
・registers ･･･ レジスタ群
a,bの2つの出力があり，selによって，どのレジスタを選択するかコントロールします．
64bitレジスタは全部で10個あります．
・alu ･･･ 演算装置
64bit同士を演算し，64bitを出力します．
足し算，引き算，かけ算，論理積にのみ対応しています．
・opcode ･･･ オペコードを保持
オペコードを保持する8bitレジスタです．
・opland ･･･ オペランドを保持
・decoder ･･･ オペランドからデータを抽出
オペランドからデータを，オペコードに基づいて抽出します．
aluへは演算命令を，registersにはレジスタ選択番号を出力します．
オペランドに整数値が含まれるとき，符号拡張してdbusに流します．アドレス値の場合はそのまま流します．
・outreg ･･･ 出力用レジスタ
出力用レジスタですが，これは私が作成した8クイーン問題のソルバー用の出力となっています．現在の8つのクイーンの位置を出力します．
これでモジュールの説明は終了です．
・命令実行について
命令の実行には，以下の3つの段階があります．
・オペコード読み込み
・オペランド読み込み
・命令実行
もう少しざっくりいえば，命令を読み込み，引数を読み込み，実行するといった感じです．
これなら，ステートマシンの状態も，3状態＋待機の4状態でいいとなるはずです．
しかし，RAMが1byteずつしか読み書きできないことが影響して，オペランド読み込みの前や，命令実行の前後で，メモリを読み書きする時間が必要となるため，ステートマシンの状態が複雑化しています．
これで自作CPUの説明は終了です．
⑥ ドットマトリクスで表示
ドットマトリクス(LEDマトリクス)は，以下のようなものです．
縦と横の制御線をコントロールして，任意の場所を光らせることができるというものです．
今回は，CPUのoutregからの出力を少し加工して，8つのクイーンを光らせます．
クイーンの位置を1つずつ順番に光らせます．この切り替えを高速にします．人間の目では全て同時に光っているように見える．
というような感じで光らせています．
5．まとめ
今回は，8つのクイーン問題が解けるCPUを作成しました．
一応CPUなので，②でコンパイルできるソースは全て動かすことができると思います．(未確認)
6．参考文献
一番お世話になったといっても過言ではないです．無料で公開されているのもありがたい！コンパイラを通してCPUについても学べるのでおすすめです．
Amazonリンクになります．CPUの回路は概ねこの本を元にして作成しています．CPUからアセンブラ，コンパイラで自作する本です．
こちらもAmazonリンクになります．CPUについて全然知らないという人におすすめです．こちらの本で使用するICはもう廃盤となっており，入手が難しいですが，作らなくても良いと思います．私はマイクラで作ってみました()．
