FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (10. 高速パスベースニューラル分岐予測器)

プロセッサアーキテクチャについて再度復習その10。ニューラル分岐予測器の続き。

  • A Survey of Techniques for Dynamic Branch Prediction
    • Sparsh Mittal

https://arxiv.org/pdf/1804.00261.pdf

パーセプトロン分岐予測器に対して、そのレイテンシの問題を改良した「高速パスベースニューラル分岐予測器」について論文を読む。 最初は何のことかわからなかったけど、しっかり読んでみると確かに面白いアイデアだなと思う。


論文 : Fast Path-Based Neural Branch Prediction

ニューラルネットワークに基づくマイクロアーキテクチャの分岐予測は、近年注目を集めている。 しかし、従来の分岐予測器よりも優れた精度というだけでは、高いレイテンシによるコストを相殺するにはまだ不十分であり、ニューラル予測は実用的ではない。 本論文では、両方向から問題を解決する新しいニューラル分岐予測器を提案する。これは、以前のニューラル予測器よりも正確ではるかに高速です。 分岐予測器は、パスとパターン履歴を組み合わせて、以前の分岐予測器に固有の制限を克服することにより精度を向上させる。 また、以前のニューラル予測よりもレイテンシがはるかに短くなる。 その結果、従来の分岐予測器よりもはるかに優れた精度を備えた分岐予測器がであり、またレイテンシはインダストリアルな分岐予測器に匹敵します。 私たちのシミュレーションは、パスベースのニューラル分岐予測器が、アグレッシブに高速化されるマイクロアーキテクチャのサイクルごとの命令(IPC)レートを元のパーセプトロン分岐予測器よりも16%向上させることを示している。

3. パスベースのニューラル分岐予測器

本節では、これまでのニューラル分岐予測器について簡単にレビューを行い、パスベースのニューラル分岐予測器について直感的な動機を与える。その後、パスベースのニューラル分岐予測器について詳細を説明する。

3.1 パーセプトロンを用いた分岐予測器

パーセプトロンの学習を用いたパーセプトロンの分岐予測器は、条件分岐命令における分岐の方向を予測するために使用される。まずは、パーセプトロン分岐予測器の設計について、Algolライクな疑似コードを用いて説明する。

パーセプトロンの分岐予測器は、グローバル履歴を保持するためのシフトレジスタを持っており、実行された分岐の結果を保持しているという面では他の分岐予測器と同一である。

パーセプトロンの分岐予測器は、n\times (h+1)ビットの整数重みビットW[0..n-1, 0..h]を保持している。nは設計におけるパラメータである。重みは通常8ビットである。行列の行は(h+1)長であり、重みベクトルと呼ばれる。各重みベクトルは1つのパーセプトロンの重みを保持しており、この単位でパーセプトロンの学習が行われる。重みベクトルw[0..h]では、最初の重みw[0]はバイアスである。BooleanベクトルG[1..h\in {1..h}\times {\text{taken}, \text{not taken}}]が、グローバル履歴レジスタである。

3.1.1 予測とアップデートのアルゴリズム

図2では、オリジナルのパーセプトロンの分岐予測器についての疑似コードを示している。予測アルゴリズムはアドレスpcに対してBooleanの値を返す。

分岐の結果が分かれば、学習アルゴリズムが動作し分岐予測がアップデートされる。トレーニンアルゴリズムは整数パラメータ\thetaが渡さる。\thetaはロングた無の精度とフェーズ動作のトレードオフのための値であり、\theta = \lfloor 1.93h + 14\rfloor が最適な値であると言われる。したがって、\thetaは履歴長によって与えられる固定値である。一度分岐の結果が分かると、パーセプトロン分岐予測器がアップデートされる。

f:id:msyksphinz:20190807010920p:plain
本論文より抜粋

3.1.2 実装

パーセプトロン分岐予測器の実装方法についていくつか検討した。

行列 Wはタグのないダイレクトマップメモリとして実装した。 n個のブロックを持ち、 i番目のブロックには h個の8ビットの重みベクトルが格納されている。したがって、分岐予測が必要な時には、アドレスpcに該当するメモリブロックが呼び出される。

重みデータの符号を反転させる必要がある場合、ビット全体のビット反転に置き換えても性能に対する影響はあまりない。これにより予測の計算に必要なレイテンシを削減することができる。

 y_\text{out}の計算にはWallaceツリーの加算器を使用した。通常の加算器を用いると O(h)の遅延が必要だが、 O(\log h)の遅延で完了させることができる。

3.1.3 パーセプトロンベースの分岐予測器の弱点

パーセプトロン分岐予測器の弱点はその長いレイテンシである。高速な演算器を使用しても、 y_\text{out}の計算に必要なレイテンシは、一般的な不快パイプラインを持つマイクロアーキテクチャに必要な演算回路のレイテンシよりも長くなる。このようなパイプラインでは、分岐予測器の性能が非常に重要[8]で、レイテンシを隠ぺいするために特殊な方法が使用されている[7]。

3.2 パスベースのニューラル分岐予測器

パーセプトロン分岐予測器の代替手法として、ニューラル分岐予測器を提案する。この分岐予測器は重みベクトルの選択を分岐のパスに応じて選択する。これまでは分岐アドレスのみに基づいて重みを選択していたが、これよりも分岐の精度を高めることができる。この手法は2つの利点を持つ。まず、 y_\text{out}の計算は分岐予測よりも前に完了するためレイテンシを短縮できる。また、パスの要素が実行されると、すぐに次のステップに進むことができる。次に、分岐予測器にパスの情報が埋め込まれるので、予測精度を向上させることができる。

