読者です 読者をやめる 読者になる 読者になる

Moiz's journal

プログラミングやFPGAなどの技術系の趣味に関するブログです

FPGAで動作するBrainf**k CPUをパイプライン化、スーパースカラー化もどきして、ベンチマークをとってみた

はじめに

前回のエントリーで紹介したFPGAで動作するBrainf**k CPU(BF CPU)を高速化しました。
高速化にあたっては

  • 明らかに無駄なところを直す
  • パイプライン化
  • スーパースカラー的な並列化

の3つを試してみました。また各段階毎にごく簡単なベンチマークをとってみました

Brainf**kについては、Wikipediaなどを参照ください
Brainfuck - Wikipedia

今回アップデートしたVerilog HDLとQuartus用プロジェクトファイルはgithubで公開してあります
github.com

明らかに無駄なところを直す

前回作成したBF CPUはループの終わりに来ると、わざわざ1バイトずつ戻ってループの先頭を探していました。
f:id:uzusayuu:20170520133646p:plain

これは、なるべく簡単な回路構成からはじめて少しずつ機能を増やしていくという方針のためにこうしたのですが、探索している時間は明らかにむだです。専用のスタックを導入することで、]に到達したら1クロックで対応する[に戻るようにしたところ、約2倍の高速化が実現できました。
ベンチマークとして、こちらのページのπを計算するプログラムyapi.bを使いました。*1
copy.sh

まずは最初の状態
www.youtube.com
目を疑うほど遅いですが、これでも50MHzで動作しています。次に高速化したもの
www.youtube.com

だいぶ速くなりました。約2倍の速度です。

パイプライン化

古典的なCPUの高速化の定番といえばパイプライン化です。BF CPUはデータフローも単純な上、もともとステージ構成もパイプライン化を念頭において作ってあったので、比較的容易にパイプライン化できます。フェッチ、実行、メモリーアクセス、の3段パイプラインです。各命令ごとの各パイプライン段での処理は以下のようになっています。

命令 フェッチ 実行 モリーアクセス
命令フェッチ、PC+1 ポインタ先+1 ポインタ先に書き込み
命令フェッチ、PC+1 ポインタ先-1 ポインタ先に書き込み
命令フェッチ、PC+1 ポインタ値+1 ポインタ先から読み込み
命令フェッチ、PC+1 ポインタ値-1 ポインタ先から読み込み
命令フェッチ、PC+1 処理なし ポインタ先の値をを出力
命令フェッチ、PC+1 処理なし ポインタ先へ入力
命令フェッチ、PC+1、ポインタ値がゼロなら探索モードへ 処理なし 処理なし
命令フェッチ、PC+1、ポインタ値がゼロなら[へジャンプ 処理なし 処理無し

ここで、+-の時はパイプライン3段目でメモリへの書き込みが、><の時は読み込みが発生します。+-では事前に読んだものをキャッシュしておいて、そこに演算を行うことでメモリー読み込みを回避しています。
パイプライン設計でまず必要なのはパイプラインハザードの回避です。今回はメモリーとして1サイクルで読み書きができる内蔵RAM/ROMを使用しているのでメモリートールはありませんが、データの依存によるストールは可能性があります。依存性のある部分を書き出してみると

条件 先の処理 次の処理
>又は< +又はー又は.
2 +又はー又は, [又は]
3 >又は< [又は]

条件1の回避のために、命令が>+などのようになっている場合(ポインタを1動かして、ポインタ先を+1)、メモリーから読んだ値を実行ユニットにフォワードします。
条件2の回避のために、実行ユニットの実行結果がフェッチユニットにフォワードされるようにしてあります。したがって、>-]のような処理(ポインタを+1して、ポインタ先を-1し、結果がゼロならジャンプ)の場合は、メモリーから読んだ値に同クロックで演算を行い、その結果を同クロック内で参照してジャンプの判定をしています。タイミング的に苦しいかとも思いましたが、FPGAでも実行できているので良しとします。
条件3はどうやっても1クロック待たないとデータが来ないので、実行を遅らせる必要があります。この場合[又は]の前にNOP命令を挿入して、ハザードを回避しています。

ここでまた先程のπ計算をやってみます。
www.youtube.com

だいぶ速くなりました。前回から約3倍。最初の状態から約6倍弱の速度です。

スーパースカラー的な命令並列化

次に考えられるのはスーパースカラー化ですが、なにしろBrainf**kには命令が8つしかなく、同時に扱う変数も一つなのでどうしても命令間の依存性が大きくなります。
並列化できるのはつながった+-をまとめる、又はつながった<>をまとめる、という程度です。しかも両者間には依存性があるので並列化はかなり面倒になります。
さらに、例えば++++をまとめる場合、+1実行ユニットを4つならべるよりも、1から4の値を増加(減少)できる演算ユニットを作成するほうが素直な実装になりそうです。
本来スーパースカラーというのは処理ユニットを複数おいて同時に実行することをいうのですが、これでは実行ユニットは一つのままなのでスーパースカラーとは言えません。ただ、一部の複数命令を同時に実行しているのは確かなので、ここでは「スーパースカラー化もどき」、とでも呼んでおきます。

実装上、今回は変更点は割と多くなり、以下のような点がかわりました

  • プログラムROMのデータ幅を8ビットから32ビットに変更(4命令同時読み込み)
  • フェッチステージで最大4つの命令をまとめて発行(+-か<>のどちらかの種類のみ)
  • これまで、各命令のアスキーコードをプロセッサ内でもオペコードとして使用してきたが、内部専用命令コードを作成
    • 内部命令は+>,.][とNOPとHALT*2の8種類(3ビット)
    • フェッチで命令と同時に、加算用の値(-4から+4)を生成(3ビット)
  • 実行ユニットでは、+1/-1の代わりに、受け渡された-4から+4までの値をポインタ値またはポインタに足す
  • 分岐命令]でジャンプした場合、1サイクルパイプラインをストールし、命令を先読みする(常時4命令以上参照できるようにするため)

