命令レベル並列性

命令レベル並列性（ILP）とは、単一プログラムからの複数の命令を同時に実行する可能性を指し、スーパースケーラプロセッサやVLIWプロセッサによって活用され、1サイクルあたり複数の命令を発行・完了させます。

Definition

命令レベル並列性とは、単一プログラムの命令が並列に実行できる度合いを指します。プロセッサは、データおよび制御依存性の制約を受けつつ、1クロックサイクルあたり複数の命令を発行、実行、完了させることでこれを活用します。

Scope

このトピックでは、単一の命令ストリーム内で利用可能な並列性、およびハードウェアとコンパイラがそれをどのように抽出するかについて扱います。具体的には、1サイクルあたり複数の命令を発行するスーパースケーラ方式、超長命令語（VLIW）設計、依存性解析、レジスタリネーミング、投機的実行などが含まれます。また、利用可能なILPの限界についても扱います。コア間およびレーン間のスレッドレベル並列性およびデータレベル並列性（並列およびマルチコアアーキテクチャ）、ならびに基本的な単一発行パイプライン（パイプライン処理とハザード）は対象外です。

Core questions

• 典型的なプログラムの命令間に本質的にどれくらいの並列性が利用可能ですか？
• スーパースケーラプロセッサは、どの命令を同時に発行できるかをどのように決定しますか？
• VLIW設計は、並列性を見つける負担をどのようにコンパイラに移行させますか？
• どのような依存性やハザードが、実現可能なILPの量を制限しますか？

Key concepts

• スーパースケーラ発行
• 超長命令語（VLIW）
• データ依存性および名前依存性
• レジスタリネーミング
• 複数の機能ユニット
• 投機的実行
• ILPの限界
• 1サイクルあたりの命令数（IPC）

Key theories

動的命令スケジューリング

ハードウェアは、依存性を追跡し、準備ができた命令を複数の機能ユニットにスケジューリングすることで、実行時にILPを発見し活用することができます。予約ステーションとレジスタリネーミングを備えたTomasuloのアルゴリズムは、アウトオブオーダーの並列発行を可能にする典型的なメカニズムです。

Mechanisms

スーパースケーラプロセッサは、1サイクルあたり複数の命令をフェッチおよびデコードし、それらの依存性をチェックし、誤った依存性を排除するためにレジスタをリネームし、独立した命令を複数の機能ユニットに発行します。一方、VLIW設計では、コンパイラが独立した操作を幅の広い命令語にバンドルすることに依存します。真のデータ依存性と制御フローは、実現可能な並列性の上限を設定しますが、投機的実行とより大きな命令ウィンドウによってその上限を拡張しようとします。

Clinical relevance

ILP技術は、数十年にわたるシングルスレッド性能の向上を牽引し、高性能CPUコアの中心的な要素であり続けています。利用可能な並列性と複雑性の限界に達したことによるILPの収穫逓減は、業界がさらなるスケーリングのためにマルチコアおよび明示的な並列処理へと移行した主要な理由の一つです。

History

複数の機能ユニットと動的スケジューリングは、1960年代のCDC 6600およびIBM System/360 Model 91に登場しました。スーパースケーラ設計は1990年代に主流となり、IntelのItaniumのようなVLIWアーキテクチャはコンパイラ主導の並列処理を追求しました。1990年代初頭のILPの限界に関する研究は、単一スレッド内の並列性がなぜ限界を持つのかを明らかにしました。

Debates

ハードウェア主導型ILP対コンパイラ主導型ILP

スーパースケーラのアウトオブオーダーハードウェアは、複雑さと電力消費を犠牲にして実行時に並列性を動的に発見しますが、VLIWはコンパイラが並列性を静的にスケジューリングすることに依存します。経験上、動的アプローチはワークロード全体でより堅牢であることが示され、静的アプローチは予測可能で低電力の設計にとって依然として魅力的です。

Key figures

• Robert Tomasulo
• Yale Patt
• John L. Hennessy
• Joseph A. Fisher
• James E. Smith

Seminal works

• hennessy2019
• tomasulo1967

Frequently asked questions

スーパースケーラとVLIWの違いは何ですか？

どちらも1サイクルあたり複数の操作を実行します。スーパースケーラプロセッサは、実行時にハードウェアでどの命令を同時に発行できるかを決定します。VLIWプロセッサは、コンパイラが独立した操作を事前に幅の広い命令にグループ化することに依存し、ハードウェアを簡素化しますが、コンパイラにより多くの負担を求めます。

命令レベル並列性に限界があるのはなぜですか？

実際のプログラムには、真のデータ依存性や頻繁な分岐があり、これらが並列に実行できる命令の数を制約します。あるウィンドウを超えると、達成可能な並列性は飽和し、より多くのILPを抽出しても、追加されるハードウェアの複雑さや電力に対して収穫逓減が生じます。