3.2.1 直観的な説明

新しい分岐予測器の構成は、パーセプトロン分岐予測器の構成と非常に似ている。行列 Wに重みベクトルを保持し、分岐命令がフェッチされて分岐予測が必要な場合、1つの重みベクトルが Wから読み込まれる。しかし、0番目の重み、つまりバイアス重みのみが現在の分岐予測に使用さえっる。最後の h回の分岐に基づいて分岐予測の加算が行われ、各課sんは前の分岐予測の最中に実行される。

図3はパーセプトロン分岐予測器(a)と新しい分岐予測器(b)の違いを示している。この図では、2つの分岐予測器が分岐 b _ {t-7}から b_tまでを通過するにあたり、どのように予測を行っているかを示している。縦の軸は各ステップにおいてアクセスされる W要素を示している。各予測器は分岐履歴を h=7まで保持できる。各予測では、分岐 b_tの予測に使用される重みは x[0..7]である。パーセプトロン分岐予測器は、時間 tにおいてベクトルにアクセスし、各重みを足し合わせて一度に y_outを計算する。一方で、新しい分岐予測器の x[0..7]の重みは、これまでの分岐 b _ {t-7}から b_tに関連づいた主mいの要素によって組み立てられる。阿多アリ氏分岐予測器では、 y _ {out}の計算中にその被加数は保持される。時間 tにおいて、残りの被加数は重みバイアス x[0]のみである。分岐 b _ {t-i}によって生成された予測は、 b_tにとっては i番目に最近の投機ヒストリビットであることに注意する。図3では、重みの位置 y[0..7]と z[0..7]は過去の分岐 b _ {t-1} b _ {t-2}の計算に使用されていることに注意する。

f:id:msyksphinz:20190807010949p:plain
本論文より抜粋

2つの分岐予測器のもう一つの違いは、予測に使われる重みの探索である。オリジナルのパーセプトロン分岐予測器では、重みベクトルの各重みは b_jに属しており、 b_tの予測に使用されている。新しい分岐予測器では、 b_jのためにフェッチされた重みベクトル b_j i番目の重みは、分岐 b _ {i+j}の予測のために使用されるということである。

3.2.2 予測アルゴリズム

図4は現在の分岐と以降の h個の分岐を予測してアップデートするためのアルゴリズムを示している。 W, n, hはこれまでに定義した。 SR[0..h]と R[0..h]を、 h+1個の整数のベクトルとする。 Wの最初のカラムはバイアス重みである。 SR[h-j]には現在のものから j番目に後の分岐予測に使用される被加数である。 SRは投機的アップデートされる。 Rはアップデートアルゴリズムにて説明するが、投機的でない SRの値を保持している。 SRは部分和を保持するためのキューであると考える。

3.2.3 アップデートのアルゴリズム

パスベースのニューラル分岐予測器の更新は、概念的には元のパーセプトロン分岐予測器の更新に似ている。 ただし、新しい更新アルゴリズムは、各重みベクトルが元の分岐予測器のように1つの分岐ではなく、複数の分岐 hに関連付けられているという事実に対処する必要がある。 分岐 b_tが完了し、その結果を使用して分岐予測器を更新する準備ができている場合、 b_tに関連付けられている重みベクトルのほとんどは、まだ完了していない将来の分岐を予測するために使用されるため、更新できない。 したがって、行列 W h+1個の独立にアドレス指定可能な高速メモリとして設計する。分岐予測器が更新されると、対応する重みに個別にアクセスできる。 バイアスの重みを持つメモリは、低レイテンシで最終的な y _ {out}値を計算する論理に最も近い場所に位置される。

f:id:msyksphinz:20190807011012p:plain
本論文より抜粋
f:id:msyksphinz:20190807011029p:plain
本論文より抜粋

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (9. パーセプトロン分岐予測器の論文を読む2)

プロセッサアーキテクチャについて再度復習その9。ニューラル分岐予測器。

  • A Survey of Techniques for Dynamic Branch Prediction
    • Sparsh Mittal

https://arxiv.org/pdf/1804.00261.pdf

その2回目。パーセプトロン分岐予測器の実装について。 調査したのは上記の論文にも引用されている原文"Dynamic Branch Prediction with Perceptrons"である。

https://www.cs.utexas.edu/~lin/papers/hpca01.pdf


論文 : Dynamic Branch Prediction with Perceptrons

6. 実装

ここでは、効率的な分岐予測器を実装する方法について提案する。

f:id:msyksphinz:20190807002157p:plain

パーセプトロンの出力の計算

パーセプトロンの入力としては-1と1しか取り得ないため、内積の計算には乗算器は必要ない。その代わりに入力ビットが1である場合は加算し、-1であれば減算を行えばよい。この計算は乗算回路に似ている。1ビット毎の整数で計算される部分積を足し合わせて乗算の値を作る操作に似ている。さらに、予測には最上位の符号ビットのみ不要なため、出力の他のビットは予測の出力ほど高速に計算する必要はない。

学習