またCPUとは直接関係ありませんが、32bit幅のデータの記述がうまく行かなかったのでROMの内容を示すFPGA用のデータファイルのフォーマットをIntel Hexから、Altera MIF形式に変更しました。*3
さて、これでどれだけ速くなったかというと、
www.youtube.com
ほとんど変わりません。次にベンチマークの結果を載せますが、約10%程度の増加です。かなりの作業量を費やした割に効果が薄く残念です。

ベンチマーク結果

これまでのベンチマークの結果をまとめるとこのようになります。計測はModelSimによるシミュレーションで行い、リセットから9桁目の数字がCPUから出力されるクロックまでの時間を測定しました。

バージョン 時間 (ms)
オリジナル 860
ジャンプ用スタック 458
パイプライン化 153
命令並列化 135

グラフではこうなります。
f:id:uzusayuu:20170520163616p:plain
こうしてみると、命令並列化のコストパフォーマンスの悪さがわかります。殆どのコードを書き直したので残念です。

他の高速化

他の高速化手法としてはこんなものが考えられます

  • 分岐時の投機実行
    • >]のようなケースで1クロックかせげる可能性があります
  • 本当にスーパースカラー
    • >と+など、異なる種類の命令を同時に実行できるようにします
  • 高クロック化

最後の高クロック化以外は労多くしてという感じなので、ちょっと考え中です。

まとめ

前回制作したFPGA用のBrainf**k CPUにパイプライン化などの高速化を行いました。
命令並列化の効果が低すぎるのが納得いかないので原因を調べてみようと思います

*1:このプログラムを動作させるためにポインター値のビット幅を16ビットに拡張したが、高速化とは直接関係ないので省略

*2:命令としてゼロが来るとHAL

*3:今は両方インテルですが

FPGAで動作するBrainf**k CPUを作ってみた

はじめに

前回のエントリーに書いたとおりBrainf**k言語を直接実行するCPUFPGA(Terasic DE0)で動作したのでまとめてみます。

f:id:uzusayuu:20170501084716p:plain

VerilogのコードとQuartusのプロジェクトファイルはこちらに公開してあります。

github.com

以下この稿では、このCPUをBF CPUと呼びます。

Brainf**kについて

Brainf**kは本来**の位置にはucが入るのですが、英語圏で非常に下品な単語なためこのように記述されることが多々あります。言語仕様としては'+-><.,[]'だけの非常にシンプルなものですが、チューリング完全であることが示されているということです。詳しくはWikipediaのページなどをご覧ください。

Brainfuck - Wikipedia

Brainfuck - Esolang 

 

スペック、必要な環境など

BF CPUのスペック
  • クロック速度: 50 MHz (ボードの制約による)
  • ROM (プログラム用): 4K byte
  • RAM (データ用): 4K byte
  • 入力: 8bit (switchからの入力)
  • 出力:8bit (LCDへの表示)
環境
  • ターゲットデバイス: Terasic DE0 (LCD必須)
  • 開発環境: Quartus II 13.1 (DE0用にセットアップされていること)
  • 使用言語: Verilog HDL (テストベンチにはSystem Verilogも使用)

BF CPUのブロック図

全体のブロック図はこんな感じです。

f:id:uzusayuu:20170501064512p:plain

コア部分のブロック図はこう

f:id:uzusayuu:20170501071531p:plain

目を疑うほどシンプルですが、一部制御などを省いて書いている以外は、だいたいこのとおりのHDLになっています。

ステートマシーンはこう

f:id:uzusayuu:20170501072438p:plain

バカにしてるのかと思うほど単純ですが、先々パイプライン化もしたいなと考えて、あえて単純な形に残しています。この他にステートと内部信号から制御信号を作る制御回路があります。

処理の流れとしては、コマンド毎にこうなります

  • '+' or '-': PC++, data_out=data_in+1 (or data_in-1)
  • '>' or '<': PC++, dp_adr ++ (or --)
  • ',' or '.' : PC++, data_out=data_in。','の場合data_inはメモリーからで、data_outは出力へ。'.'の場合、data_inは入力からで、data_outはメモリーへ 
  • '[': PC++, data_in=0なら探索モード(正方向)に移行
  • ']': dp_adr変更なし、data_in>0なら、探索モード(負方向)に移行。それ以外はPC++。
  • 探索モード(正方向): PC++、コマンドが'['なら、ループネストカウンターを+1。']'なら-1。カウンターが0になったら探索モード終了
  • 探索モード(負方向): PC--、コマンドが']'なら、ループネストカウンターを+1。'['なら-1。カウンターが0になったら探索モード終了

探索モードは'['と']'によるループのために作られたものです。'['又は']'が来ると条件次第でこのモードに入り、対応する'['や']'を探します。負方向に関してはスタックを作れば高速化できるのはわかっていたのですが、まずは小さいサイズで始めるためにこのようにしました。

実行してみる

まずBrainf**kのコードを用意します。普通の人間にかけるものではないので(書ける人もいるようですが...)、変換器などを使うのが良いと思います。文字を表示するだけならこちらをどうぞ。

Brainfuck text generator

こちらのサイトは文字を入力すると、その文字を出力するBFコードを作ってくれます。

たとえば、'BF rocks!'ならこう。

f:id:uzusayuu:20170501075405p:plain

