RISC-Vベースの自作CPUに自作OSを実装(helloコマンドしかできない)

こんにちは,めぶきぶです.
この記事は,大学院生の春休みに就活をほったらかして作成した,自作CPUに自作OSを実装する,その記録になります.


タイトルは「RISC-Vベースの自作CPUに自作OSを実装(helloコマンドしかできない)」ですが,もう少し詳しく説明すると,「RISC-VとChiselで学ぶ はじめてのCPU自作」の内容をVerilogに移植し,「Writing an OS in 1,000 lines」という記事中のhelloコマンドまでを,移植したCPU上で動作させるという意味です.完全に自作というわけではないです.

 

 

1.完成したもの

TeraTermを用いてUART通信を行っています.

コマンドを入力し,その応答が返ってきます.

↓動画です(私のポスト)

https://x.com/MebuKibu/status/1773163575554592995?s=20

 

Github

github.com

 

2.システムの全体像

構築したシステムは図のようになっています.

動作の流れ

C言語にてOSを作成

RISC-VコンパイラでOSをコンパイルし,バイナリファイルを作成

③バイナリファイルから,命令部分のみを抽出し,16進数に変換

④CPUのmemory.vに16進数形式のファイルを書き込む

⑤Vivadoを用いて,Verilogで作成したCPUをbitstreamファイルに変換

FPGAボードに書き込み,CPUを起動

TeraTermを用いてUART通信を行い,helloコマンドを入力し「Hello World

 

 

2.1.FPGAボード

今回使用したFPGAボードはDigilent社の「ARTY S7-50」です.

digilent.com

 

数年前に,秋月電子通商で購入しました.そのときは,13,000円くらいだったと記憶していますが,今見たら22,440円になってました.びっくり

購入理由としては,「作ろう!CPU」のサポートページ において,このボードを用いたサンプルを見つけたためです.

Vivadoのインストールからシミュレーションの方法,FPGA書き込みまでサポートしているので,初心者の方にはおすすめです.

 

2.2.CPU

自作CPUは,「RISC-VとChiselで学ぶ はじめてのCPU自作――オープンソース命令セットによるカスタムCPU実装への第一歩」という本で作成するCPUをVerilogに移植したものです.

gihyo.jp

私の認識では,ChiselはVerilogよりも高位なハードウェア記述言語です.おそらく,ChiselコードをVerilogコードに変換することも可能ですが,より低位な視点で1からCPUを作成したいと思ったので,Verilogで書くことにしました.

この本は,かなりボリューミーで,簡単なCPUの実装から,パイプライン処理,ベクトル命令,カスタム命令について書かれています.その中から,「簡単なCPUの実装」の部分だけ使用し,Verilogに移植しました.

自作したCPUの命令セットは,RV32Iです.これは,RISC-V 32bitの基本整数命令セットIであり,乗算,除算命令は含みません.

 

2.3.OS

自作OSは,「Writing an OS in 1,000 lines」という記事のhelloコマンドまでを自作CPUに合うように変更しました.

operating-system-in-1000-lines.vercel.app

この記事は,全18章で構成され,章ごとに少しずつ実装していく形式になっています.一歩ずつ進めていくので,OSを勉強する上でおすすめです.

全18章のうち,15章のシステムコールまでを対象としました.16章以降は,ホストOS(自分のPCのOS)との通信するという内容でした.私は,FPGAボードに実装が目標だったため,内容が違うなと思い,16章以降は見送りました.

 

「Writing an OS in 1,000 lines」のOSと私の自作OSの変更点は以下です.

・OpenSBIを用いない

OpenSBIとは,RISC-VのオープンソースなSモードインターフェースです.自作CPUは,一から構築するため,これは使用できません.QEMUでのシミュレーションでは,-bias none としています.

 

・文字入出力はメモリマップドなUARTモジュール

OpenSBIが使用できないと,文字の入出力も一苦労です.ここでは,xv6-riscvで使用されているUARTモジュールを参考にして,実装することにしました.

xv6は,MIT(マサチューセッツ工科大学)の授業で用いられているOSです.元々x86 CPU用に実装されたxv6をRISC-V CPU用に実装し直したものがxv6-riscvです.ソースコードは,GitHubで公開されています.

github.com

 

・ページングSV32が実装できなかったので,ページングなし

ページングSV32に設定するには,CSRのSATPの32bit目の立てればよいと思っていたのですが,この処理を行うと例外が発生してしまいます.色々調べたのですが,解決方法が見つからず,ページングはなしとなりました.

shell.cはユーザアプリケーションで,ベースアドレスは仮想アドレスを指定しています.しかし,ページングがないため,仮想アドレスから物理アドレスへの変換ができません.そのため,一度コンパイルしてから,その結果をダンプしてアプリケーションのベース物理アドレスを確認し,その物理アドレスリンカスクリプトで指定してから,再びコンパイルするという方法でなんとか実装しました.(アプリケーションとは)

