命令レベル並列性（ILP）：概念、技法、実用上の限界

ILPの測定と制約

ILPはしばしば、厳密な逐次実行に対する倍率または高速化率として表現される。次の3命令を考える。

• e = a + b
• f = c + d
• g = e * f

第1命令と第2命令は独立しており、並列に実行できる。一方、第3命令はそれらの結果に依存するため、待機しなければならない。各命令に1単位時間を要するとすれば、重複のない列では3単位時間が必要であるが、重複させれば2単位時間で完了する。このときILP係数は3/2（1.5）となる。実際のプログラムには、このような依存関係やハザードが数多く存在し、ILPを制限する。すなわち、命令が結果を必要とする真の依存関係であるデータ依存、分岐による制御依存、有限の機能ユニットに起因する資源競合である。実行順序と順次性についての簡単な説明は、基本的な実行モデルを参照されたい。ILPの潜在力が異なるワークロードの例として、グラフィックスや科学技術計算は通常ILPが高い一方、多くの暗号カーネルでは低いことが多い。ワークロードの特性を参照。

ILPを活用する代表的なマイクロアーキテクチャ技法

現代のCPUは、ILPを発見し利用するためにさまざまな手法を採用している。これらの多くは協調して機能する。一部はコンパイラ主導であり、他はハードウェアにより動的に実装される。主な技法は以下のとおりである。

• 命令パイプライン化 — 命令実行を段階に分割し、複数の命令が同時に異なる段階にあるようにする。パイプライン化を参照。
• スーパースカラ実行 — 複数の並列実行ユニットを設け、1サイクル当たり複数命令を完了できるようにする。スーパースカラおよび一般的な実行ユニットを参照。
• アウト・オブ・オーダー実行 — プログラムの意味を保ちながら、準備が整った後続命令を古い命令より先に進める。アウト・オブ・オーダー実行を参照。
• レジスタ・リネーミング — レジスタ名の再利用により生じる偽の依存関係を除去し、独立した操作を並列実行可能にする。レジスタ・リネーミングを参照。
• 投機的実行 — 実行ユニットを稼働させ続けるため、一部の条件が確定する前に命令を実行する。投機実行を参照。
• 分岐予測 — 条件分岐の進行方向を推定し、パイプライン停止を回避して投機実行をより有効にする。分岐予測を参照。

歴史、実用上の限界、メモリウォール

ILP技法は、プロセッサがより高い単一スレッド性能を追求するなかで段階的に発展した。数十年にわたり、パイプライン化とスーパースカラ設計はクロック当たりのスループットを高め、動的スケジューリングにはアウト・オブ・オーダー機構と投機的機構が加わった。しかし、実用上の限界も明らかになった。多くのプログラムには、幅広い実行パイプラインを埋めるほど十分な独立命令がそもそも存在しない。また、依存関係と資源競合が続くため、ハードウェアを追加しても得られる利得は次第に小さくなる。さらに、プロセッサ速度とメモリアクセス時間の差が拡大する現象は、しばしばメモリウォールと呼ばれる。現代のシステムではキャッシュミスによって実行が数十から数百サイクル停止し得る。キャッシュレイテンシと、チップ外メモリの影響に関する議論を参照されたい。こうした現実は、マルチコアチップや、マルチプロセッシング、マルチスレッディングのような多数スレッドシステムを含む、他の並列性の形態およびシステム設計への産業界の移行を時代とともに促した。

用途、区別、注目すべき事項

ILPは、多くの場面で単一スレッド性能とエネルギー効率を改善するための中心的な要素であり続けている。高性能な数値計算コード、メディア処理、遅延に敏感な制御ループは、積極的なILP活用から恩恵を受ける。ILPはスレッドレベル並列性（TLP）を補完する。ILPが単一の命令ストリーム内から並列性を引き出すのに対し、TLPは複数のスレッドまたはプロセスを並行して実行する。設計者は、ILP機構への投資を電力、シリコン面積、複雑さとの兼ね合いで判断する。多くの現代的な設計では、控えめなILPとマルチコアによる拡張を組み合わせるハイブリッドな手法が用いられる。マイクロアーキテクチャ上の考慮事項については、マイクロアーキテクチャを参照。

参考資料とリソース

より深い技術的内容を求める読者に向け、以下のリンクはコンパイラ技法、ハードウェアの説明、ワークロード研究にわたる出発点を提供する。

1. プログラムと並列性の例
2. 依存関係の例と解析
3. ILPのためのコンパイラ戦略
4. プロセッサの実装
5. 設計とエンジニアリングの視点
6. 命令の実行順序
7. ワークロード依存のILP
8. マイクロアーキテクチャの概要
9. パイプライン化の基礎
10. スーパースカラ・プロセッサ
11. 実行ユニットの種類
12. アウト・オブ・オーダー実行
13. レジスタ・リネーミングの詳細
14. 投機的実行の技法
15. 分岐予測の手法
16. キャッシュミスとレイテンシ
17. ILPを超える動向
18. チップ外メモリとレイテンシ
19. マルチプロセッシングのアプローチ
20. マルチスレッディングと並行性