このコードを適当なテキストファイルにコピーし、Quartusのコンパイラーが読めるように、tools内にあるtxt2hex.cを使ってrom_data.hexという名前のHEXテキスト形式ファイルに変換します。*1このファイルはプロジェクトファイル(bf.qpf)と同じ階層においておきます。 Quartus IIはこのファイルを読んで、ROM化します。ファイルの中身はこんな感じです。

:100000002b2b2b2b5b2b2b2b2b3e2d2d2d3c5d3ea1
:100010002d2e2b2b2b2b2e5b2d2d3e2b3c5d3e2d89
:100020002d2d2e3e2d5b2d2d2d3e2b3c5d3e2d2d61
:100030002d2e2d2d5b2d2d2d3e2b3c5d3e2d2e2d61
:100040002d2d2d2d2d2d2d2d2d2d2d2e2b2b2b2be7
:100050002b2b2b2b2e2b2b2b2b2b2b2b2b2e2b5bba
:100060002d2d3e2b2b2b2b2b3c5d3e2d2e5b5d0a2d
:00000001FF

これで準備ができました。

次にQuartus II 13.1を起動し、プロジェクト(bf.qpf)を開き、Processing->Start compilationでコンパイル、Tools->Programmerでプログラマーを開き、DE0に転送します。転送が終了したら、Button-2を押すとソフトリセットがかかり、こんなふうに実行されます。

f:id:uzusayuu:20170430161743j:plain

まとめ

単純な回路なのでCPUのロジック自体は半日程度でできたのですが、実際のROM/RAMをとりつけて、LCDに表示できるようになるまで随分かかってしまいました。この後改行をつけたり、入力を改善したりしようかなと思っています。

*1:フォーマットについてはWikipediaなどでIntel HEXを参照ください。

Brainf**k言語を直接実行するCPUがFPGAで動いた

f:id:uzusayuu:20170424125823j:image

 

なんとか動き出したので、そのうちGitHubに上げてブログで紹介します

 

Ubuntu16.04 64-bitで、Quartus II 13.1からModel-sim

前回の続きでQuartus II 13.1に付属のModel-sim Altera Starter Edition 10.1を64ビット版のUbuntu 16.04で動かしてみました。前回も触れましたが、64bit版Linuxと旧バージョンのQuartusの相性はあまり良くないようです。また、Ubuntuはサポート外となっていますので、私のような事情のない方は最新のQuartusとサポートOSの組み合わせをおすすめします。

とりあえず試す

AlteraのModelsSim-Altera Editionのチュートリアル通りに進めていくと、Tools -> Run Simulation Tool -> RTL simulation を選んだところでこんなエラーが出ました。

$ ** Fatal: Read failure in vlm process (0,0)
[2]+ Segmentation fault (core dumped) bin/vsim

予想通りの展開です。

FreeTypeコンパイル

どうやらこの原因はFreeTypeのバージョンの食い違いによるもののようです。いろいろなサイトに情報がありますが、こちらのブログが一番まとまっていました

www.molnar-peter.hu

Freetypeソースコードを手に入れてコンパイルし、modelsim_ase以下にlib32ディレクトリを作って、できたライブラリーをコピー。configureやmakeでエラーがでる場合は必要がライブラリーが足りないので適宜インストールします。このあたりは上記のブログを参照ください。

なお、私の環境では、途中で以下のようなエラーが出ましたが、

$ sudo apt-get build-dep -a i386 libfreetype6
E: You must put some 'source' URIs in your sources.list

/etc/apt/sources.listからコメントを省き、そのあとで

sudo apt-get update
sudo apt-get build-dep -a i386 libfreetype

を行うことで実行することができました。

Modelsimの環境設定、及びQuartus II との連携

これで、LD_LIBRARY_PATHにこのlib32ディレクトリを登録すれば、modelsim_ase/linux/vsimを呼び出すことができるようになります。("~/altera/13.1/modelsim_ase"はmodelsimのインストールディレクトリに変更する必要あり。)

$ export LD_LIBRARY_PATH=~/altera/13.1/modelsim_ase/lib32
$ ~/altera/13.1/modelsim_ase/linux/vsim

 ただ、これではまだQuartus II のメニューから呼び出す事ができません。Quartus IIで行った設定を元にシミュレーションしたい場合は以下の作業が必要です。

  1. Tools->Options...で、modelsim/alteraのディレクトリが、modelsim_ase/binが指定されていることを確認。f:id:uzusayuu:20170423064754p:plain
    私の環境ではこれが、modelsim_ase/linuxaloemを指していたために解決に無駄な時間を費やしてしまいました。
  2. modelsim_ase/bin/vcoの変更
    先ほどのブログでは、bin/vco*1中、dirの定義の後で
    export LD_LIBRARY_PATH=${dir}/lib32
    を追加すればよいと書いてありましたが、私の環境ではうまくいかないので、ディレクトリ名を直接指定しました。("/home/uname/altera/13.1/modelsim_ase"の部分はmodelsimのインストールディレクトリに変更が必要です
  3. dir=`dirname $arg0` #この行はもとからあった
    export LD_LIBRARY_PATH=/home/uname/altera/13.1/modelsim_ase/lib32 #追加

     さらに、最近の4.0以上のカーネルではディレクトリの指定がうまくいっていないので、以下の部分を、

      case $utype in
    2.4.[7-9]*) vco="linux" ;;
    2.4.[1-9][0-9]*) vco="linux" ;;
    2.[5-9]*) vco="linux" ;;
    2.[1-9][0-9]*) vco="linux" ;;
    3.[0-9]*) vco="linux" ;;
    *) vco="linux_rh60" ;;
    esac

      このように変更します

      case $utype in
    2.4.[7-9]*) vco="linux" ;;
    2.4.[1-9][0-9]*) vco="linux" ;;
    2.[5-9]*) vco="linux" ;;
    2.[1-9][0-9]*) vco="linux" ;;
    3.[0-9]*) vco="linux" ;;
    4.[0-9]*) vco="linux" ;; この行追加
    *) vco="linux_rh60" ;;
    esac

