Moiz's journal

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

ラズベリーパイ版Haribote OSのビルド環境とインストール方法

だいぶ間があいてしまいましたが、ラズベリーパイ用Haribote OSのビルド方法について紹介します*1

PC環境はUbuntu 16.04を想定していますが、他のバージョンのUbuntu又は、他のLinuxでも同様にビルドできると思います。

2017.10.13追記: Raspberry Pi上のStretch上で試してみたところ同様の手順でビルドできるようです。gccのバージョンは6.3.0でした。*2

 

ラズベリーパイ版Hariboteのビルド

ラズベリーパイに移植したHaribote OSはGithubに公開してあります。

github.com

”Clone or download"からzipをダウンロードします。(もちろんgitを使ってリポジトリをクローンしてもかまいません。その場合は当然ながらgitをインストールして、githubsshで接続する設定をしておく必要があります。)zipファイルは作業フォルダーに展開しておきます。Ubuntuなら右クリックから"Extract Here"で展開できます。

ビルドにはクロスコンパイル用のライブラリーが必要なのでインストールします。Ubuntuならクロスコンパイル用のライブラリーは次のコマンドで簡単にインストールできます。

sudo apt-get install gcc-arm-none-eabi

他のディストリビューションでは他の方法でインストールする必要があるかもしれません。こちらのCambridgeのOSのコースの開発環境構築方法が参考になるとおもいます。

Computer Laboratory – Raspberry Pi: Downloads

これでビルドできるはずです。やってみましょう。

展開したフォルダの最上位階層でMakeします。

make all

これで、Hariboteフォルダ内にkernel.img、binフォルダ内にアプリケーションのバイナリ(.out)ファイルが作られるはずです。

起動用SDカードの準備

次にRaspberry Piの起動用SDCARDを用意します。一旦起動したSD CARDはHariboteをビルドするたびに使いまわしができるので、この項はSD CARD毎に一回やっておけばすみます。

Raspberry Piは以下のファイルをブートローダーとして使用します。RPiHariboteではいずれもRaspbianなどの起動フォルダに含まれているものを流用します。

bootcode.bin

start.elf

これらのファイルがkernel.imgをロードして OSが立ち上がります。RPiHariboteはこのkernel.imgを置き換えることで起動します。

まずSDCARDを用意します。容量はRaspbianがインストールできるサイズ(4GB程度以上のSD/SDHC)なら問題ありません。また、Zeroで動作させる場合はMicro SDを使用します。Raspbianをインストールする際にデータはすべて消えてしまうので、それでも構わないSDCARDを使用ください。

次にRaspbianのツールを用いてRaspbianをSDCARDにインストールします。こちらにオフィシャルのインストラクションがあります。

www.raspberrypi.org

イメージのダウンロードはこちらです。Raspbian自体は使わないので、今回はサイズの小さいRaspbian Stretch Liteをダウンロードして、解凍します。

Download Raspbian for Raspberry Pi

同様にEtcherをダウンロードして、解凍して実行します。

etcher.io

先ほど解凍したRaspbian Liteのイメージ(今回の場合"2017-09-07-raspbian-stretch-lite.img")を選択し、対象のSDCARDが選択されていることを確認したら、Flashをクリック。

f:id:uzusayuu:20170910034749p:plain

ここまではRaspbianの起動ディスク作成と同じですので、もし何か上手く動作しない場合はWebを検索すればいくらでも情報が出てくると思います。

次の項に進む前にいったんこの状態で起動し正常に動作することを確認しておきます。一度起動させて置かないと正常にHariboteが動作しないようです。

インストール

作成した起動ディスクのBootフォルダの方の中身をみてみると、kernel.imgというファイルがあります。ラズベリーパイ用Hariboteはこのファイルを置き換えることで実行されます。

まず、もともとのkernel.imgをkernel.bakなどにリネームします。

次に、先ほどビルドしたフォルダから haribote\kernel.imgをここにコピーします。(最上位階層のkernel.imgはgithubからダウンロードしたものです。これでも動作はしますが、先ほどビルドしたものとは異なります)。

次に、bin\以下のファイルをkernel.imgと同じフォルダにコピーします。アプリケーションの.outファイルも、アプリケーション内で使用するデータ類(.org, .fnt, .txt)もすべてコピーします。結果はこのようになると思います。

f:id:uzusayuu:20170910040644p:plain

もし、config.txtに何か設定が必要な場合は設定しておく必要がありますが、ほとんどの場合はそのままで良いと思います。*3

あとは、SD CARDをイジェクトして、対応しているラズベリーパイ(Model B+、又はZero。他の機種では動作確認されていない)に差し込み、起動。うまく行けばすぐにコンソールが表示されるはずです。

f:id:uzusayuu:20170909134412j:plain

 これで、Raspberry Pi用のHariboteをビルドして実行できました。

 

 

 

 

 

*1:実をいうと最近Linuxの環境を別のPCに移したので環境再構築の備忘録なのですが

*2:以前Jessie上で試した時はエラーがでてコンパイルできなかったように記憶しています。何か変わったのかもしれません

*3:私の環境ではconfig.txtにディスプレイの設定を加えないと綺麗に表示されないが、これはディスプレイが特殊なため

Brainf**k CPU でマンデルブロー集合を試してみた

FPGA上で動作するBrainf**k CPUを使ってマンデルブロー集合を表示させてみる

Brainf**kで書いたマンデルブロー集合を計算するプログラムがある、と聞いてずっと自作のBF CPUで動作させたいと思っていました。HDLを改造することで動作させることに成功したので、紹介します。

f:id:uzusayuu:20170529031603j:plain

変更点

Brainf**kでマンデルブルロー集合を計算するプログラムはこちらのものを使用

Index of /brainfuck/utils/mandelbrot

作者はErik Bosman氏だとクレジットがありますが、氏のホームページやオリジナルのリポジトリなどは見つかりませんでした。ちなみにコードの抜粋はこんな感じです。

A mandelbrot set fractal viewer in brainf*** written by Erik Bosman
+++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+
<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>

こちらのプログラムは約12KBですが、BF CPUは4Kまでのプログラムしか保存できないので、ROM容量を16KBまで増やしました。Brainfu**kのコードをROMのデータ(MIF形式)に変換するツールtxt2mifも16KB対応にしました。

また、Manderblot.bの出力は128x48文字ありますが、BF CPUが動作するDE0の液晶には16x2文字しか表示できないので外部に出力させる必要があります。そのため、UART出力(TXDのみ)をVerilo-HDLで実装し、PCのコンソールに表示できるように変更しました。

 

f:id:uzusayuu:20170529031111j:plain

今回の変更点はgithubリポジトリーに反映させてあります

github.com

結果

シミュレーションによる検証をへて、実機で動作させたところ一回目のテストで実行できました。(検証大事!超大事!) 

www.youtube.com

これでも50MHzで動作して、ほぼ毎クロックに1コマンド実行しているはずなんですが、いやはや、遅いですね。

まとめ

Brainfu**kを直接実行するCPUをFPGA上で動作させて、マンデルブロー集合を計算し、UART経由でPCのコンソール上に表示させました。内容はすべてGithubで公開しています。

これでBrainf**k CPUでやりたかったことは一通り終わりましたが、何か思いついたらまたやってみようと思います。

 

 

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を参照ください。