3.3節の学習のアルゴリズムはハードウェアにより効率的に実装できる。ループイタレーション内での依存関係が存在しないので、すべてのループは独立に並列に実行できる。x_itは-1もしくは1であるため、ループの本体は「t=x_iならばx_iをインクリメントし、そうでなければデクリメントする」という簡単な実装に変換することができる。また、w_iは最大でも9ビットであるので:

for each bit in parallel
  if t = xi then
    wi := wi + 1
  else
    wi := wi  - 1
  end if

遅延

0.25umプロセスにおいて54\times 54の乗算器は2.7nsの速度で実装される。これは700MHzの動作周波数において2サイクル程度に相当する。より履歴長が長くなると、我々の実装は54\times 54の乗算器の実装に似てくる。ただし、データ相関のための部分積は最大で9ビットである。したがって、乗算回路に少なくとも1つ必要なキャリー伝搬加算器はそれほど深くする必要はない。我々の分岐予測器において、多くのハードウェアを使用するような実装である場合は最大でも2サイクルで予測を生成できる。ハードウェアのサイズを小さくすると、1サイクルで予測を生成できる。2サイクルは可変長パスの分岐予測器に要求されるサイクル数である[23]。遅延を削減するために、ハードウェアのパイプライン化を提案している。

Jimnezらの研究では、分岐予測器の遅延を削減するためにのいくつかの技法を提案している[13]。もし分岐命令がパーセプトロンが予測する前に到達した場合、もしくは予想した分岐アドレスが実際には誤っていた場合、小さなgshareのテーブルにより高速な分岐が行われる。2つのgshareテーブルを使用した似たような分岐予測器は、大きな分岐予測器を1つ使う場合に比べて47%高速化される。

TensorFlow Lite on RISC-Vの論文を読む

知り合いの人からCARRV 2019 (Third Workshop on Computer Architecture Research with RISC-V)でTensorFlow Lite on RISC-Vの発表があったと聞いたので、さっそく論文をダウンロードしてみた。

carrv.github.io

https://carrv.github.io/2019/papers/carrv2019_paper_7.pdf

きちんと読んだわけではなく流し読みなので、詳細まで把握したわけではないけれど、ざっと流し読みをした。

この人たちは、TensorFlow LiteをRISC-Vアーキテクチャで動かすために、まずはRISC-Vのベクトル命令をTensorFlowのソースコードに移植した。 次に命令セットシミュレータを拡張してDeep Learningのテストパタンを動かし、ARMと比べてどの程度の性能が出たのか調査した。

まず、

  1. Intrinsicを使って、TensorFlowのコードでRISC-Vのベクトル命令に変換できるところを書き直した。以下の表に示すベクトル命令を用いて移植を行った。
f:id:msyksphinz:20190808231708p:plain
RISC-V移植のために使用したベクトル命令。

どうもTensorFlow Liteにはreference_optoptimized_optという2つのソースコードの分類があって、

  • reference_optはポータブルな実装、つまり汎用命令しか使ってはいけないのかな?
  • optimized_optはハードウェア実装に依存した実装にしてよい。つまりアクセラレータとか使っても良いのかな?

という分類らしい。

まずはソースコード移植 → コンパイル → シミュレータでシミュレーション(Spike-ISSを改造) → 実行命令数比較

となるらしい。まだ現物のハードウェアで実行したわけではなさそうだから、Commited Instruction、つまり命令数での比較となっている。 命令数比較ならば、ベクトル命令を導入すれば命令数としては短くなるのは当たり前で、その比較はどうだろう...?という気分になる。

f:id:msyksphinz:20190808233104p:plain
TensorFlow Lite on RISC-Vの移植フロー

その結果、最適化をすると命令数的にはARMに勝った。そりゃそうだろ。命令数だもん。

f:id:msyksphinz:20190808233230p:plain
ARMとRISC-VのTensorFlow Liteの実行命令数比較。

とりあえず、移植できたというのは大きな成果なのかなという印象。あとは、

  • 現物ハードウェアで動作させる。
  • 性能を上げる

といったところが課題かな。

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (8. パーセプトロン分岐予測器の論文を読む)

プロセッサアーキテクチャについて再度復習その8。今回からニューラル分岐予測器。

  • A Survey of Techniques for Dynamic Branch Prediction
    • Sparsh Mittal

https://arxiv.org/pdf/1804.00261.pdf

で、パーセプトロン分岐予測器なんて勉強したこともなかったので、サーベイ論文ではなく原文に当たることにした。 調査したのは上記の論文にも引用されている原文"Dynamic Branch Prediction with Perceptrons"である。

https://www.cs.utexas.edu/~lin/papers/hpca01.pdf


論文 : Dynamic Branch Prediction with Perceptrons

3. パーセプトロンを用いた分岐予測器

本セクションでは、我々の分岐予測器を理解するために必要なバックグラウンドについて説明する。パーセプトロンについて説明し、どのように我々の分岐予測器に使用するのかについて説明する。また、この分岐予測器の利点と欠点について説明する。我々の手法は、基本的に2レベル分岐予測器であり、パタンヒストリテーブルをパーセプションのテーブルに置き換えるだけである。

3.1 なぜパーセプトロンなのか?

