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つ手に入りました。ひとつは未使用