これでどうにかQuartus II 13.1からmodelsimを呼び出すことができるようになりました

f:id:uzusayuu:20170423070655p:plain

その他

Ubuntuは関係ありませんが、Megawizardで作ったモデルを使うときは、Start Simulationの画面で適切なライブラリ(今回の場合はaltera_mf_ver)をLibrariesタブからSearch Libraries Firstのテーブルに入れておく必要があります。また、ROMなどの初期化ファイルはプロジェクトフォルダにおいておきます。(わからなくてしばらくハマりました。)

*1:vcoはlinux以下やlinuxaloem以下のvsimなどの本体を呼び出すためのスクリプト

Ubuntuに古いQuartus IIを入れたらいろいろ大変だった

Ubuntu16.04(64ビット)にQuartus II 13.1 Web Editionを入れた際のメモ

久しぶりにFPGAボード(Terasis DE0)を動かそうと思ったのですが、最近デスクトップのメインOSをUbuntuに変えたところなので、ついでにQuartus II 13.1をインストールしたところいろいろ大変だったので、その個人的メモです。間違っている可能性もかなりありますので、もし参考にされる方がいらっしゃる場合はご自身の判断を元に自己責任でおねがいします。

www.terasic.com.tw

最新のQuartusが16.1だというのに、なぜいまさら13.1なのかというと、手元に2個もあるDE0*1がもったいなかったからで、DE0に入っているCyclone IIIをサポートする最新のバージョンが13.1だからです。UbuntuがQuartusのサポートOSリストに入っていないことはインストールしてしばらく経ってから気がついたのですが、いまさら戻るに戻れず、無理やり進めています。

これからインストールするのなら、サポートされているOSで、最新のQuartus IIを使ったほうが無難だと思います。

Quartus II 13.1 Web Edition のインストール

  • 次のようなシンボリックリンクを貼ると良いという人がいたので真似をしてみる。これでインストールスクリプトがとりあえず動く。
    ln -s /lib/x86_64-linux-gnu/libpng12.so.0 /usr/lib64/libpng12.so.0
    ln -s /lib/i386-linux-gnu/libpng12.so.0 /usr/lib/libpng12.so.0
  • インストール先としては/opt/quartusを勧めている人が多いが、今回は~/altera/13.1/quartusにインストール。今のところ問題なし
  • 自分のミスだが、途中rootで実行した処理のせいで~/.alteraにユーザーの書き込み権限がなくなってしまい、設定が反映されず苦労した(talkbackがオンにならない、など)
  • これだけやっても、ヘルプページなどが表示できない。ブラウザーとの連携がうまくいっていない模様

USB Blaster

  • こちらのページを参考にUSB Blasterの設定
    Altera USB-Blaster with Ubuntu 14.04 | fpga-dev.com
  • DE0の場合、ACアダプターが接続されていないと、一見して電源が入っているようでもUSB Blasterが動作しないようだ

NIOS2 EDS

  • NIOSII EDSにインストール場所を伝えるために以下のラインを.bashrcに追加。対象のディレクトリは適宜変更のこと。(1行目は後述のflash_programmerのため)
    export QUARTUS_ROOTDIR="$home/altera/13.1/quartus"
    export QUARTUS_ROOTDIR_OVERRIDE=$QUARTUS_ROOTDIR
    export QUARTUS_64BIT=1

Flash_programmer

  • NIOS II EDSからFlash_programmerでプログラム(ELF)とSOFをフラッシュに書き出すために、/bin/shを変更。これがないとflash_programmerがError code:1を吐き出して止まる。ただし、副作用の確認が必要
    Ubuntuのデフォルトでは/bin/shはdashへのシンボリックリンクだが、flash_programmerはbashを仮定しているため、このままでは動作しない)
  • sudo rm /bin/sh
    sudo ln -s /bin/bash /bin/sh

Qsys (Ubuntuは関係ないが、13.1で困った点)

  • flash_programmerでflashにsofとelfを書き込む場合、Qsysで以下の点について確認しておくこと
  • NIOS2のjtag_debug_module_reset出力がSerial Flash Controllerのreset入力に接続されていることを確認。こうしておかないと、EPCSのregisterが見つからずError code: 8でflash_programmerが終了する。

    Why does the Nios II Processor Flash controller not find the EPCS registers and fail when trying to program the flash?

  •  同様に、QsysでSerial Flash Controllerのcontrol portがNIOS2のインストラクションアドレスに加えて、データアドレスに接続されている事を確認。さもないと、registerが見つからないという上と同様のエラーがでる

  • Qsysで、PIOなどのexternal-connection (Conduit)などはexportする必要がある。exportコラムをダブルクリックで設定

その他(UbuntuもQuartusのバージョンも関係はないが、困った点)

  • ピンのアサインメントを変えるときはprojectのqsfファイルを直接変更してもダメ。変更したアサインメントファイルをインポートする(またはエディタで変更する)
  • コンパイル時に「Open Core Plusのファイルがあるからライセンスがないとコンパイルできない」というエラーが出た場合、Quartus II -> Assignment -> Setting -> EDA Tool Setting -> Simulation、で、"Tool name"を<none>に変更

まとめ