パーセプトロンは、分岐予測器において自然な選択肢であり、その理由はパーセプトロンは効率的にハードウェアに実装吸うことができるからである。ニューラルネットワークのそれ以外の形態としては、バックプロパゲーションや、決定木などの機械学習向けの手法として利用されているが、実装コストが大きすぎるために適切ではない。この論文では、ADALINE[25]やHebb learning[8]などの他のシンプルなニューラルアーキテクチャについても検討したが、パーセプトロンが最も効率が良かった(ADALINEはハードウェアの効率が悪く、Hebbは精度が低い)。

パーセプトロンの一つの利点は、ハードウェアが学習した値の相関などの「重み」などの値を調べることによって、ハードウェアが生成した予測の意味を簡単に理解できるからである。対照的に、ニューラルネットワークの多くの形式の弱点んは、ニューラルネットワークが予測を行うまでに、どのようにして決定したかを理解するのが困難なことである。ニューラルネットワークからルールを抽出する技術も提案されている[21]が、その制度はあまり高くない。パーセプトロンはこのような不透明性が発生しない; パーセプトロンの決定プロセスは、簡単な数式により理解することができる。この特徴については、5.7章で議論する。

3.2 パーセプトロンはどのように働くのか

パーセプトロンは1962年に提案された、脳の学習機能を模擬した手法である。ここでは、最もシンプルなパーセプトロン[2]である「単一レイヤ パーセプトロン」を使用する。単一レイヤパーセプトロンでは、1つの人工ニューロンと、複数の入力ユニットと、1つの出力ユニットを持っている。我々の用途では、重みは符号付きの整数である。出力は重みベクトル w _ {0..n}と入力ベクトル x_{1..n}内積である( x _ 0は常に1であり、「バイアス値」を入力している)。パーセプトロンの出力 yは以下のようにして計算できる :

 y = w_0 + \sum_{i=1}^n x_iw_i

パーセプトロンの入力はバイポーラであり、つまり各 x _ iは-1あるいは1であり、それぞれ分岐しない、分岐するに相当する。パーセプトロンにおいて負数は分岐しないと予測したことを意味し、正数は分岐すると予測したことを意味する。

f:id:msyksphinz:20190807002716p:plain
図1. パーセプトロンモデル。入力値 x _ {1}, ... x _ {n}は重みを通じてパーセプトロンに接続され、内積が計算される。 w_0はバイアスに対する重みである。(本論文より抜粋)

3.4 パーセプトロンの学習

パーセプトロンの出力が一度計算されると、以下のアルゴリズムによってパーセプトロンが学習される。分岐が成立しなかった場合は t=-1とし、分岐が成立した場合は t=1とする。 \thetaスレッショルドであり、学習アルゴリズムによって学習がどれくらい十分に完了したかを示している。

if sign(y_out) != t or |y_out| <= theta then
  for i:= 0 to n do
    w_i := w_i + t*x_i
  end for
end if

 t x_iは常に-1か1のため、このアルゴリズムでは分岐の結果が x_iと合致した場合に i番目の重みがインクリメントされ、そうでない場合はデクリメントされる。緒間的には、全体的に合致する、つまり正の相関がある場合は値が大きくなる。そし、全体的合致しない、つまり負の相関がある場合は、値が小さくなる。どちらの場合でも、重みの値は予測に対して大きな影響を与える。これらに対して弱い相関がある場合は、重みの値はは0に近づき、パーセプトロンの出力に対する影響度が落ちていく。

3.4 線形分離可能性

パーセプトロンの制約は、「線形分離可能」な関数に対してのみ学習が可能であると言う事である[8]。つまり、 n次元の空間に対するすべてのパーセプトロンの入力を想像すると、そのときの学習結果の解は以下の式で示される「超平面」(例えば、 n=2の場合は直線)により入力に対するパーセプトロンの答えが「False」と「True」に分離できる直線となる。

 w_0 + \sum_{i=1}^n x_iw_i = 0

Boolean関数に対して x _ {1..n} Trueの領域とFalseの領域を分離することができる w _ {0..n}が存在する場合、それは「線形分離可能」であるという。パーセプトロンの出力は上記の等式によって決定されるため、線形分離可能な関数しか学習することができない。例えば、パーセプトロンは2つの入力に対するANDは学習することができるが、XOR関数は学習することができない。何故ならばXORは線形分離可能ではないからである。

後で紹介するように、プログラム中の分岐の動作に関する多くの関数は線形に分離可能である。また、パーセプトロンを時間とともに学習させるため、非線形なものに対しても適用可能であるが、その制度は100%ではない。対照的に、gshareのような2レベルのPHTでは、十分にトレーニング時間を取ればどのようなBoolean関数に対しても学習可能である。

3.5 まとめ

パーセプトロンを利用して、特定の分岐の結果について、グローバル履歴と現在の分岐から相関を学習することができる。これらの相関は重みとして表現される。重みが大きいと相関が強く、グローバル履歴中のとある分岐が、これから予測すべき分岐の予測に対して強い相関があることを示している。

図2はパーセプトロン分岐予測器のブロックダイアグラムを示している。プロセッサは高速SRAM中にN個のパーセプトロンのテーブルを保持している。これは他の分岐予測手法に置け®う2ビットカウンタと同じような立ち位置である。パーセプトロンの数 Nはハードウェアの面積、重みの数つまり何個の分岐履歴を記憶しておけるかによって決定される。特殊な回路が yの値を計算し、学習を行う。フェッチステージにおいてプロセッサが分岐命令に遭遇すると、以下のステップが実行される。

  1. 分岐アドレスがハッシュ化され、インデックス i (0 .. N-1)が生成される。
  2.  i番目のパーセプトロンがテーブルからフェッチされ、ベクトルレジスタ P _ {0..n}の重みとしておかれる。
  3.  y Pとグローバル履歴レジスタ内積として計算される。
  4.  yが負の数ならば分岐しない、 yが正の数ならば分岐すると予測する。
  5. 実際の分岐結果が判明すると、学習アルゴリズムが動作して重み Pの値を学習する。
  6.  Pの値は i番目のテーブルに格納される。

