命令レベルの並列性

命令レベルの並列性（めいれいレベルのへいれつせい、Instruction-level parallelism、ILP）とは、プログラムの中で並列して実行できる処理がいくつあるかの尺度である。

例として以下のようなプログラムを考える。

1. e = a + b
2. f = c + d
3. g = e * f

処理3は、処理1と処理2の結果に依存している。したがって、処理3は処理1と処理2が完了してからでないと計算を開始できない。 しかし、処理1と処理2は何にも依存していないので並列して実行できる。 それぞれの処理にかかる時間が同じだとして、それを1とすると、これら3命令が完了するのにかかる時間は2となり、結局ILPは3/2となる。

コンパイラとCPUの設計者の目標のひとつは、可能な限りILPを高めることである。通常のプログラムは逐次実行モデルで書かれており、命令はプログラマが記した順に実行されることが前提となっている。ILP はコンパイラやプロセッサが複数の命令を同時に実行することを可能にしたり、順番を全く変えて実行することを可能にする。

プログラム内の命令レベルの並列性は、個々のアプリケーションによって異なる。グラフィックスや科学技術計算といった特定の分野では、計算量は多いが単純計算の繰り返しが多く、命令レベルの並列性は大きいことが多い。しかし、暗号などの処理では条件判定を多用するため結果の分岐次第でプログラムルーチンが変化してしまい、並列性は小さい。

ILPを利用するアーキテクチャ上の技法としては、以下のようなものがある。

命令パイプライン

メモリよりも高速なキャッシュメモリを使うことでアクセスにかかる待ち時間を軽減する。しかしキャッシュメモリ自体のアーキテクチャにも依存する。

レジスタ・リネーミング

論理レジスタ（の写像）による不必要なプログラムの順序性を防ぐテクニック。物理レジスタリソースが少ない場合は割り当てができないことがある。

投機的実行

条件分岐によるパイプラインストールを減らす。パイプラインが深い場合は特に有効だが、ハードウェアリソースを増大させる。

分岐予測

パイプラインを最充満状態にしておくために使われる。しばしば投機的実行とともに実装する。

スーパースケーラ

複数の実行ユニットが並行して複数の命令を実行する。並列計算ではなく並行計算にあたる。

アウト・オブ・オーダー実行

メモリアクセスによるパイプラインストールを減らす。だが製造価格に大きく影響するほどのハードウェアリソースを必要とするため、かつては純粋な実装は現実的でなかった。近年は新しいスキームの提案や改良を加えたアーキテクチャの実装により実現している。

アウト・オブ・オーダー実行の現在の実装では、普通のプログラムから（コンパイラの助けを借りずに）動的に命令レベルの並列性を引き出す。並列性をコンパイル時に引き出し、その情報をハードウェアに伝えるという方法もある。アウト・オブ・オーダー実行は大規模化すると実装するのが難しくなるため、命令セットを見直して、一つの命令に独立して実行可能な複数の操作を符号化する方法が見直された。そのような手法として、VLIW と EPICアーキテクチャがある。VLIW とアウト・オブ・オーダー実行は同時に使用することも可能である。

データフローアーキテクチャは命令レベルの並列性を明示的に引き出す別の手法である。

近年、ILP技法はプロセッサに比較してメモリが遅いという問題を克服して性能向上させる方法（メモリレイテンシーの隠蔽策）として使われている（System/360のころのILP技法はレジスタ数の少なさへの対処であった）。キャッシュミス時のペナルティは（21世紀初頭でも）数百サイクルにもなる。メモリレイテンシへの対処として上に挙げたようなILP技法を使うということは、リソースや電力消費の点であまりにも不釣合いである。さらに、ハードウェアが複雑化することでかえって動作周波数を上げられなくなり、性能が頭打ちになるという問題も生じている。従って、CPUがチップ外のデータを待って停止するのを避けるためにILP技法を利用するのは不適切であるとの考え方が出てきた。その代わりに、業界はマルチプロセッシングやハードウェアマルチスレッディングのような技法で明確でより高レベルな並列性を利用する方向へと進んでいる^[1]

依存関係には2つの種類がある。データの依存関係と制御の依存関係である。一般のプログラムは逐次実行モデルを前提として書かれている。このモデルにおいては、命令はひとつずつ実行され、個々の命令は不可分であり（すなわち、任意の時点で実行されている命令は1つだけである）、プログラムが指定した順序通りに実行される。

命令レベルの並列性を妨げる依存関係は様々である。複数の命令の並列実行を行えば、命令の実行順序が変わってしまい、そこに依存関係があれば、最終的な結果が期待したものとは変わってしまう。データの依存関係には、以下のようなものがある。

真の依存（true dependency）は、ある命令がその前の命令の実行結果に依存している場合を指す。

1. A = 3
2. B = A
3. C = B

3番の命令は2番の命令に「真の依存」をしている。つまり、Cの最終的な値は、Bを更新する命令の結果に依存する。2番の命令は1番の命令に「真の依存」をしている。つまり、Bの最終的な値は、Aを更新する命令の結果に依存する。3番の命令が2番の命令に真の依存をしていて、2番の命令が1番の命令に真の依存をしているため、3番の命令は1番の命令に真の依存をしている。従って、この例には命令レベルの並列性は存在しない。^[2]

反依存（anti-dependency）は、命令が後で更新される値を必要とする場合を指す。以下の例では、3番の命令は2番の命令に反依存している。これらの命令を順番を変えたり、同時に並列して実行すると、最終的な A の値が期待したものとは変わってしまう可能性があるため、逐次的にしか実行できない。

1. B = 3
2. A = B + 1
3. B = 7

反依存は「名前依存; name dependency」の一種でもある。すなわち、変数名を変えてやることで依存関係が解消される。以下に例を示す。

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

新たな変数 B2 を導入して B を代入する命令 N を追加する。すると、2 と 3 の反依存は解消され、これらを並列して実行可能となる。しかし、この修正によって新たな依存関係が生じている。2番の命令は N に真の依存をしており、N は1番に真の依存をしている。真の依存であるため、これらは解消できない。^[2]

出力依存（output dependency）とは、命令の並べ替えによって最終的な変数の出力値が変わってしまうことを指す。以下の例では、3番と1番の命令に出力依存がある。命令を並べ替えると、Aの最終的な値が変わってしまうため、これらの命令を並列して実行することはできない。

1 A = 2 * X
2 B = A / 3
3 A = 9 * Y

反依存と同様、出力依存も名前依存の一種である。従って、変数名を変えることで解消できる。この例の場合、以下のように修正すればよい。

1 A2 = 2 * X
2 B = A2 /3
3 A = 9 * Y

一般に、変数名に関わるデータの依存関係は、リード・アフター・ライト（真の依存）、ライト・アフター・ライト（出力依存）、ライト・アフター・リード（反依存）と呼ばれる（レジスタ・リネーミング参照）。

命令Bがその前にある命令Aに制御依存しているという場合、命令Aが命令Bを実行するか否かを決定していることを意味する。以下の例では、命令 2 は 命令 1 に対して制御依存している。

1.         if a == b goto AFTER
2.         A = 2 * X
3. AFTER:

^[2]

1. ^ Reflections of the Memory Wall
2. ^ ^{a b c} Hennesy; Patterson (2003年). Computer Architecture: a quantitative approach (3rd ed). Morgan Kaufman. ISBN 1-55860-724-2 

• メモリレベルの並列性 (MLP)

• Reflections of the Memory Wall
• Wired magazine article that refers to the above paper
• Approaches to addressing the Memory Wall