第3章データ依存関係

第3章　データ依存関係

命令の中には、レジスタやメモリを介してデータを操作するものがある。データ操作を伴う命令に起因して、CPUのパイプライン上を命令が滞りなく流れなくなり、結果としてソフトウェアの実行が遅くなる場合がある。今回はその要因の１つの「データ依存関係」について見ていく。

3.1 データ依存関係とは

ある２つの命令が、同一のレジスタやメモリ領域を使用する場合、その２つの命令間には「データ依存関係」があるという。以下がデータ依存関係のいくつかのパターンである。

データ依存関係なし：ここでは２つの命令において、同じレジスタ番号を使用していないこと。
1 2
mul x22, x23 ,x24 add x25, x26, x27
真のデータ依存関係：先行命令の書き込み結果を、後続命令が読み込む場合の関係。先行命令の結果が出るまで後続の命令が実行できないため、命令流を滞らせる原因になる。「先行命令の実行完了」→「後続命令の実行開始」の逐次実行を強要される。
1 2
mul x1, x23 ,x24 add x25, x26, x1
逆依存関係：先行命令が読みだすレジスタと、後続命令が書き込むレジスタが同じ場合の関係
1 2
mul 22, x23 ,x1 add x1, x26, x27
出力依存関係：先行命令が書き込んだレジスタへ、後続命令も書き込む場合の関係
1 2
mul x1, x23 ,x24 add x1, x26, x27
入力依存関係：２つの命令が同じレジスタから読みだす場合の関係
1 2
mul x22, x23, x1 add x25, x26, x1

3.2 真のデータ依存関係のスーパーパイプライン化への影響

例として、命令実行ステージが4段のスーパーパイプライン構成において命令実行に4ステージを要するmul命令の結果を、後続のadd命令する場合を考える(真のデータ依存の例)。パイプラインの挙動を下の図に示す。

3-2
図3.2 真のデータ依存関係のパイプラインタイミング

スーパーパイプラインは、パイプラインステージを時間方向に細分化し、後続命令の開始を早めることで、ソフトウェアを高速化するアプローチだった。上の図だとmulの結果が得られるのは時刻t5であり、その結果をaddで使用できるのはt6となる。従って、後続のadd命令は時刻t6まで命令実行を開始できない。

このように、スーパーパイプライン化において「レイテンシが2サイクル以上ある命令の実行結果を後続の命令が使用する」という真のデータ依存関係がある場合には、後続の命令実行開始が保留され待たされる。上の図では、命令実行ステージⅣにおいて３サイクル分の空きが出てしまっている。この無駄なサイクルを「ペナルティサイクル」、パイプラインの流れを妨げる要因や状況を「ハザード」と呼ぶ。

スーパーパイプライン化で真のデータ依存関係がある場合には、命令実行ステージの分割数を増やすほどペナルティサイクルが発生する。以下が図である。

3-3
図3.3　真のデータ依存関係のスーパーパイプラインへの影響

3.3 真のデータ依存関係のスーパースカラ化への影響

スーパースカラは、パイプラインを物理的に複数搭載することによって同時に実行できる命令を増やし、ソフトウェアを高速化するアプローチだった。しかし、真のデータ依存関係がある場合には、後続の命令を同時に開始することはできない。

下の図は、2並列と4並列のスーパースカラ化されたパイプラインを例に、命令1と命令2に真のデータ依存関係がある場合を示している。スーパースカラ化により同時に実行できるパイプラインの数を増やすほど、そこで得られるはずの命令実行機会をより多く失うことになる。

3-4
図3.4　真のデータ依存関係のスーパースカラへの影響

3.4 アウトオブオーダー実行による緩和

真のデータ依存関係によって失われる命令実行機会の損失を緩和し、埋め合わせるためのハードウェアによる策として、真のデータ依存関係がない別の命令の実行開始を前倒しするという手法がある。このように命令間の実行開始の順序を入れかえて高速化する方式のことを、「アウトオブオーダー実行」と呼ぶ。

以下の図は、真のデータ依存関係によって後続の命令が待たされている状況においての、インオーダー実行とアウトオブオーダー実行の違いを示している。

3-5
図3.5　アウトオブオーダー実行のパイプラインタイミング

アウトオブオーダー実行では、真のデータ依存関係によって待たされている命令2の代わりに後続の依存関係のない命令3を前倒しで実行している。つまり、命令間の実行開始の「順序の入れ替え」をしている。これにより、空きサイクルを有効活用できている。

アウトオブオーダー実行を行うためには、前倒し可能な命令が必要であり、その候補は別の先行命令に対して真のデータ依存関係にあるものは選べない。