SRAMトランザクションと多くの計算が必要であるため、予測の速度は遅く、1ステップから5ステップ程度必要である。しかし、第6節ではいくつかの数学的かつマイクロアーキテクチャのトリックを用いて、長い履歴長でも予測を1サイクルで行うことができる手法を提案する。

f:id:msyksphinz:20190807002127p:plain
図2. パーセプトロン分岐予測器のブロック図。分岐アドレスはハッシュ化されテーブルからのパーセプトロンの選択に使用される。グローバル履歴レジスタと合わせてパーセプトロンの出力が計算され、分岐の予測が生成される。パーセプトロンは学習アルゴリズムによりアップデートされ、テーブルに書き戻される。(本論文より抜粋)

System Verilogで記述されたRISC-VコアArianeを試す (1. ビルドとシミュレーション)

Arianeは、System Verilogで記述されたインオーダの6ステージRISC-Vパイプラインプロセッサだ。

RISC-Vコアとしてはそこまで性能が高いわけではないが、多くのコンポーネントがSystem Verilogで記述されているということでハードウェア技術者にとっても解析しやすいし、RISC-VのOpenHW Groupでもサポートが行われる予定だということで、長らく標準的なRISC-Vコアとして使用される可能性があると思っている。

github.com

www.openhwgroup.org

https://github.com/msyksphinz/ariane/raw/master/docs/img/ariane_overview.png

まずは、Arianeを使ってどのようにハードウェアシミュレーションを行うのかチュートリアルを行ってみることにした。

まず、GitHubからArianeをダウンロードする。

git clone https://github.com/msyksphinz/ariane.git --recurse-submodules
cd ariane

RISCV環境変数を設定しておくこと。 - デザインのコンパイルを行う。Verilatorを使う。

make verilate
  • VCDを出力するときは、DEBUG=1を指定すること。
make verilate DEBUG=1

シミュレーションを行う際は、テストパタンを指定する。

./work-ver/Variane_testharness ${RISCV}/riscv64-unknown-elf/share/riscv-tests/isa/rv64um-v-divuw

また、VCDを生成する場合は-vオプションで出力VCDファイルを指定する。

./work-ver/Variane_testharness -v rv64um-v-divuw.vcd ${RISCV}riscv64-unknown-elf/share/riscv-tests/isa/rv64um-v-divuw

VCDをGTKWaveで確認した。このようにして波形を確認できる。

f:id:msyksphinz:20190804203845p:plain
GTKWaveで確認したシミュレーション結果

LLVMのバックエンドを作るための第一歩 (50. 浮動小数点レジスタ向けのCalling Conventionの追加)

f:id:msyksphinz:20190425001356p:plain

浮動小数点演算命令を使った算術演算は生成できるようになったが、まだ関数の引数として浮動小数点型を使用することができない。 これは、MYRISCVXのCalling Conventionに、浮動小数点を追加していないからだ。

RISC-VのCalling Conventionでは、浮動小数点の関数の引数渡しは整数と同様に定義されている。

Name ABI Mnemonic Meaning Preserved across calls?
f0-f7 ft0-ft7 Temporary registers No
f8-f9 fs0-fs1 Callee-saved registers Yes*
f10-f17 fa0-fa7 Argument registers No
f18-f27 fs2-fs11 Callee-saved registers Yes*
f28-f31 ft8-ft11 Temporary registers No

上記の通り、浮動小数レジスタ経由の引数渡しでは、f10-f17が用意されている。戻り値はf10経由で戻せばよいだろう。 というわけで、整数レジスタのCalling Conventionと同様に、2種類のCalling Conventionを用意する。

  • lp32 : 最初の8個までの引数は浮動小数レジスタf10 - f17で渡す。それから先の引数はスタック経由で渡す。
  • stack32 : 全ての浮動小数点引数をスタック経由で渡す。

このため、MYRISCVXCallingConv.tdに記述の追加を行う。

f:id:msyksphinz:20190802231859p:plain
浮動小数点型に対するCalling Conventionの定義
  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXCallingConv.td

LP32について、f32とf64の型についての引数の情報を指定した。 f10-f17レジスタを使用するように指定し(CCAssignToReg)、残りはスタックを使用するようにする(CCAssignToStack)。

