FPGA開発日記

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

UCBのAdvanced Computer Architectureの講義資料を読む(7. ILPの向上テクニック)

CPU コンピュータアーキテクチャ

コンピュータアーキテクチャの論文を読んでいたのだが、どうもよく知らない項目がある。 よく考えてみたらコンピュータアーキテクチャの最新トレンドも含め最近勉強量が不足していたので、ここらへんでもう一度復習しておきたい。 せっかくなので海外の大学の講義資料を読んでみよう。

  • Advanced Computer Architecture

https://www.ece.ucsb.edu/~strukov/ece154BSpring2018/home.htm

目次

Advanced Computer Architecture

4. 命令レベル並列性とその抽出

1985年以降、パイプライン化は世界的に一般的な手法となった。パイプライン化は命令をオーバラップさせて実行するテクニックであり、「命令レベル並列性」を抽出するテクニックである。

パイプライン化を超えるテクニックとして、以下のような手法が検討された。

  • ハードウェアベースの動的なアプローチ
    • サーバ向けプロセッサやデスクトッププロセッサで使用されている。
    • モバイル向けのデバイスでは、広くは使われていない。
  • コンパイラベースの静的なアプローチ
    • 現代のプロセッサではあまり成功していない。

命令レベル並列性の目標はCPIを小さくすること。CPIが大きくなってしまう要因は、

  • 構造ハザード
  • データハザード
  • 制御ストール
技法 CPI削減要因
フォワーディングとバイパシング 潜在的なデータハザードによるストール
遅延分岐と単純な分岐のスケジューリング 制御ハザードストール
基本的なコンパイラのパイプラインスケジューリング データハザードストール
基本的な動的スケジューリング（スコアボーディング） 真のデータ依存によるデータハザードストール
ループアンローリング 制御ハザードストール
分岐予測 制御ストール
リネーミングによる動的スケジューリング データハザードによるストール、出力依存、逆依存
ハードウェア投機実行 データハザードと制御ハザードストール
動的メモリアクセスの曖昧性解消 メモリによるデータハザードストール
サイクル当たりの複数命令発行 理想CPI
コンパイラに依存解析、ソフトウェアパイプライン、トレーススケジューリング 理想CPI、データハザードストール
ハードウェア支援付きコンパイラ投機実行 理想CPI、データハザードストール、分岐ハザードストール

データ依存

データ依存では、ある命令jがある命令iにデータ依存があるというのは、

  • 命令iが生成する結果を命令jが使用する場合を意味する。
  • 命令jと命令kにデータ依存が存在すると、命令iと命令kにもデータ依存が存在する。

データ依存の存在する命令は同時に実行することができない。パイプラインの構成では、このようなデータ依存が初声英いた場合には命令のストールが発生する。さらに、メモリを介するデータ依存の検出はより難しくなる。

名前依存

2つの命令が同じ名前を使用するが、実際にはフローの関係性がないことを名前依存という。真おデータ依存ではないが、りおーだ実行を行うときに問題となる。このときに「逆依存」という問題があり、命令jがレジスタやメモリからデータを読み込む前に、命令jがレジスタやメモリに値を書き込んでしまうという問題である。また、「出力依存」というのは、命令iと命令jが同じメモリ領域、同じレジスタに値を書き込んでしまう問題であり、順序を守る必要がある。これらの問題を解決するためには、リネーミングを行う。

データハザード

データハザードには、以下の3種類が存在する。

  • Read After Write (RAW)：データを書き込む前に読み込んでしまうハザード
    • ADD 3, 1, 2
    • NAND 4, 3, 5
  • Write After Write (WAW)：データを書き込んだ後にデータを書き込むハザード。アウトオブオーダ実行で問題になる。
    • ADD 3, 1, 2
    • NAND 3, 5, 6
  • Write After Read (WAR)：逆依存。リオーダリングで発生する。
    • ADD 1, 2, 3
    • NAND 2, 5, 6

コンパイラによるILPの抽出例

パイプラインスケジューリングでは、パイプラインレイテンシによってデータの依存関係を隠蔽する。

  • 例：
for (i=999; i>=0; i=i-1) {
    x[i] = x[i] + s;
}
結果を生成する命令 結果を使用する命令 レイテンシ
FP ALU op Another FP ALU op 3
FP ALU op Store Double 2
Load double FP ALU op 1
Load double Store Double 0
f:id:msyksphinz:20200316231311p:plain

最初の実行：パイプラインストール
Loop: L.D F0,0(R1)
stall
ADD.D F4, F0, F2
stall
stall
S.D F4,0(R1)
DADDUI R1,R1,#-8
stall
BNE R1,R2,Loop

スケジューリングした結果
Loop: L.D F0,0(R1)
DADDUI R1,R1,#-8
ADD.D F4, F0, F2
stall
stall
S.D F4,0(R1)
BNE R1,R2,Loop

ループアンローリング

例えば4回分ループを展開することによりストールのスロットを埋めていく。ループアンローリングの問題は、使用するレジスタが増えてしまうことと、プログラムのサイズが大きくなってしまうことである。

ストリップマイニング

ループの回数がその場で決まっていない場合、例えばループの回数が$n$回で、ループアンローリングの回数を$k$回とすると、

  • 最初に$n$ mod $k$回ループを実行するコードを生成する。
  • 次に$k$回分アンローリングしたループを$n$回実行する。

アウトオブオーダ実行

レイテンシの異なるパイプラインを混合させると、必然的にハザードが発生する。WAR/WAW/RAWハザードをどのように解決するか？

Instruction 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ADD 3, 2, 1 IF ID EX M WB
MUL 6, 5, 4 IF ID E1 E2 E3 E4 E5 E6 E7 M WB
DIV 8, 7, 6 IF ID x x x x x x E1 E2 E3 E4
ADD 7, 2, 1 IF ID EX M WB
SUB 8, 2, 1 IF ID EX M WB

スコアボード：Bookkeeping Technique

スコアボードは1963年にCDC6600で導入された技術。インオーダ発行、アウトオブオーダ実行、アウトオブオーダコミット。

  • 命令デコードステージで、構造ハザードを検出する。
  • オペランドリードでは、データハザードが解消されるまで待つ。
f:id:msyksphinz:20200316231331p:plain

アウトオブオーダ完了なので、WARハザードとWAWハザードが発生する。これをどのように解決するか？

  • WAR：後続のレジスタ読み込みがすべて完了するまで、レジスタ書き込みをストールさせる。
  • WAW：ハザードを検出し古い命令が完了するまで新しい命令の発行をストールする。

スコアボードのためのステージ実装の変更

  • 発行ステージ：

    • プログラムの順番で命令を発行する。
    • 構造ハザードが発生している場合は命令を発行しない。
    • 出力依存が発生している場合は命令を発行しない。

  • オペランド読み込み：

    • 全てのデータハザードが解決するまで待つ。
    • フォワーディングは発生しない。
  • 実行：
    • オペランドを受け取ると、実行を行う。結果がReadyになると、スコアボードに命令の実行完了を通知する。
  • データ書き込み：
    • 前の命令とWARハザードが発生しないようにストールする。