FPGA開発日記

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

ISCA2021のVectorization Replayに関する論文を読む (1.)

ちょっと読んでいる論文のメモ：

ieeexplore.ieee.org

SIMDアーキテクチャは、安全な場合にのみ、コードをベクトル形式に変換できる。メモリアクセスの解析能力や、メモリデータ依存が発生している場合は、コードの全領域を安全にベクトル化することが出来ない。

新しいSIMDアーキテクチャを提案する。ベクトル実行中に発生するメモリ依存の違反を特定するため、補足するためにPredictionを使用する。一度依存が発見されミスが検出されると、誤ったデータを使用したSIMDレーンのみが再生され、他のレーンは古いものも含めて最新の実行結果を維持する。依存関係のある場所についてはコンパイル時にマークを行い、安全にベクトル実行を行う。これをSelective Replay Vectorization(SRV)と名付けている。汎用ベンチマーク及びHPCベンチマークで評価したところ、ベクトル化されたコードに対して平均で2.9倍、最良のケースでは最大で5.3倍のループ速度向上が確認された。

1. Introduction

SIMDベクトル化を行うためには、周囲のメモリアクセス命令などで依存が発生しないことを保証する必要があり、そのためにSIMDを使用する際に制限が発生することがある。

既存技術：

  • FlexVec : コード実行時にメモリ依存性のランタイムチェックを追加する
  • バイナリ変換器を用いて、実行時に逐次コードを推測的にベクトル化し、チェックポイントで再開し、違反が発生するとフォールバックする。

どちらの場合も実行時にオーバヘッドが発生し、性能が低下する。

本論文では、ベクトル化されたコードの領域を投機的に実行し、アクセスされたメモリアドレスを監視して依存性の違反を特定する。依存の違反が発生したレーンのみに対してコードを再実行する。Selective Replay Vectorizationアーキテクチャを採用することにより、依存性違反の検出と修正のオーバヘッドを抑える。

2. Motivation

データの依存性が分からない場合、コードのベクトル化は失敗する。

実際にベンチマークを使って調査すると、ベクトル化されていない内部ループの70％以上はメモリの依存性を持っており、ベクトル化することが困難である。

FlexVecは、コンパイラが生成する実行時チェックを追加し、依存性違反のあるレーンまで、なるべく多くのレーンをベクトル化する。

しかしこの方法は、ランタイムオーバヘッドが大きくなる。部分的なベクトル化ではデータレベルの並列性を十分に引き出すことが出来ない。

SRVにより、これらの問題を解決する。

3. Selective-Replay Vectorization

コンパイラが推測的にコードをベクトル化した場合、データ依存性の違反を自動的に検出し、影響を受けるレーンを再実行する。ハードウェアがすべての違反を検出して解決してくれることが特徴。

図1は標準的なアウトオブオーダスーパスカラパイプラインを示している。SRVのための論理は、車線で示した部六に対して追加されている。SIMD命令は、通常通りパイプラインを進むが、各レーンの実行はSRV-Replayレジスタと呼ばれるレジスタでガードされている。

f:id:msyksphinz:20220417010451p:plain
本論文より引用

依存性違反が発生すると、その違反の種類及び不正なレーンを別のレジスタ(SRV-needs-erplayレジスタ)に記録することで解決する。ベクトル命令のシーケンスが終了すると、SRV-needs-replayレジスタは、再実行が必要なレーンに対してマークが付けられる。

A. SRV実行の有効化

SRVのベクトル化をサポートするために、新しい命令を2つ導入した。

  • SRV-start: 依存性がある可能性があるベクトルループ本体の先頭に配置される。
  • SRV-end: 依存性がある可能性があるベクトルループ本体の末尾に配置される。

この2つの命令で囲まれた領域をSRV領域と呼び、この領域にはベクトル命令のみが含まれる。

/* Read integers from the standard input. */
int *x = read();
for (i = 0; i < N; i++) {
    a[x[i]] = a[i] + 2;
}

Loop:
   srv_start
   v_load v0, a[i:i+15]
   v_add v0, 2
   scatter v0, a[x[i]:x[i+15]]
   srv_end
   inc i, 16
   comp i, N
   bne Loop

SRV-start命令により、投機実行を開始し、レーンがメモリ依存性を違反した場合、ロールバックして再実行するための必要なポイントを記録する。

  • 次の命令のPCを記録する
  • SRV-replayレジスタを初期化する
  • ロードストアキューにメモリ曖昧性解消を支持する

依存性に対して違反する可能性のあるスカラ演算については、コンパイラによってSRV領域の外に置かれるので、これらの変数が投機的に実行される事は無い(FENCEに近い役割を持つ？)