そもそも,自作CPUではCSRは存在するだけで,ほぼ機能していないので,ユーザモードとか意味ないです(泣)

 

2.4.UART通信

メモリマップドなUARTモジュールについて少し説明します.

メモリマップドとは,あるアドレスに対するメモリの読み書きが,他のデバイスの読み書きと対応する形式のことを指します.

私の自作CPUの場合だと,アドレス0x1000に対してメモリの読み書きを行うと,そのアドレスにはUARTモジュールが接続されているので,UARTモジュールに対して読み書きが行われます.

この手法の利点は,CPU側はメモリの読み書きをするだけでよく,他のデバイスのことを考える必要がないことです.

UARTのOS側動作(C言語)は,前述のようにxv6-riscvを参考にしています.

一方,CPU側(Verilog)では,主に以下の記事を参考にしました.

www.acri.c.titech.ac.jp

この記事は,UARTの送信側だけですが,受信側も検索すれば沢山出てきます.

 

3.まとめ

今回,RISC-Vベースの自作CPUに,helloコマンドができる自作OSを実装し,FPGAボードで動作させました.

今後は,まずページングをなんとかすることと,ファイルシステムにも挑戦してみたいと思います.

8クイーン問題が解けるCPUを作った

どうも,めぶきぶです.

この記事は,大学生の春休みに8クイーン問題が解けるCPUをVerilogHDLで作成した,その記録になります.

 

 

1.8クイーン問題とは

8クイーン問題について軽く説明します.

8クイーン問題とは,チェスの盤上にクイーンを8つ配置するのですが,そのそれぞれのクイーンが自分以外のクイーンの攻撃範囲に入っていないように,配置することはできるのかという,一種のパズルみたいなものです.

 

詳しくは以下のWikipediaを参照してください.

エイト・クイーン - Wikipedia

 

2.完成したもの

完成したものを載せます.(私のツイートです)

スレッドにしてしまったため,見にくいですが,「8クイーン問題を解ける~」と書いてある方を見てください.

mobile.twitter.com

ツイートにもある通り,8クイーン問題を解いている様子の動画になります.

動画では5秒ほどですが,実際には1分程度かかっています.

 

作成したコードの全てをgithubに載せましたので,そのURLを載せます.

しかし.コメント等何もしていないので,見られたものではないと思います.

GitHub - mebukibu/mcpu: 8クイーン問題が解けるCPUを作る

 

3.作成したシステムの概要

ここからは作成したシステム概要についてです.

システムは以下の図の通りです.

f:id:MebuKibu:20220403104137p:plain

作成したシステム

一応,言葉でも説明すると,

というような流れで,8クイーン問題を解き,表示します.

 

4.作成したシステムの個々の説明

ここでは,作成したシステム①~⑥を1つずつ説明していきます.

 

① 8クイーン問題のソルバー

8クイーン問題を解くプログラムをC言語で作成します.

ただし,ここのC言語は自作コンパイラ(?)でコンパイルできる文法に限られます.

ざっくりいうと,構造体やfloat,double型,ヘッダの利用等ができません.

 

どんな感じで実装したかを説明すると,クイーンが他のクイーンの攻撃範囲に入らないように,1つずつ置いていって,クイーンが置けなかったら1つ前に置いたクイーンの位置を変えて,8つ置けるまで繰り返すといった感じです.

 

② 自作コンパイラ(?)

ここまでの記事で自作コンパイラ(?)と,(?)が付いているのが気になった人もいると思います.

これは,自作コンパイラ(?)は自作したものではなく,以下の記事を写経したものだからです.

低レイヤを知りたい人のためのCコンパイラ作成入門

この記事のステップ28までのコンパイラを使用しています.ただし,int型の大きさを8byteから4byteに変更しています.

(2週間くらいかけてしっかり勉強したので,自作(?)くらいは許してください)

 

ステップ28までのコンパイラでは,C言語のうち,以下のものに対応しています.

・符号付き整数 ・四則演算 ・比較演算 ・ローカル変数 ・return文

・if-else, for, while文 ・関数 ・ポインタ ・sizeof 演算子 ・配列

グローバル変数 ・文字型 ・文字列リテラル

こう見ると,かなり多くのものに対応していると思います.

 

アセンブリを自作アセンブリに変換

②で出力されるアセンブリは,64bit Linux環境で動作します.

8クイーン問題が解けるCPUは,②で出力されるアセンブリが動作すればよいことが分かります.

しかし,②で出力されるアセンブリは割と単純ではなく,複雑です.