//===----------------------------------------------------------------------===//
// MYRISCVX LP32 Calling Convention
//===----------------------------------------------------------------------===//
def CC_LP32 : CallingConv<[
  CCIfByVal<CCDelegateTo<CC_MYRISCVX_ByVal>>,

  // Promote i8/i16 arguments to i32.
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // Integer arguments are passed in integer registers.
  CCIfType<[i32], CCAssignToReg<[A0, A1, A2, A3, A4, A5, A6, A7]>>,
  // Single Floating-Point arguments are passed in FP registers
  CCIfType<[f32], CCAssignToReg<[F10_S, F11_S, F12_S, F13_S, F14_S, F15_S, F16_S, F17_S]>>,
  // Double Floating-Point arguments are passed in FP registers
  CCIfType<[f64], CCAssignToReg<[F10_D, F11_D, F12_D, F13_D, F14_D, F15_D, F16_D, F17_D]>>,

  // Integer values get stored in stack slots that are 4 bytes in size and 4-byte aligned.
  CCIfType<[i32], CCAssignToStack<4, 4>>,
  // Floating-Point values get stored in stack slots that are 4 bytes in size and 4-byte aligned.
  CCIfType<[f32], CCAssignToStack<4, 4>>,
  // Floating-Point values get stored in stack slots that are 8 bytes in size and 8-byte aligned.
  CCIfType<[f64], CCAssignToStack<8, 8>>
]>;

STACK32については、すべての引数をレジスタで渡する。すべてCCAssignToStackだ。

//===----------------------------------------------------------------------===//
// MYRISCVX STACK32 Calling Convention
//===----------------------------------------------------------------------===//
def CC_STACK32 : CallingConv<[
  CCIfByVal<CCDelegateTo<CC_MYRISCVX_ByVal>>,

  // Promote i8/i16 arguments to i32.
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // Integer values get stored in stack slots that are 4 bytes in size and 4-byte aligned.
  CCIfType<[i32], CCAssignToStack<4, 4>>,
  // Floating-Point values get stored in stack slots that are 4 bytes in size and 4-byte aligned.
  CCIfType<[f32], CCAssignToStack<4, 4>>,
  // Floating-Point values get stored in stack slots that are 8 bytes in size and 8-byte aligned.
  CCIfType<[f64], CCAssignToStack<8, 8>>
]>;

戻り値については、浮動小数レジスタf10を経由して戻する。このための記述を追加する。

def RetCC_MYRISCVXEABI : CallingConv<[
  // i32 are returned in registers A0, A1
  CCIfType<[i32], CCAssignToReg<[A0, A1]>>,

  // Floating-Point are return in registers FA0, FA1
  CCIfType<[f32], CCAssignToReg<[F10_S]>>,
  CCIfType<[f64], CCAssignToReg<[F10_D]>>
]>;

これだけだ。LLVMをビルドして、サンプルプログラムを動作させてみる。以下のようなコードを考える。

  • fp_args.cpp
float test_dp_arg(float a, float b, float c)
{
  return a + b + c;
}
double test_dp_arg(double a, double b, double c)
{
  return a + b + c;
}
float test_dp_longarg(float f0, float f1, float f2, float f3, float f4,
                      float f5, float f6, float f7, float f8, float f9)
{
  return f0 + f1 + f2 + f3 + f4 + f5 + f6 + f7 + f8 + f9;
}
double test_dp_longarg(double f0, double f1, double f2, double f3, double f4,
                       double f5, double f6, double f7, double f8, double f9)
{
  return f0 + f1 + f2 + f3 + f4 + f5 + f6 + f7 + f8 + f9;
}
./bin/clang -O3 fp_args.cpp -emit-llvm
./bin/llc -filetype=asm fp_args.bc -mcpu=simple32 -march=myriscvx32 -target-abi=lp64 -relocation-model=static -o -
  • LP32の場合。test_dp_arg()コンパイル結果。floatの場合は以下のようなコードとなる。
_Z11test_dp_argfff:
# %bb.0:                                # %entry
        fadd.s  f0, f10, f11
        fadd.s  f10, f0, f12
        ret

単純に引数渡しで演算をおこない、レジスタ経由で戻り値を渡する。

  • test_dp_longarg()コンパイル結果。floatの場合は以下のようなコードとなる。
_Z15test_dp_longargdddddddddd:
# %bb.0:                                # %entry
        fadd.d  f0, f10, f11
        fadd.d  f0, f0, f12
        fadd.d  f0, f0, f13
        fadd.d  f0, f0, f14
        fadd.d  f0, f0, f15
        fadd.d  f0, f0, f16
        fadd.d  f0, f0, f17
        fld     f1, 0(x2)
        fadd.d  f0, f0, f1
        fld     f1, 8(x2)
        fadd.d  f10, f0, f1
        ret

最初の8つの引数はレジスタ経由で渡されていることが分かる。8個以降は、レジスタが足りないのでスタック経由で引数を渡している。

./bin/clang -O3 fp_args.cpp -emit-llvm
./bin/llc -filetype=asm fp_args.bc -mcpu=simple32 -march=myriscvx32 -target-abi=lp64 -relocation-model=static -o -
  • STACK32の場合。test_dp_arg()コンパイル結果。floatの場合は以下のようなコードとなる。
_Z11test_dp_argfff:
        .cfi_startproc
        .frame  x8,0,x1
        .mask   0x00000000,0
        .set    noreorder
        .set    nomacro
# %bb.0:                                # %entry
        flw     f0, 4(x2)
        flw     f1, 0(x2)
        fadd.s  f0, f1, f0
        flw     f1, 8(x2)
        fadd.s  f10, f0, f1
        ret

全ての引数をスタックに積んで渡していることが分かる。戻り値はf10レジスタを経由して戻している。

  • STACK32の場合。test_dp_longarg()コンパイル結果。floatの場合は以下のようなコードとなる。