SRV領域の実行中は、各命令はSRV領域内を進んでいく。完了後にSRV-end命令実行時に、メモリ依存性の違反が無ければ、すべての投機的実行をコミットしてSRV領域の実行を継続する。しかし、不正なレーンを発見すれば、記録されたPCを使用して、SRV-start命令の直後まで命令がロールバックされ、不正なデータを使用したレーンのみを再実行する。ロールバックは、すべてのレーンが正しく実行されるまで複数回実行される可能性がある。これにより、ワークロードの最悪のケースで1％未満の追加反復実行が発生する。

SRV-start命令は、SRV領域の反復順序特性を示す属性が付与される。アクセスするメモリアドレスが増加するとベクトルレジスタレーン番号が増加する場合、SRV-start命令にはUP属性が付与される。そうでなく、メモリアドレスが減少するときはDOWN属性が付与される。

B. メモリの曖昧さの解消

SRVでのメモリ曖昧性解消を行うために、LSUのコンポーネントに対して論理を追加し、データ依存性の違反を補足するようにした。LSUにはロードキュー(Load Queue: LQ)、ストアアドレスキュー(SAQ)、ストアデータキュー(SDQ)に分割されているものとする。連続したベクトルロード命令とブロードキャストベクトルロード命令はLQを1つ専用するが、ベクトルギャザー命令は各レーンに対して1エントリを占有する。また、連続するベクトルストア命令はSAQとSDQで1つのエントリを占有するが、ベクトルスキャターはデータを格納する各レーンで1つのエントリを占有する。

  1. ロード命令実行する。ロード命令が発行されると、SAQのすべての古いストア命令と比較される。スカラ命令であればこれをフォワーディング可能であるが、SRVではWrite-After-Read違反が発生するだけとなる。この場合はSDQからエントリを転送することは出来ない。ロード命令は、転送可能なデータを古いSDQエントリの前のレーンのみから取得する必要がある。一致するものがない場合は、通常通りメモリ階層からデータをロードする。これによりデータを部分的にメモリシステムからロードし、SDQから部分的に転送する。

  2. ストア命令の実行では、仮想アドレスが判明した時点で、若いロード命令を含むLQエントリと比較する。また、Write-After-Writeを検出するためにSAQの検索も並行して行う。

SRVの場合には、古いストア命令が若いロード命令の投機的実行を検査して、アドレスが重複した場合は書きつぶすのに加え、発行元のストアが、古いロード命令が読み込んだアドレスと同じアドレスに書き込む場合にも、RAW違反を発生させる。

SRV領域での実行により、データ依存性違反を発生させる可能性がある。WARの場合には古いレーンのデータを転送せず、WAWの場合には古いレーンのデータをメモリに書き込むかをSAQが記録し、最終的にプログラム順で書き戻す。一方、RAW依存はSRV-needs-replayレジスタのビットを設定し、違反レーンを再実行することで処理する。

D. その他のアーキテクチャ上の変更点

  • 同期化ポイント：SRV-end命令は、同期化ポイントが作成され、直前の命令よりも若い命令は実行することが出来なくなっている。
  • アーキテクチャステート：アーキテクチャステートは、SRV領域から命令がコミットされるごとに進んでいき、SRV-end命令が実行されると、SRV-replayレジスタが読み込まれて、SRVの終了が判定される。 SRV領域実行中にコンテキストスイッチやプロセッサモード変更が発生した場合、現在のPC値、SRV-replayレジスタ、SRV-start命令の次のPCを対比する。再開時には、これらのレジスタの値が復元される。
  • 割り込みと例外：SRV領域での割込み発生では、上記で示したように即座に処理される。例外処理については、例外の発生したレーン番号を特定し、そのレーンが現在実行中の最も古いレーンである場合は、割り込みと同様に処理する。そうでない場合は、そのレーンとそれ以降のレーンに再実行のマークを付け、メモリ依存性違反の後に誤ったデータを使用した場合の例外発生を防止する。
  • SAQの変更：ストアはROBの先頭に到達するとコミットされるが、ストアキューに投機的フラグが設定されている場合はストアキューに残される。SRV-needs-replayレジスタが設定されていない場合は、保存されたデータがL1キャッシュに書き戻される。
  • レジスタリネーム：再実行時に、既に実行されたレーンを保持するために、命令のマージ動作が必要となる。このため、新しいデータをマージするために、ソースオペランドとして古い書き込みレジスタのデータも読みだしておく必要がある。
  • インオーダアーキテクチャ：アウトオブオーダに比べて、インオーダマシンへのSRVの適用は容易であるが、データ依存性の違反を検出するための論理は必要である。
  • LSUのオーバフロー：利用可能なLSUエントリ数よりも多くのロードストア命令を持つSRVを作成する可能性があり、この場合は等価的に順次実行にフォールバックされる。