この記事では結果だけ書いたのでさくさくすすんでいるように見えますが、各項目解決するまで1−2時間悩んだり、検索したり、試行錯誤したりを繰り返しました。大変でしたが、これでどうにか、参考書として使っている「FPGAボードで学ぶ組込みシステム開発入門 Altera編」の第5章までUbuntu16.04-64bitとQuartus II 13.1の組み合わせで進むことができました。

まだModelsimを試していないのでこの後もどんなトラップが待ち受けているのかドキドキです。

*1:配達時のトラブルで一つ注文したはずのものがなぜか2つ手に入りました。ひとつは未使用

Raspberry Pi用Haribote OSの変更箇所2 - タスクスイッチ

本稿について

先日Githubに公開したラズベリーパイ用Haribote OSについてオリジナルのX86版からの変更箇所解説2回目です。齢のせいか、たったの一月で何をやったのかどんどん忘れて来ているので、なるべく急いで進めて行こうと思います。今回はタスクスイッチです。

ラズベリーパイ用Haribote OS (RPiHaribote)はこちらに公開してあります
github.com

関連記事はこちら
uzusayuu.hatenadiary.jp
uzusayuu.hatenadiary.jp
uzusayuu.hatenadiary.jp


注意事項:あくまで筆者にとってOS開発は趣味の範疇の上に勉強中の身のため、内容については不正確な点もあると思います。そのような点が見つかった場合の指摘、または、さらによい方法の提案などしていただける場合は、喜んで参考にさせていただきます。なお、本記事はあくまで上記プログラムの解説であり、ARMの解説記事ではありません。また、記事の内容の正確性や実機での動作の再現性についてはいずれも保証できませんし、本記事の内容を使って起こるいかなる損害についても責任をもちません。

オリジナルのHariboteのタスクスイッチ

元々の「30日でできる!OS自作入門」では、タスクスイッチにはTSS(タスク状態セグメント)という仕組みを使っています。

struct TSS32 {
    int backlink, esp0, ss0, esp1, ss1, esp2, ss2, cr3;
    int eip, eflags, eax, ecx, edx, ebx, esp, ebp, esi, edi;
    int es, cs, ss, ds, fs, gs;
    int ldtr, iomap;
};

これはタスクの情報とレジスタの内容を保存した構造体で、これをセグメントとして設定しておき、そこにジャンプすることで対象のタスクにスイッチできます。タスクの情報、レジスターの内容は自動でこの構造体から読み込まれ、セグメントもスタックも切り替えが行われ、CPUのステートも自動で変わります。(便利ですね。)
ラズベリーパイで使われているARMv6でもこういった仕組みがあるのかなと思って探してみたのですが見つかりませんでした。ということは、レジスターの値の待避と読み込みCPUのステートの変更はOSが行う必要があります。OS自作入門の中にセグメント切り替えに関して、

ちなみに、タスク切り替えは最初からTSSを使ってやりましたが、あれもTSSを使わないでやる方法があります。その場合は、これくらいに大変になります。

という記述がありますが、ラズベリーパイでは「これくらい」(セグメント切り替えをソフトウェアでやるくらい)大変になるわけです。(他にもっと楽な方法があるようなら教えていただければ感謝します)

RPiHariboteのタスクスイッチ

PCB (Process Control Block)

ARM社の「ARMコンパイラツールチェーン」という文書を見ると、「6.17 コンテキストスイッチ」という項があり、ここでPCB(Process Control Block)という物を使ったコンテキストスイッチが紹介されています。ページにでかでかとSupersededと書かれていますが、他に良い方法が見つからなかったのでより良い方法が見つかるまではこちらを参考にして進めます。

まず、以下のような構造体を作りました。名前はTSS32を流用していますが、元のHaribote用のTSS32とはまったく違う物です。

struct TSS32 {
	uint32_t	cpsr,	pc,	r0,	r1;
	uint32_t	r2,	r3,	r4,	r5;
	uint32_t	r6,	r7,	r8,	r9;
	uint32_t	r10,	r11,	r12,	sp;
	uint32_t	lr,	sp_svc,	sp_sys,	sp_usr;
	uint32_t	run_flag,	vmem_table;
};

意味は以下の通りです

  • cpsr: プロセスのCPSR(Current Processor Status Register: プロセッサーの状態の納められた特殊レジスタ)の値を保存するのに使う
  • pc: 対応するプロセスの中断したプログラムのアドレス+4*1
  • r0 - r12、sp, lr : レジスタの保存用です。(ここまでPCB。これ以降はプロセス管理に関わる情報)
  • sp_svc: スーパーバイザーモード用スタックポインタ。タスク切り替え時には使わない
  • sp_sys: システムモード用スタックポインタ。タスク切り替え時には使わない。*2
  • sp_usr: ユーザーモード用スタックポインタ。タスク切り替え時には使わない。*3
  • run_flag: アプリが動作しているかどうかのフラグ*4
  • vmem_table: 仮想テーブルのエントリー

上記でわかるように、RPiHariboteでは各プロセス毎に、システムモード用(task_aとconsoleが使用)と、スーパーバイザー用(スーパーバイザーコール時のみに使用)、ユーザーモード用(アプリケーションが使用)の3つのスタックが割り当てられています。ラズベリーパイのベアメタルプログラミングではスーパーバイザーモードを使う事が多いようですが、その場合タスク切り替え時の条件分けが複雑になるため、RPiHariboteではtask_aとconsoleはシステムモードで動作させています。

タスク切り替え