また、命令を前倒すためには、その命令がすでにフェッチされ、デコードされている必要がある。図3.5でもt2までにデコードが完了していないため、命令３をt2で実行できない。つまり、命令の供給が追い付いていないのである。命令の実行開始を前倒すためには、フロントエンド(命令フェッチ＋命令デコード)を先に進めていつでも実行開始できるように命令を準備しておく必要がある。

アウトオブオーダー実行は、真のデータ依存関係によってソフトウェアが遅くなる状況を緩和できるが、別の真のデータ依存関係や命令の供給状況によって効果は制約される。大変有用であるが、万能ではない。

アウトオブオーダー

順序を守らないことを一般的に表す広い用語である。順序の対象は、命令のフェッチの順序、命令の実行完了順序、メモリのアクセスの順序など幅広い。ここで使われるのは、命令の実行開始についての順序を指す。

3.5 再順序化(リオーダー)の必要性

CPUが実行する命令は、必ずしも実行の完了が保障されているわけではない。例外、割り込み、分岐などの影響により、その命令を実行してはいけない場合もある。アウトオブオーダー実行では、本来実行完了してはいけない命令を前倒しし、書き換えてはいけないレジスタやメモリの内容を書き換えてしまう可能性がある。

この問題を解消するためには、CPUハードウェアで命令実行後に再順序化(リオーダー)を行う必要がある。命令実行ステージにおける命令実行の開始と完了はアウトオブオーダーで行い、命令実行完了のタイミングで実行結果を仮に保持しておいて、それをプログラムの順番通り(インオーダー)に並べ直して実際のCPU資源(レジスタやメモリ)に対して反映していくわけである。そのために、パイプラインに「命令コミットステージ」や「命令リタイアステージ」と呼ばれる新たなステージを設けている。

3-6
図3.6　リオーダーのパイプラインタイミング

再順序化を実現するためには、実行中および実行を保留されている全命令について、そのプログラム順序を正確に記録しておくための仕組みが必要である。そのような仕組みの1つとして、「命令のプログラム順序をテーブルに記録しておく」という方法がある。そのためのテーブルは「リオーダーバッファ」と呼ばれる。リオーダーバッファでは、まだ実行完了してはいけない命令と、実行を完了させるべき命令の境界を正確に管理し、無効な命令のみを正確にキャンセルできるようになる。

アウトオブオーダー実行により、同時に処理できる命令の数は、リオーダーバッファのハードウェア実装コストによって制限される。100個の命令をアウトオブオーダー実行するためには、100個のエントリを持つリオーダーバッファが必要だからである。すべてのエントリが使用されている場合には、新たな命令の実行開始は保留され、待たされる。アウトオブオーダー実行は、ハードウェアの実装に関して大きな課題がある手法だと言える。

3.6 真ではないデータ依存関係への影響を解消する

アウトオブオーダー実行は、真のデータ依存関係による命令実行機会の損失を緩和するが、それ以外のデータ依存関係にも影響が及ぶ仕組みである。逆依存関係もしくは出力依存関係がある命令は、命令間の実行開始の順序を入れ替えると誤動作となってしまうからである。従って、アウトオブオーダー実行が抑制されてしまっている。

下の図に逆依存関係にある命令を入れ替える状況を示す。後続のadd命令をmul命令よりも前倒すと、mul命令が読み出すはずであった本来のレジスタx1の値をadd命令が上書きして壊してしまう。よって、入れ替えてはいけない。

3-7
図3.7　逆依存関係の課題

下の図は、出力依存関係の場合である。後続のadd命令をmul命令よりも前倒すと、add命令が書き込んだレジスタx1の値が本来は最終的な値となるところがmul命令の値が最終的なものになってしまう。よって入れ替えるべきではない。

3-8
図3.8　出力結果の課題

幸い、これらのデータ依存関係に関する問題は真のデータ依存関係と違って解消が可能である。逆依存関係と出力依存関係は、レジスタを再利用していることにより生じる見かけ上の依存関係であることからレジスタの再利用を回避することで解消できる。具体的には、書き込み対象のレジスタとして、毎回、新しいレジスタを割り当てることで対策できる。

下の図は、命令で指定している書き込み対象のレジスタを、ハードウェアにより別の便宜上のレジスタに置き換える状況を示している。add命令で指定されたレジスタx1を、便宜上のレジスタp1に置き換えることでmul命令が参照するレジスタx1を壊さないようにしている。

3-9
図3.9　レジスタリネーム

このように、CPUのアーキテクチャ仕様上のレジスタをユーザーからは見えない便宜上のレジスタにリネームする方式を「レジスタリネーム」と呼ぶ。リネーム用のレジスタの実装方法として、前述のリオーダーバッファを用いる方法や、物理レジスタ群を搭載する方法がある。

レジスタリネームのためのハードウェア実装コストも、アウトオブオーダー実行で同時に処理できる命令の数を制限する要因となる。このレジスタ数が不足した場合には、新たな命令の実行開始は保留され、待たされるからである。リネーム用のレジスタ資源の数は、CPUのアーキテクチャ仕様で規定されるレジスタよりも多い必要がある。