_Z15test_dp_longargdddddddddd:
# %bb.0:                                # %entry
        fld     f0, 8(x2)
        fld     f1, 0(x2)
        fadd.d  f0, f1, f0
        fld     f1, 16(x2)
        fadd.d  f0, f0, f1
        fld     f1, 24(x2)
        fadd.d  f0, f0, f1
        fld     f1, 32(x2)
        fadd.d  f0, f0, f1
        fld     f1, 40(x2)
        fadd.d  f0, f0, f1
        fld     f1, 48(x2)
        fadd.d  f0, f0, f1
        fld     f1, 56(x2)
        fadd.d  f0, f0, f1
        fld     f1, 64(x2)
        fadd.d  f0, f0, f1
        fld     f1, 72(x2)
        fadd.d  f10, f0, f1
        ret

こちらもすべての引数をスタックに積んで渡していることが分かる。戻り値はf10レジスタを経由して戻している。

LLVMのバックエンドを作るための第一歩 (49. 浮動小数点算術演算命令の追加)

f:id:msyksphinz:20190425001356p:plain

浮動小数点のロードストア命令が生成できるようになったので、次は簡単な算術演算ができるようにする。とりあえずは、加減乗除、そして積和演算ができるようになりたい。

私たちはすでに命令定義のクラスとテンプレートを持っているので、そこに当てはめるだけで良い。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfoFD.td
def FADD_S   : ArithLogicR<0b1010011, 0b000, 0b0000000, "fadd.s", fadd, FPR_S>;
def FSUB_S   : ArithLogicR<0b1010011, 0b000, 0b0000100, "fsub.s", fsub, FPR_S>;
def FMUL_S   : ArithLogicR<0b1010011, 0b000, 0b0001000, "fmul.s", fmul, FPR_S>;
def FDIV_S   : ArithLogicR<0b1010011, 0b000, 0b0001100, "fdiv.s", fdiv, FPR_S>;

def FADD_D   : ArithLogicR<0b1010011, 0b000, 0b0000001, "fadd.d", fadd, FPR_D>;
def FSUB_D   : ArithLogicR<0b1010011, 0b000, 0b0000101, "fsub.d", fsub, FPR_D>;
def FMUL_D   : ArithLogicR<0b1010011, 0b000, 0b0001001, "fmul.d", fmul, FPR_D>;
def FDIV_D   : ArithLogicR<0b1010011, 0b000, 0b0001101, "fdiv.d", fdiv, FPR_D>;

単精度版では、使用するレジスタとしてFPR_S、倍精度版ではFPR_Dを指定した。 それぞれ、生成パタンに使用する演算としてはfadd, fsub, fmul, fdivを指定している。 これだけで、fadd.s, fsub.s, fmul.s, fdiv.s, fadd.d, fsub.d, fmul.d, fdiv.dが生成することができる。

さらに、積和演算も定義します。積和演算命令は以下のようなフォーマットになっている。

1564738842189

このフォーマットで、積和演算用の命令クラスを作成します。MYRISCVX_FMAクラスとする。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrFormats.td
//===----------------------------------------------------------------------===//
// FMA-Type instruction class in MYRISCVX : <|opcode|rd|rs1|rs2|rs3|>
//===----------------------------------------------------------------------===//
class MYRISCVX_FMA<bits<7> opcode, bits<2> fmt, bits<3> rm,
                   dag outs, dag ins, string asmstr, list<dag> pattern,
                   InstrItinClass itin>:
  MYRISCVXInst<outs, ins, asmstr, pattern, itin, FrmR>
{
  bits<5> rs3;
  bits<5> rs2;
  bits<5> rs1;
  bits<5> rd;

  let Inst{31-27} = rs3;
  let Inst{26-25} = fmt;
  let Inst{24-20} = rs2;
  let Inst{19-15} = rs1;
  let Inst{14-12} = rm;
  let Inst{11-7}  = rd;
  let Inst{6-0}   = opcode;
}

さらにMYRISCVX_FMAクラスを使いやすくした、FPMultAddクラスを作成しておく。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfoFD.td
// Floating-Point FMA instructions with 3 register operands.
class FPMultAdd<bits<7> opcode, bits<2> fmt, bits<3> rm,
                string instr_asm,
                RegisterClass RC> :
  MYRISCVX_FMA<opcode, fmt, rm, (outs RC:$rd), (ins RC:$rs1, RC:$rs2, RC:$rs3),
               !strconcat(instr_asm, "\t$rd, $rs1, $rs2, $rs3"),
               [], IIAlu> {
    let isReMaterializable = 1;
}

このテンプレートを元に、単精度用と倍精度用の積和演算命令を追加する。

f:id:msyksphinz:20190802231032p:plain
浮動小数点積和演算命令を定義するためのクラステンプレート
  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfoFD.td
//
// Single Floating Point Operations
//
def FMADD_S  : FPMultAdd<0b1010011, 0b00, 0b000, "fmadd.s",  FPR_S>;
def FMSUB_S  : FPMultAdd<0b1000111, 0b00, 0b000, "fmsub.s",  FPR_S>;
def FNMSUB_S : FPMultAdd<0b1001011, 0b00, 0b000, "fnmsub.s", FPR_S>;
def FNMADD_S : FPMultAdd<0b1001111, 0b00, 0b000, "fnmadd.s", FPR_S>;