「ARMコンパイラツールチェーン」ではレジスタr12に次のPCBのポインタを代入しておくことで切り替え先のプロセスを指定しますが、RPiHariboteでは、r0を使ってPCBを指定しますタイマー割り込み時にタスクスイッチが発生すると、割り込みハンドラーから帰ってくるときに戻りに値に次のPCBの値が代入されているようにしてあります。(戻り値が0の場合はタスクスイッチせず割り込み元のプロセスに帰る)ARMのABI(Application Binary Interface: C言語などの関数との引数と戻り値に関する規約)では戻り値はr0に納められることになっているので、結果的にPCBのアドレスがr0に入ることになります。
実際にタスクを切り替えるアセンブラのルーチンは以下のようになります。なお、この部分は割り込み処理の一環としてIRQモードで処理されます。また、この処理の前にタスク切り替え以外の割り込み処理(キーボード・マウスのチェック、タイマー処理、など)があり、sp以外の汎用レジスタIRQ突入時にスタックにプッシュしてあります。

_TaskSwitchIRQ:
		str		r0, _next_pcb
		ldmia	sp!, {r0-r12, lr} 	// restore all registers at IRQ entry from sp_irq
		str		sp, _sp_save		// Save SP_irq
		ldr		sp, _cur_pcb		// load current pcb adr, sp = pcb->cpsr
		add		sp, #8			// move to PCB.r0 position
		stmia	sp, {r0-lr}^		// store all usr registers (sp_usr, lr_usr)
		mrs		r0, spsr			// 
		stmdb	sp, {r0, lr}		// spsr and return address
		ldr		r0, _next_pcb		// r0 = &pcb_b
		str		r0, _cur_pcb