3.7 ソフトウェアによる緩和

アウトオブオーダー実行は、真のデータ依存関係による影響をCPUハードウェアにより緩和する仕組みである。一方、プログラム側で実行レイテンシが長い命令を避けたり、レイテンシが長い命令をより早めに実行したりすることで、真のデータ依存関係を緩和する方法も考えられる。真のデータ依存関係がない別の命令で無駄な空きサイクルを埋めるといった方策も有効である。

ここでは、真のデータ依存関係による速度低下の緩和に有効と考えられる、ソフトウェアを開発するプログラマー側のアプローチをいくつか紹介する。

3.7.1 レイテンシの仕様を知る

真のデータ依存関係による影響は、先行命令の実行レイテンシが長いほど大きくなる。そのため、命令レイテンシについて意識することは有効である。

仕様を公開しているものをいくつか抜粋したものは以下の表の通りである。

3-1
表3.1　各CPUの代表的なレイテンシ値

表からCPUの種類によらず、レジスタ間転送や加算のような単純な命令のレイテンシは一般に1サイクルであることが分かる。一方、乗算命令は回路規模が複雑であることから加算命令よりも遅く、3サイクル程度必要である。一般にメモリから読みだすロード命令は数サイクルかかる遅い命令であることが読み取れる。複雑なアルゴリズムで実装される除算命令については、各社ともに10サイクル以上の規模となっている。

3.7.2 レイテンシが長い命令を避ける

有効なパターン例 - 除算命令(定数による除算を行う場合かつ精度が許す場合)→定数を逆数にして乗算命令する - 2のべき乗の蒸散命令→シフト命令

3.7.3 レイテンシが長い命令が先行されるように配置する

レイテンシが長い命令を早めに実行できれば、後続の命令がより早くその結果を読みだせる。一般化するのは難しいが、例えばループ構造に着目してレイテンシが長い命令が早めに実行されるプログラムを変形できる場合がある。具体的には、ループに置ける次の周回の一部の命令を、現在のループ周回に前倒しさせることが可能な状況を探すということである。このような高速化は「ソフトウェアパイプライニング最適化」と呼ぶ。

for (int i = 0; i < N; i++) {
    C[i] = A[i] + B[i];
}

↓　ソフトウェアパイプライニング最適化

// 仮に2命令先読みする例（擬似コード）

// 先に先読み
load_A0 = A[0];
load_B0 = B[0];

for (int i = 1; i < N; i++) {
    load_A1 = A[i];
    load_B1 = B[i];
    C[i - 1] = load_A0 + load_B0;
    load_A0 = load_A1;
    load_B0 = load_B1;
}
C[N - 1] = load_A0 + load_B0;  // 最後の1回分を処理

3.7.4 真のデータ依存関係のない命令で埋める

CPUハードウェアによるアウトオブオーダー実行と同様に、真のデータ依存関係のない別命令は無駄な空きサイクルを埋めることができる。一般化は難しいが、ループ構造に着目することで可能になることがある。具体的には、ループにおける次の周回に依存関係のない状況を見つけ出し、それを丸ごと現在のループ周回で一緒に実行させる。これは「ループアンローリング最適化」と呼ばれる。ループアンローリングでは使用するレジスタ数が増えることから、レジスタ不足による性能劣化が生じる可能性があることに注意が必要。

for (int i = 0; i < N; i += 4) {
    A[i]   = B[i]   + 1;
    A[i+1] = B[i+1] + 1;
    A[i+2] = B[i+2] + 1;
    A[i+3] = B[i+3] + 1;
}

3.8 命令レイテンシの計測実験

本章では、真のデータ依存関係と命令レイテンシの長さが命令流の実行速度に及ぼす影響について説明した。これらに対する直感を得ることを目的として、加算命令、乗算命令、ロード命令、レイテンシを計測(推定)するためのアセンブリプログラムとその実行例を簡単に紹介する。

3.8.1 加算命令のレイテンシ計測

一般的なCPUにおける命令のレイテンシをミクロなサイクル粒度で正確に計測するのは困難なので、命令の実行回数を多くすることで、サイクル数を統計的に観測する。

addprog
リスト3.1:latency_add.S

計測対象であるadd命令を合計で10億回実行するlatency_add.Sを使用する(100個のadd命令を1000万回のループ)。x86のadd命令は、加算の入力データを指定する１つ目のレジスタと、加算の結果を格納するレジスタが同一となる仕様となっている。そのため、毎回のadd命令で真のデータ依存関係が発生している。これによって、複数のadd命令が同時に実行されるのを防げるため、命令単位でレイテンシが計測可能になっている。（スーパースカラ構成のCPUが複数実行するのを防ぐ）

3-2
3-2