命令レベルの並列性

命令レベルの並列性（ILP）とは

命令レベルの並列性（Instruction-level parallelism、ILP）とは、プログラムの中で並列して実行できる処理がどれだけあるかを示す尺度です。これは、コンピュータの性能を向上させる上で重要な要素であり、コンパイラやCPUの設計において、ILPを最大限に活用することが目標とされています。

ILPの概要

ILPを理解するために、簡単な例を考えてみましょう。


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


このプログラムでは、3番目の処理（gの計算）は1番目と2番目の処理（eとfの計算）の結果に依存しています。したがって、3番目の処理は1番目と2番目の処理が完了するまで開始できません。しかし、1番目と2番目の処理は互いに依存していないため、並列に実行できます。

もし、それぞれの処理にかかる時間が同じだと仮定し、それを1とすると、この3つの命令を完了するのにかかる時間は2となります。この場合、ILPは3/2となります。

ILPを高めるための技術

コンパイラやプロセッサの設計者は、ILPを高めるために様々な技術を利用しています。

命令パイプライン: 命令を複数の段階に分割し、同時に複数の命令を処理します。
キャッシュメモリ: メインメモリよりも高速なキャッシュメモリを使用することで、メモリアクセスの待ち時間を短縮します。
レジスタ・リネーミング: 論理レジスタを物理レジスタに動的に割り当てることで、不必要な命令の順序性を排除します。
投機的実行: 条件分岐の結果を予測し、予測に基づいて命令を事前に実行することで、パイプラインの停止を防ぎます。
分岐予測: パイプラインを常に満たしておくために、分岐先の予測を行います。
スーパースケーラ: 複数の実行ユニットを並列に動作させ、複数の命令を同時に実行します。
アウト・オブ・オーダー実行: 命令の依存関係を解析し、順序を入れ替えて実行することで、メモリアクセスによるパイプラインの停止を減らします。

アウト・オブ・オーダー実行とVLIW/EPICアーキテクチャ

アウト・オブ・オーダー実行は、プログラムから動的にILPを引き出す技術ですが、大規模化すると実装が難しくなります。そのため、命令セットを見直し、一つの命令に複数の操作を符号化するVLIW (Very Long Instruction Word) や EPIC (Explicitly Parallel Instruction Computing) といったアーキテクチャも提案されています。

データフローアーキテクチャ

データフローアーキテクチャは、命令レベルの並列性を明示的に引き出す別の手法です。これは、命令の実行順序をデータ依存関係のみによって決定する方式です。

メモリレイテンシ問題とILP

近年、プロセッサの速度に対してメモリが遅いため、ILPの技術は、メモリレイテンシ（メモリアクセスの遅延）を隠蔽するための方法として使われるようになっています。しかし、ILPを追求しすぎると、ハードウェアが複雑化し、消費電力が増大するだけでなく、動作周波数を上げられなくなるという問題も生じています。

そのため、より明確で高レベルな並列性を利用する、マルチプロセッシングやハードウェアマルチスレッディングといった技術に注目が集まっています。

依存関係の種類

命令の並列実行を妨げる依存関係には、以下の2種類があります。

1. データの依存関係: ある命令が別の命令の結果を必要とする場合。
2. 制御の依存関係: ある命令が別の命令の実行を制御する場合。

データの依存関係

データの依存関係には、さらに以下の3つの種類があります。

真の依存（リード・アフター・ライト; RAW）: ある命令が、別の命令が書き込んだ値を読み込む場合に発生します。


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


この例では、命令2は命令1に、命令3は命令2に真の依存をしています。

反依存（ライト・アフター・リード; WAR）: ある命令が、別の命令が読み込む値を書き込む場合に発生します。


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


この例では、命令3は命令2に反依存しています。

出力依存（ライト・アフター・ライト; WAW）: 複数の命令が同じ変数に書き込む場合に発生します。


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


この例では、命令3は命令1に出力依存しています。

これらの依存関係は、変数名を変更することで解消できる場合があります（レジスタリネーミング）。

制御の依存関係

制御の依存関係は、ある命令の実行が別の命令の実行結果に依存する場合です。


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


この例では、命令2は命令1に制御依存しています。命令1の条件が真の場合、命令2は実行されません。

まとめ

命令レベルの並列性は、コンピュータの性能向上に不可欠な概念です。コンパイラやCPU設計者は、様々な技術を駆使してILPを最大化しようとしています。しかし、ILPを追求しすぎると、ハードウェアが複雑化し、消費電力が増大するといった問題も生じるため、より高レベルな並列性を利用するマルチプロセッシングなどの技術に注目が集まっています。

もう一度検索