次の文を例を挙げます.

 push rax

この文の時のCPUの動作は,RSP(スタックポインタ)の値を8引いて,スタックにRAXレジスタの値を保存します.引き算と保存という2つの行動をします.

2つ行動ができるようなCPUを作るのは難易度が高いと思ったので,以下の文に変換することにしました.

 SUBN RSP 8
 PUSH RAX
行っていることは同じですが,上記のように,1つずつの行動に独立させることにしました.

 

更に,例を出します.

 push rax
 push アドレス
 push 整数(4byte)

このように,pushは3種類の引数をとることができます.

この3種類にどうやって対応しているのか分からなかったため,以下のように全て区別することにしました.

 push rax  → PUSH RAX
 push アドレス → PUSHA アドレス
 push 整数(4byte) → PUSHN 整数(4byte)

PUSH以外の命令も全て区別しています.

これらの変換をすることが,③の役目になります.

 

④ 自作アセンブラ

③で出力された自作アセンブリを自作機械語に変換します.

機械語は,

 命令 + 1個以上の引数

の形式になっています.これをここでは

 オペコード + オペランド

とも呼ぶことにします.

命令は,1byteで一応ルールも決まっています.その図を示します.

 

f:id:MebuKibu:20220403130823p:plain

 

例としてPUSH系の3命令を挙げると,

 PUSH      → 00000100
 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の回路図を示します.

f:id:MebuKibu:20220403133623p:plain

CPUの回路図

この後は,モジュール1つ1つを説明して,それからどんな感じで命令を実行しているのかについて説明します.

 

・モジュールの個々の説明

回路図の左上から順に説明します.

また,selectorとdecoder以外のモジュールは全てクロックに同期しており,立ち上がりエッジ で動作します.

selectorとdecoderは組み合わせ回路です.

 

・flag ・・・ フラグレジスタ

演算命令が実行される度に更新されます.2bitレジスタです.

flag[0]は,演算結果が0であるとき,「1」を保持します.

flag[1]は,演算結果が負であるとき,「1」を保持します.

 

・state ・・・ ステートマシン

ステートマシンです.状態は9種類あります.

f:id:MebuKibu:20220403141734p:plain

 

・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 ・・・ オペランドを保持

オペランドを保持する64bitレジスタです.

 

・decoder ・・・ オペランドからデータを抽出

オペランドからデータを,オペコードに基づいて抽出します.

aluへは演算命令を,registersにはレジスタ選択番号を出力します.

オペランドに整数値が含まれるとき,符号拡張してdbusに流します.アドレス値の場合はそのまま流します.

 

・outreg ・・・ 出力用レジスタ

出力用レジスタですが,これは私が作成した8クイーン問題のソルバー用の出力となっています.現在の8つのクイーンの位置を出力します.

 

これでモジュールの説明は終了です.

 

・命令実行について

命令の実行には,以下の3つの段階があります.

 ・オペコード読み込み

 ・オペランド読み込み

 ・命令実行

 

もう少しざっくりいえば,命令を読み込み,引数を読み込み,実行するといった感じです.

これなら,ステートマシンの状態も,3状態+待機の4状態でいいとなるはずです.

しかし,RAMが1byteずつしか読み書きできないことが影響して,オペランド読み込みの前や,命令実行の前後で,メモリを読み書きする時間が必要となるため,ステートマシンの状態が複雑化しています.

 

これで自作CPUの説明は終了です.

 

⑥ ドットマトリクスで表示

ドットマトリクス(LEDマトリクス)は,以下のようなものです.

f:id:MebuKibu:20220403151454j:plain

縦と横の制御線をコントロールして,任意の場所を光らせることができるというものです.

今回は,CPUのoutregからの出力を少し加工して,8つのクイーンを光らせます.

クイーンの位置を1つずつ順番に光らせます.この切り替えを高速にします.人間の目では全て同時に光っているように見える.

というような感じで光らせています.

 

5.まとめ

今回は,8つのクイーン問題が解けるCPUを作成しました.

一応CPUなので,②でコンパイルできるソースは全て動かすことができると思います.(未確認)

 

6.参考文献

低レイヤを知りたい人のためのCコンパイラ作成入門

一番お世話になったといっても過言ではないです.無料で公開されているのもありがたい!コンパイラを通してCPUについても学べるのでおすすめです.

 

プログラムがコンピュータで動く仕組み

Amazonリンクになります.CPUの回路は概ねこの本を元にして作成しています.CPUからアセンブラコンパイラで自作する本です.

 

CPUの創り方

こちらもAmazonリンクになります.CPUについて全然知らないという人におすすめです.こちらの本で使用するICはもう廃盤となっており,入手が難しいですが,作らなくても良いと思います.私はマイクラで作ってみました().