- Authors
- Name
- Youngju Kim
- @fjvbn20031
概要
現代のプロセッサは複数の命令を同時に実行して性能を高めます。これを命令レベル並列性（Instruction-Level Parallelism、ILP）と呼びます。コンパイラはILPを最大限活用するよう命令の順序を再配置（スケジューリング）する役割を担います。
この記事では、ILPの概念、これを支援するプロセッサアーキテクチャ、そしてコンパイラの命令スケジューリング技法を見ていきます。
1. 命令レベル並列性（ILP）
1.1 基本概念
ILPはプログラム内で同時に実行できる命令がどれだけあるかを示します。
// ILPが高いコード
a = x + y // この3つの命令は互いに独立
b = p + q // 同時実行可能
c = r - s
// ILPが低いコード
a = x + y // 逐次的依存性
b = a + z // aに依存
c = b * 2 // bに依存
1.2 データ依存性の種類
命令間の依存性がILPを制限します：
真の依存性（True Dependence、RAW：Read After Write）
a = b + c // aを書き込み
d = a + e // aを読み取り（待機必要）
逆依存性（Anti-Dependence、WAR：Write After Read）
a = b + c // bを読み取り
b = d + e // bを書き込み（名前変更で解決可能）
出力依存性（Output Dependence、WAW：Write After Write）
a = b + c // aを書き込み
a = d + e // aを再び書き込み（順序維持必要）
逆依存性と出力依存性はレジスタ名前変更（register renaming）で解決できるため、名前依存性とも呼ばれます。
2. ILPのためのプロセッサアーキテクチャ
2.1 パイプライニング（Pipelining）
命令の実行を複数のステージに分けて、各ステージを重ねて実行します。
// 5段パイプライン：IF(Fetch)、ID(Decode)、EX(Execute)、MEM、WB(Writeback)
時間： 1 2 3 4 5 6 7
命令1： IF ID EX MEM WB
命令2： IF ID EX MEM WB
命令3： IF ID EX MEM WB
// 理想的には毎クロック1つの命令が完了
パイプラインハザード（hazard）：
// データハザード（RAW）
ADD R1, R2, R3 // R1に結果を書き込み（WBステージ）
SUB R4, R1, R5 // R1を読み取り（IDステージ）- まだ値が準備できていない！
// 解決：フォワーディング（forwarding）またはストール（stall）
ADD R1, R2, R3
NOP // バブル挿入（stall）
SUB R4, R1, R5
// コンパイラが独立した命令を間に挿入するとstallを防止
ADD R1, R2, R3
MUL R6, R7, R8 // 独立した命令で空きスロットを埋める
SUB R4, R1, R5
2.2 スーパースカラプロセッサ（Superscalar）
1クロックで複数の命令を同時に発行（issue）します。
// 2-issueスーパースカラプロセッサ
時間： 1 2 3
スロット1：ADD MUL LD
スロット2：SUB AND ST
// 理想的には毎クロック2個の命令が完了
// （IPC = Instructions Per Cycle = 2）
2.3 VLIWアーキテクチャ
VLIW（Very Long Instruction Word）は一つの長い命令に複数の演算を束ねます。
// VLIW命令（4演算スロット）
// | ALU1 | ALU2 | MEM | BRANCH |
// | ADD R1.. | MUL R3.. | LD R5.. | NOP |
// 各スロットは独立した機能ユニットで実行
// 並列実行の責任はコンパイラにある
スーパースカラ vs VLIW：
| 特性 | スーパースカラ | VLIW |
|---|---|---|
| 並列性の決定 | ハードウェア（動的） | コンパイラ（静的） |
| ハードウェア複雑度 | 高い | 低い |
| コード互換性 | 高い | 低い |
| コンパイラ負担 | 普通 | 高い |
| 代表的な製品 | Intel x86、ARM | Intel Itanium、TI DSP |
3. 命令スケジューリング
3.1 基本ブロックスケジューリング
基本ブロック内で命令順序を再配置してパイプラインstallを最小化します。
依存性DAGの構成：
// 元のコード：
// 1: LD R1, a // ロードレイテンシ = 2
// 2: ADD R2, R1, R3 // R1に依存（RAW）
// 3: LD R4, b // 独立
// 4: MUL R5, R4, R6 // R4に依存（RAW）
// 5: ADD R7, R2, R5 // R2、R5に依存
// 依存性DAG：
// 1 --2--> 2 --1--> 5
// 3 --2--> 4 --1--> 5
// （辺の重み = レイテンシ）
3.2 リストスケジューリング（List Scheduling）
リストスケジューリングは基本ブロック内で最も広く使われるスケジューリングアルゴリズムです。
アルゴリズム：リストスケジューリング
1. 依存性DAGを構成
2. 各ノードの優先度を計算（通常クリティカルパス長）
3. 依存性がない命令を準備リスト（ready list）に追加
4. while 準備リストが空でない：
a. 優先度が最も高い命令を選択
b. 現在のサイクルに発行
c. 後続命令の依存性が解消されたら準備リストに追加
3.3 リストスケジューリングの例
// 依存性DAG（レイテンシ）：
// LD a(2) -> ADD(1) -> ST(1)
// LD b(2) -> MUL(3) -> ST(1)
// 優先度（ルートまでのクリティカルパス長）：
// LD a: 2+1+1 = 4
// LD b: 2+3+1 = 6（より高い優先度）
// ADD: 1+1 = 2
// MUL: 3+1 = 4
// ST(ADD結果): 1
// ST(MUL結果): 1
// スケジューリング：
// サイクル1：LD b（優先度6、最高）
// サイクル2：LD a（LD b結果待ち中、別のものを発行）
// サイクル3：MUL（LD b結果準備完了、サイクル1+2=3）
// サイクル4：ADD（LD a結果準備完了、サイクル2+2=4）
// サイクル5：ST（ADD結果、サイクル4+1=5）
// サイクル6：ST（MUL結果、サイクル3+3=6）
// 元の順序で実行すると7サイクル必要
// スケジューリング後6サイクルに短縮
4. ソフトウェアパイプライニング（Software Pipelining）
4.1 概念
ループの複数の反復を重ねて実行するようコードを変換する技法です。ハードウェアパイプライニングと類似のアイデアをソフトウェアレベルで適用します。
// 元のループ（各反復に3命令、各1サイクル）
// 反復i： A(i), B(i), C(i)
// 反復i+1：A(i+1), B(i+1), C(i+1)
// 時間： 1 2 3 4 5 6 7
// 元： A(0) B(0) C(0) A(1) B(1) C(1) A(2)...
// ソフトウェアパイプライニング後：
// 時間： 1 2 3 4 5
// 元： A(0) B(0) C(0)
// A(1) B(1) C(1)
// A(2) B(2) C(2)
//
// 定常状態（steady state）カーネル：
// 時間： ... k k+1 k+2 ...
// C(i) C(i+1) ...
// B(i+1) B(i+2) ...
// A(i+2) A(i+3) ...
4.2 構成
ソフトウェアパイプライニングされたループは3つの部分で構成されます：
// 1. プロローグ（prologue）：パイプラインの充填
A(0)
A(1), B(0)
// 2. カーネル（kernel）：定常状態の反復
loop:
A(i+2), B(i+1), C(i) // 3つの反復が重なる
i = i + 1
if i < n-2 goto loop
// 3. エピローグ（epilogue）：パイプラインの排出
B(n-1), C(n-2)
C(n-1)
4.3 利点
- ループ本体の**スループット（throughput）**最大化
- リソース（機能ユニット、レジスタ）のバランスの取れた活用
- ループ展開と組み合わせるとさらに効果的
5. レジスタ割り当てとスケジューリングの相互作用
5.1 相反する目標
レジスタ割り当てと命令スケジューリングは互いに相反する目標を持ちます：
// スケジューリングに有利なコード（レジスタを多く使用）
LD R1, a
LD R2, b // R1待ち中に別のロードを実行
LD R3, c
ADD R4, R1, R2 // R1準備完了
MUL R5, R3, R4
// レジスタ割り当てに有利なコード（レジスタを少なく使用）
LD R1, a
ADD R1, R1, b // R1を即座に使用（stall可能！）
LD R1, c
MUL R1, R1, R1
5.2 解決方法
方法1：スケジューリング先、割り当て後
1. 仮想レジスタ（無限レジスタ）でスケジューリングを実行
2. スケジューリングされたコードに対してレジスタ割り当て
3. spillが発生したらspillコード挿入後に再スケジューリング
方法2：割り当て先、スケジューリング後
1. 先にレジスタ割り当てを実行
2. 割り当てられたコードに対してスケジューリング
3. スケジューリングの自由度が制限される（同じレジスタ使用による偽の依存性）
方法3：統合アプローチ
1. レジスタ割り当てとスケジューリングを同時に考慮
2. より良い結果が得られるが複雑度が高い
ほとんどの実用的なコンパイラは方法1を使用します。
6. グローバルスケジューリング
6.1 基本ブロックを超えたスケジューリング
基本ブロックサイズが小さいとスケジューリングの自由度が制限されます。グローバルスケジューリングは複数の基本ブロックにまたがって命令を移動します。
6.2 トレーススケジューリング（Trace Scheduling）
最も頻繁に実行される経路（トレース）を見つけ、その経路全体を一つの単位としてスケジューリングします。
// フローグラフ：
// B1（実行確率100%）
// |
// B2（if cond）-- 90% --> B3
// |
// 10% --> B4
// トレース：B1 -> B2 -> B3（最も頻繁な経路）
// この経路を一つの長いブロックのようにスケジューリング
// B2からB3に命令を移動したり
// B1からB2に命令を移動できる
// （頻度の低い経路B4に対する補償コードが必要）
6.3 スーパーブロック（Superblock）
トレースから中間入口点を除去してスケジューリングを単純化したものです。
// スーパーブロック：一つの入口点、複数の出口点
// entry -> A -> B -> C -> exit1
// |
// v
// exit2
//
// 途中から入る辺がないためコード移動がより自由
7. VLIWコード生成
7.1 VLIWの特徴
VLIWプロセッサではコンパイラが並列実行の全責任を負います。
// VLIW命令パケット（3スロット：ALU、MEM、BR）
// 各スロットに独立した演算を配置
// サイクル1：| ADD R1,R2,R3 | LD R4, mem1 | NOP |
// サイクル2：| MUL R5,R4,R6 | LD R7, mem2 | NOP |
// サイクル3：| SUB R8,R5,R7 | ST mem3, R1 | BEQ R8, L1 |
7.2 NOP問題
ILPが不足すると空きスロットがNOPで埋められ、コードサイズが大きくなります。
// ILPが低いコード：
// | ADD R1,R2,R3 | NOP | NOP |
// | MUL R4,R1,R5 | NOP | NOP | // すべての演算が依存的
// | SUB R6,R4,R7 | NOP | NOP |
// 解決：ループ展開 + ソフトウェアパイプライニングでILPを増加
7.3 バンドル圧縮
NOPによるコードサイズ増加を減らすためにバンドル圧縮技法を使用します：
- 実際に使用されるスロットのみエンコード
- ヘッダビットでどのスロットがアクティブかを表示
まとめ
| 概念 | 説明 |
|---|---|
| ILP | 同時実行可能な命令の水準 |
| パイプライニング | 命令実行ステージを重ねて実行 |
| スーパースカラ | ハードウェアが動的に複数命令を同時発行 |
| VLIW | コンパイラが静的に並列演算を一つの長い命令に配置 |
| リストスケジューリング | 優先度ベースの基本ブロックスケジューリングアルゴリズム |
| ソフトウェアパイプライニング | ループの複数反復を重ねて実行 |
| トレーススケジューリング | 頻繁な実行経路を一つの単位としてスケジューリング |
命令スケジューリングは現代プロセッサの性能を最大限引き出す核心的なコンパイラ技法です。特にVLIWアーキテクチャではコンパイラのスケジューリング能力がプロセッサの性能を直接決定します。次の記事では、より大きな単位の並列性であるデータ並列性とループ変換を扱います。