// switch virtual memory table
		ldr		r0, [r0, #0x54]  	// load vmem table address
		bl		switch_vmem		// switch virtual memory table
//  retrieve next registers
		ldr		r0, _next_pcb		// r0 = &pcb_b
		add		sp, r0, #8			// move sp to PCB.r0 position
		ldmdb	sp, {r0, lr}
		msr		spsr, r0
		ldmia	sp, {r0-lr}^
		ldr		sp, _sp_save  		// retrieve sp_irq
		nop
		subs	pc, lr, #4
_sp_save:	.word	0

一つ一つ見ていきます。
まず、r0に入っている次のPCBのアドレスを_next_pcbというラベルの位置に保存します。

		str		r0, _next_pcb

次に、割り込み発生時に保存したSP以外のレジスターをIRQ用のスタックからポップして、割り込み突入時のレジスター状態を復元します。

		ldmia	sp!, {r0-r12, lr} 	// restore all registers at IRQ entry from sp_irq

IRQ用SPを一旦_sp_saveというラベルの位置に保存します。

		str		sp, _sp_save		// Save SP_irq

現在のPCBへのポインターを_cur_pcbというラベルの位置から読み出し、+8します。これでspはTSS32.r0のアドレスを示すことになります

		ldr		sp, _cur_pcb		// load current pcb adr, sp = pcb->cpsr
		add		sp, #8			// move to PCB.r0 position

割り込み元の汎用レジスターの値を_cur_pcbが示すPCB領域に書き込みます。ここで^は、ユーザーモード又はシステムモードのspとlrを書き出すことを示します。(sp, lrはIRQモードで独立していますが、システムモードとユーザーモード間では共有されます。)

		stmia	sp, {r0-lr}^		// store all usr registers (sp_usr, lr_usr)

次にユーザーモードのCPSRの値が保存されている特殊レジスタであるSPSRをr0にコピー

		mrs		r0, spsr			// 

割り込み元のプログラムアドレス+4が保存されているlrと、spsrが保存されているr0をPCBに書き込み

		stmdb	sp, {r0, lr}		// spsr and return address

これでタスクスイッチ前のレジスタが待避できました。次はスイッチ先のPCBの読み込みです。
次に、先ほど保存した次のタスクに対応するPCBへのポインターを呼び出します。

		ldr		r0, _next_pcb		// r0 = &pcb_b

現在のPCBを保存しておく_cur_pcbというラベルが示すアドレスに同じ値を保存しておきます(次回のタスクスイッチの時に参照するため)

		str		r0, _cur_pcb

ここで仮想メモリーのテーブル(TTBR)を変更します。まず、TSS32.vmem_tableをr0に読み込み、仮想メモリーテーブル変換ルーチンを呼び出します。(割り込みルーチンなどが読み込まれるアドレスはどの仮想メモリー空間でも変わらないように設定してあるので、以下の処理に影響はありません。)仮想メモリーについては以前のエントリーを参照ください。

		ldr		r0, [r0, #0x54]  	// load vmem table address
		bl		switch_vmem		// switch virtual memory table

再びspに次のPCBのアドレス+8を読み込ませ、TSS32.r0のアドレスを参照させます。

		ldr		r0, _next_pcb		// r0 = &pcb_b
		add		sp, r0, #8			// move sp to PCB.r0 position

PCBから次のpc+4、cpsrを、spsrとlrに読み込ませます。割り込みから戻る際にこれらの値はcpsrとpcに書き戻されます。

		ldmdb	sp, {r0, lr}
		msr		spsr, r0

汎用レジスターを、ユーザーモードレジスターに読み込みます。ユーザーモードのspとlrはIRQからもどる際に復帰されます

		ldmia	sp, {r0-lr}^

最初に保存しておいたIRQ用のspを読み込みます。

		ldr		sp, _sp_save  		// retrieve sp_irq

おまじない(nop)の後、IRQからユーザーモード(又はシステムモード)への復帰手順を使い、次のプロセスに移ります。

		nop
		subs	pc, lr, #4

ユーザーモードに戻る際に、先ほど読み込んだspsrはcpsrにコピーされ、spとlrはユーザーモード用の物に切り替わります。
これで、指定されたPCBの示すプロセスに復帰することができました。

タイマー割り込み以外でのタスクスイッチ

プロセスがスリープに入る場合にタイマーを待たずタスクスイッチがおきることがあります。この場合、_task_switch_asmというアセンブラのルーチンを使います。
_task_switch_asmでは、モードをIRQに切り替えて上記のタスクスイッチルーチンにジャンプしています。単純な処理なので解説は省略します。

まとめ

RPiHariboteのタスクスイッチについて解説しました。オリジナルHariboteではTSSとCPUの機能を使ってタスクスイッチしているところを、RPiHariboteではPCBとソフトウェアによって状態の待避と復帰を行っています。
短いアセンブラルーチンですが、安定して動作するようになるまでずいぶん試行錯誤を繰り返しました。現状、PCBのアドレスの保存やSPの一時保存にtextセグメント内のアドレスを使っているのがあまり好みで無いので、そのうちdataセグメントに移しておこうと思います。

*1:+4されているのは、はARMが割り込みに入るときにPC+4がLRに保存されているのでこれにあわせた

*2:アプリケーション実行中にシステムモード用スタックポインタの値を一時保存するのに使用

*3:スーパーバイザーコール中に一時的にシステムモードに移る際に、アプリケーション用のスタックポインタの値を保存しておくのに使用

*4:Hariboteではtss.ss0で判断していたが、RpiHariboteでは専用フラグをおいている

Brainf**kを直接実行するCPUを作ってみる

Brainf**kについて

先日こちらのブログを拝見しました。

itchyny.hatenablog.com

見に行ったときはLLVMについて興味があったのですが、記事中で使われているBrainf**kという言語に興味津々。恥ずかしながらこれまで存在を知りませんでした。Wikipediaによると、この言語で使われる要素は><+-.,[]だけだそうです

Brainfuck - Wikipedia

Wikipediaにのっていた例によるとHello, World!を表示するコードはこうなります。(実行部分のみ)

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

Wikipediaによると意味は以下の通り

  • +でポインタ値を+1
  • ーでポインタ値を-1
  • >でポインタを+1(一つ進む)
  • <でポインタを-1(一つ戻る)
  • [で、ポインタ値が0なら対応する]に進む
  • ]で、ポインタ値が非0なら対応する[に戻る
  • .でポインタ値を出力
  • ,で入力値をポインタ先に代入

ちょうど、久しぶりにハードウェア関係で何か遊びたいなとか、VerilogHDLでデザイン書いてみたいな(自分はVHDL派でした)、などと思っていたところなので、Brainf**kをネイティブ実行するCPUを書いてみました。

Brainf**k CPU

たぶんググったら先行事例が沢山出てくると思うので、検索とかせずに、ひたすらコーディング。しばし格闘の後、できました。

module brainfuck( clk, rst_n, pc, pc_r, op, op_en, dp, d_o, w_en, w_sel, d_i, r_en, r_sel, d_en);
  input clk, rst_n;
  output  [11:0] pc;
  input   [7:0] op;
  output  pc_r;
  input   op_en;
  output  [11:0] dp;
  output  [7:0] d_o;
  output  w_en;
  output  w_sel; // 0: mem, 1: key
  input   [7:0] d_i;
  output  r_en;
  output  r_sel; // 0: mem, 1: key
  input   d_en;
  reg [11:0] pc;
  reg [11:0] pc_i, pc_n;
  reg [11:0] dp;
  reg [7:0] d_o;
  wire r_en;
  reg pc_r, w_en, w_sel, r_en_reg, r_sel;
  reg mov, mov_dir; // mov: 0, regular, 1: [ or ]
  reg [11:0] p_cnt; //  number of parenthesis skipped
  
  reg [4:0] cur, nxt; // state machine
  reg [7:0] cur_op;
  parameter IDLE = 5'b00000, FETCH = 5'b00001, DEC = 5'b00010, MEMR = 5'b00100, MEMW = 5'b01000;
  reg pc_inc, pc_dec;
  wire mread, mwrite;
  
  // state machine 
  always @(posedge clk or negedge rst_n) begin
    if (rst_n==0)
      cur <= IDLE;
    else 
      cur <= nxt;
  end
  
  // state machine next state
  always @(cur or op_en or mread or d_en) begin
    case (cur)
      IDLE:
        nxt <= FETCH;
      FETCH:        
        if (op_en == 1) // Next ope code came in
          nxt <= MEMR;
      MEMR:
        if (mread==0 | d_en == 1'b1)
          nxt <= MEMW;
      MEMW:
        nxt <= FETCH;
      default: nxt <= FETCH; // IDLE
    endcase
  end
  
  // pc change
  always @(posedge clk or negedge rst_n) begin
    
if (rst_n==0)
    pc_i <= 0;
  else
    pc_i <= pc_n;
  end
  
  always @(pc_inc or pc_dec or pc_i) begin
    if (pc_inc==1 & pc_dec==0)
      pc_n <= pc_i + 1;
    else if (pc_inc==0 & pc_dec==1)
      pc_n <= pc_i - 1;
    else
      pc_n <= pc_i;
  end
  
  // pc_read
  always @(pc_inc or pc_dec or pc_n or pc_i) begin
    pc_r <= pc_inc | pc_dec;
    if (pc_inc | pc_dec)
      pc <= pc_n;
    else
      pc <= pc_i;
  end
  
  // Decoder for [ & ]
  always @(posedge clk or negedge rst_n) begin
    if (rst_n==0)
      begin
        mov <= 0;
        mov_dir<= 0;
        p_cnt <= 0;
      end
    else if (cur==MEMR)
      if (mov == 1)
        begin
          if       ((mov_dir==0 & cur_op==8'h91) | (mov_dir==1 & cur_op==8'h93))
            p_cnt <= p_cnt+1;
          else if (((mov_dir==0 & cur_op==8'h93) | (mov_dir==1 & cur_op==8'h91)) & (p_cnt==0))
        	    mov <= 0;
          else if  ((mov_dir==0 & cur_op==8'h93) | (mov_dir==1 & cur_op==8'h91))
            p_cnt = p_cnt-1;  
        end
      else if (d_en == 1'b1 & cur_op==8'h91 & d_i==0)
        begin
          mov <= 1;
          mov_dir <= 0;
          p_cnt <= 0;
        end
      else if (d_en == 1'b1 & cur_op==8'h93 & d_i!=0)
        begin
          mov <=1;
          mov_dir <= 1;
          p_cnt <= 0;
        end
  end
  
  // decoder for PC change  
  always @(cur) begin
    case (cur)
      IDLE:
        begin
          pc_inc <= 1;
          pc_dec <= 1;
        end
      MEMW:
        begin
          pc_inc <= (mov==0 | mov_dir==0) ? 1 : 0;
          pc_dec <= (mov==0 | mov_dir==0) ? 0 : 1;
        end
      default:
        begin
          pc_inc <= 0;
          pc_dec <= 0;
        end
    endcase
  end  
  
  always @(posedge clk or negedge rst_n) begin
    if (rst_n == 1'b0)
      cur_op <= 8'h0;
    else if (cur==FETCH & op_en==1)
      cur_op <= op;
  end
  
  // dp
  always @(posedge clk or negedge rst_n) begin
    if (rst_n == 1'b0)
      dp <= 0;
    else if (cur==MEMR & mov==0 & cur_op==8'h60)
      dp <= dp - 12'h1;
    else if (cur==MEMR & mov==0 & cur_op==8'h62)
      dp <= dp + 12'h1;
  end
  
  // r_en
  always @(posedge clk or negedge rst_n) begin
    if (rst_n == 1'b0)
      r_en_reg <= 0;
    else if (cur==FETCH & nxt==MEMR & mread)
      r_en_reg <= 1;
    else if (cur==MEMR & nxt==MEMR)
      r_en_reg <= 1;
    else
      r_en_reg <= 0;
  end
  assign r_en = (cur==FETCH & nxt==MEMR & mread) | r_en_reg;
  
  assign mread = (mov==0 & (op==8'h43 | op==8'h45 | op==8'h44 | op==8'h91 | op==8'h93)) ? 1 : 0;
 
  // data read
  always @(posedge clk or negedge rst_n) begin
    if (rst_n == 1'b0)
      d_o <= 0;
    else
      if      (mov==1)
        d_o <= d_o; // no operation. Just for readability
      else if (cur==MEMR & d_en==1 & cur_op==8'h43) // +
        d_o <= d_i + 1;
      else if (cur==MEMR & d_en==1 & cur_op==8'h45)  // -
        d_o <= d_i - 1;
      else if (cur==MEMR & d_en==1)
        d_o <= d_i;
  end
  
  // r_sel
  always @(posedge clk or negedge rst_n) begin
    if (rst_n == 1'b0)
      r_sel <= 0;
    else if (cur==FETCH & op_en==1 & op==8'h46)
      r_sel <= 1;
    else if (cur==FETCH & op_en==1)
      r_sel <= 0;
  end
  
  // write the data
  always @(posedge clk or negedge rst_n) begin
    if (rst_n == 1'b0)
      w_en<=0;
    else
      if (nxt == MEMW)
        w_en <= mwrite;
      else 
        w_en <= 0;
  end

  assign mwrite = (mov==0 & (cur_op==8'h43 | cur_op==8'h45 | cur_op==8'h44)) ? 1 : 0;
  
  // w_sel
  always @(posedge clk or negedge rst_n) begin
    if (rst_n == 1'b0)
      w_sel <= 0;
    else if (cur==FETCH & op_en==1 & op==8'h44)
      w_sel <= 1;
    else if (cur==FETCH & op_en==1)
      w_sel <= 0;
  end

endmodule

シミュレーションによる動作確認

とりあえずシミュレーションで動作確認してみます。
先ほどのHello, World!をVerilogのテストベンチが読めるように、ASCIIコードでファイルに書きます。わかりやすいように改行が入っていますが、上と同じ物です。

@00
91
91
91
93
93
93
00
43 43 43 43 43 43 43 43
91
62 43 43 43 43
91
62 43 43
62 43 43 43
62 43 43 43
62 43
60 60 60 60 45
93
62 43
62 43
62 45
62 62 43
91 60 93
60 45
93
00
62 62 44
62 45 45 45 44
43 43 43 43 43 43 43 44 44 43 43 43 44
62 62 44
60 45 44
60 44
43 43 43 44 45 45 45 45 45 45 44 45 45 45 45 45 45 45 45 44
62 62 43 44
62 43 43 44

シミュレーション実行
f:id:uzusayuu:20170306152358p:plain
わかりにくいですが、動作しました。実行結果をモニターする部分を拡大するとこんな感じです。
f:id:uzusayuu:20170306152527p:plain
ちゃんと"Hello, World!"と表示されています。

終わりに

一通りコーディングした後で検索したところ当然ながらBrainf**k CPUの先行事例は山ほどでてきましたが、自分の楽しみのためにやっているので問題ありません。次は少し時間がかかるかもしれませんが、論理合成して周辺回路と合わせてFPGA上で実行させるのを目標にしたいと思います。