//
// Double Floating Point Operations
//
def FMADD_D  : FPMultAdd<0b1010011, 0b01, 0b000, "fmadd.d",  FPR_D>;
def FMSUB_D  : FPMultAdd<0b1000111, 0b01, 0b000, "fmsub.d",  FPR_D>;
def FNMSUB_D : FPMultAdd<0b1001011, 0b01, 0b000, "fnmsub.d", FPR_D>;
def FNMADD_D : FPMultAdd<0b1001111, 0b01, 0b000, "fnmadd.d", FPR_D>;

さらに、これらの命令の生成パタンを追加する。FMADDに関してはfmaというパタンがあるのだが、それ以外についてはデフォルトで用意されていないので、手動で追加する。

// Floating-Point FMA pattern registration
def : Pat<(fma FPR_S:$rs1, FPR_S:$rs2, FPR_S:$rs3),               (FMADD_S  $rs1, $rs2, $rs3)                  >;
def : Pat<(fma FPR_S:$rs1, FPR_S:$rs2, (fneg FPR_S:$rs3)),        (FMSUB_S  FPR_S:$rs1, FPR_S:$rs2, FPR_S:$rs3)>;
def : Pat<(fma (fneg FPR_S:$rs1), FPR_S:$rs2, FPR_S:$rs3),        (FNMSUB_S FPR_S:$rs1, FPR_S:$rs2, FPR_S:$rs3)>;
def : Pat<(fma (fneg FPR_S:$rs1), FPR_S:$rs2, (fneg FPR_S:$rs3)), (FNMADD_S FPR_S:$rs1, FPR_S:$rs2, FPR_S:$rs3)>;

// Floating-Point FMA pattern registration
def : Pat<(fma FPR_D:$rs1, FPR_D:$rs2, FPR_D:$rs3),               (FMADD_D  $rs1, $rs2, $rs3)                  >;
def : Pat<(fma FPR_D:$rs1, FPR_D:$rs2, (fneg FPR_D:$rs3)),        (FMSUB_D  FPR_D:$rs1, FPR_D:$rs2, FPR_D:$rs3)>;
def : Pat<(fma (fneg FPR_D:$rs1), FPR_D:$rs2, FPR_D:$rs3),        (FNMSUB_D FPR_D:$rs1, FPR_D:$rs2, FPR_D:$rs3)>;
def : Pat<(fma (fneg FPR_D:$rs1), FPR_D:$rs2, (fneg FPR_D:$rs3)), (FNMADD_D FPR_D:$rs1, FPR_D:$rs2, FPR_D:$rs3)>;

ここまで出来たら、LLVMをビルドしてテストコードを流してみる。以下のようなテストコードを用意した。

  • fp_ops.cpp
#include <math.h>

void test_fp_math(float *a, float *b, float *c)
{
  float res_add = *a + *b + *c;
  float res_sub = *a - *b - *c;
  float res_mul = *a * *b * *c;
  float res_div = *a / *b / *c;

  float res_fmad  = fmaf(*a, *b, *c);
  // float res_fsub  = *a * *b - *c;
  // float res_fnmsub = (-*a) * *b + *c;
  // float res_fnmadd = (-*a) * *b - *c;
}

void test_dp_math(double *a, double *b, double *c)
{
  double res_add = *a + *b + *c;
  double res_sub = *a - *b - *c;
  double res_mul = *a * *b * *c;
  double res_div = *a / *b / *c;

  double res_fmad  = fma(*a, *b, *c);
  // double res_fsub  = *a * *b - *c;
  // double res_fnmsub = (-*a) * *b + *c;
  // double res_fnmadd = (-*a) * *b - *c;
}
./bin/clang -O0 fp_ops.cpp -emit-llvm
./bin/llc -filetype=asm fp_ops.bc -mcpu=simple32 -march=myriscvx32 -target-abi=lp32 -o -

このコードは、値は引数から取得しているが、値そのものはポインタを使用している。 何故なら、浮動小数点のCalling Conventionをここではまだ定義していないので、浮動小数レジスタ経由での値の受け渡しができないからだ。 これは、後で追加する。また、それぞれの計算結果自体はその場で捨てており、関数としてみると無駄なコードなので、最適化オプションを付けると消されてしまっている。 -O0で実行する。

生成されたアセンブリ命令を見てみる。

_Z12test_fp_mathPfS_S_:
# %bb.0:                                # %entry
        addi    x2, x2, -32
        .cfi_def_cfa_offset 32
        lw      x10, 40(x2)
        lw      x10, 36(x2)
        lw      x11, 32(x2)
        sw      x10, 24(x2)
        lw      x10, 32(x2)
        flw     f0, 0(x10)
        lw      x10, 24(x2)
        flw     f1, 0(x10)
        fadd.s  f0, f0, f1
        lw      x10, 40(x2)
        flw     f1, 0(x10)
        fadd.s  f0, f0, f1
        fsw     f0, 20(x2)
...
        fsub.s  f0, f0, f1
...
        fsub.s  f0, f0, f1
...
        fmul.s  f0, f0, f1
...
        fmul.s  f0, f0, f1
...
        fdiv.s  f0, f0, f1
...
        fdiv.s  f0, f0, f1
...
        fmadd.s f0, f0, f1, f2
...
        fmadd.s f0, f0, f1, f2

無事に浮動小数点演算命令を生成することができた。 ここでは省略しているが、倍精度命令のテストも正しく命令を生成することができている。