概要
マルチコアプロセッサとGPUが普及するに伴い、プログラムから**並列性**を見つけて活用することが非常に重要になりました。コンパイラはプログラムを分析して安全に並列実行できる部分を自動的に検出し、ループ変換を通じて並列性と局所性の両方を向上させることができます。
1. 並列性の種類
1.1 データ並列性（Data Parallelism）
同じ演算を異なるデータに対して同時に実行します。
// データ並列：各反復が独立
for (i = 0; i < n; i++) {
c[i] = a[i] + b[i];
}
// 4つのプロセッサで分割実行：
// P0: i = 0..n/4-1
// P1: i = n/4..n/2-1
// P2: i = n/2..3n/4-1
// P3: i = 3n/4..n-1
1.2 タスク並列性（Task Parallelism）
異なる作業を同時に実行します。
// タスク並列：3つの関数が独立
result1 = processA(data) // タスク1
result2 = processB(data) // タスク2
result3 = processC(data) // タスク3
// 3つのタスクを同時に実行可能
1.3 パイプライン並列性
データを段階的に処理し、各段階を異なるプロセッサが担当します。
// 3段パイプライン：
// Stage 1: read -> P0
// Stage 2: process -> P1
// Stage 3: write -> P2
// 時間： 1 2 3 4 5
// P0: read1 read2 read3 read4 read5
// P1: proc1 proc2 proc3 proc4
// P2: wrt1 wrt2 wrt3
2. 依存性分析（Dependence Analysis）
ループを並列化するには反復間の依存性を分析する必要があります。
2.1 ループ依存性の種類
// フロー依存性（真の依存性）
for (i = 1; i < n; i++) {
a[i] = a[i-1] + 1; // 反復iが反復i-1の結果に依存
}
// 依存距離（distance） = 1、並列化不可
// 逆依存性
for (i = 0; i < n-1; i++) {
a[i] = a[i+1] + 1; // 読み取り後書き込み
}
// 順序を逆転すれば解決可能
// 出力依存性
for (i = 0; i < n; i++) {
a[i % 2] = b[i]; // 同じ位置に繰り返し書き込み
}
2.2 依存ベクトルと依存距離
多重ネストループでの依存性をベクトルで表現します。
// 2重ループでの依存ベクトル
for (i = 1; i < n; i++) {
for (j = 1; j < m; j++) {
a[i][j] = a[i-1][j-1] + 1;
}
}
// a[i][j]はa[i-1][j-1]に依存
// 依存ベクトル：(1, 1)（i方向距離1、j方向距離1）
2.3 配列依存性テスト
2つの配列アクセスが同じ位置を参照するかを判別するテストです。
**GCDテスト**（必要条件）：
// a[c1*i + c2]とa[c3*j + c4]が同じ位置を参照するには
// c1*i + c2 = c3*j + c4を満たす整数i、jが存在しなければならない
// -> gcd(c1, c3)が(c4 - c2)を割り切る必要がある
// 例：
// a[2*i + 1]とa[2*j]
// gcd(2, 2) = 2、c4 - c2 = 0 - 1 = -1
// 2は-1を割り切れない -> 依存性なし！（並列化可能）
**Banerjeeテスト**（より精密な検査）：
// ループ範囲を考慮して依存性を検査
// a[i + 1]とa[j]（0 <= i,j < n）
// i + 1 = jを満たす(i,j)ペアが範囲内に存在するか？
// 0 <= i < nかつ0 <= i+1 < nなら存在
// -> 依存性あり
2.4 依存性分析の限界
// 正確な依存性分析が難しい場合：
// 1. 間接配列アクセス
a[b[i]] = ... // b[i]の値が不明
// 2. ポインタを通じたアクセス
*p = ... // pが指す位置が不明
// 3. 関数呼び出し
foo(a, i) // fooがaを修正するか不明
// こうした場合保守的に依存性ありと仮定（安全だが並列化不可）
3. ループ変換
3.1 ループ交換（Loop Interchange）
ネストループの順序を入れ替える変換です。並列性の露出やメモリ局所性の向上に使用されます。
// 元：行優先アクセス（Cでは既に最適）
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
a[i][j] = 0;
// 交換後：列優先アクセス
for (j = 0; j < m; j++)
for (i = 0; i < n; i++)
a[i][j] = 0;
交換が合法な条件：**依存ベクトルの辞書式順序が維持**されなければなりません。
// 依存ベクトル(1, -1)の場合：
// 交換後(-1, 1) -> 第1成分が負 -> 不正！
//
// 依存ベクトル(1, 0)の場合：
// 交換後(0, 1) -> 辞書式正 -> 合法！
3.2 ループタイリング / ブロッキング（Loop Tiling/Blocking）
ループを小さなタイル（ブロック）に分割してキャッシュ活用度を高めます。
// 元：行列乗算
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j];
// タイリング後（タイルサイズT）：
for (ii = 0; ii < n; ii += T)
for (jj = 0; jj < n; jj += T)
for (kk = 0; kk < n; kk += T)
for (i = ii; i < min(ii+T, n); i++)
for (j = jj; j < min(jj+T, n); j++)
for (k = kk; k < min(kk+T, n); k++)
c[i][j] += a[i][k] * b[k][j];
タイルサイズTをキャッシュサイズに合わせると：
- a、b、cのT x T部分行列がキャッシュに収まる
- キャッシュミスがO(n^3)からO(n^3/T)に減少
3.3 ループ融合（Loop Fusion）
同じ範囲を巡回する複数のループを一つに合わせます。
// 元：2つの別々のループ
for (i = 0; i < n; i++)
a[i] = b[i] + 1;
for (i = 0; i < n; i++)
c[i] = a[i] * 2;
// 融合後：一つのループ
for (i = 0; i < n; i++) {
a[i] = b[i] + 1;
c[i] = a[i] * 2;
}
融合の利点：
- ループオーバーヘッドの削減
- `a[i]`をレジスタに保持可能（メモリアクセス削減）
- データ局所性の向上
融合条件：2つのループ間で依存方向が逆転してはなりません。
3.4 ループ分裂（Loop Fission/Distribution）
一つのループを複数のループに分割します。
// 元
for (i = 0; i < n; i++) {
a[i] = b[i] + 1; // 独立部分1
c[i] = c[i-1] + a[i]; // 依存部分2
}
// 分裂後
for (i = 0; i < n; i++)
a[i] = b[i] + 1; // 並列化可能！
for (i = 0; i < n; i++)
c[i] = c[i-1] + a[i]; // 逐次実行必要
分裂の利点：
- 並列化可能な部分のみ分離して並列実行
- 各ループの作業セット（working set）が小さくなりキャッシュ効率向上
4. アフィン変換理論の基礎
4.1 アフィン変換とは
ループの反復空間を線形変換して並列性と局所性を同時に最適化する統合フレームワークです。
// 元の反復空間：(i, j)
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
S: a[i][j] = ...
// アフィン変換：新しい反復変数 (p, q) = T * (i, j)
// 例：(p, q) = (i+j, j) -> 傾いた反復空間
4.2 スキュー変換（Skewing）
依存方向を変更して並列性を露出させます。
// 元：依存ベクトル(0,1)と(1,0) -> 両次元とも逐次的
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] = (a[i-1][j] + a[i][j-1]) / 2;
// スキュー：p = i + j, q = j
// 変換後同じp値を持つ反復は並列実行可能
// 変換後の依存ベクトル：(1,1), (1,0) -> p（外部ループ）は逐次、q（内部ループ）は並列可能
4.3 多面体モデル（Polyhedral Model）
アフィン変換を一般化したフレームワークで、現代の自動並列化コンパイラ（Polly、Pluto）で使用されます。
各文の反復ドメインを多面体で、依存性をアフィン関係で、スケジュールをアフィン関数で表現します。
// 多面体表現：
// 文Sの反復ドメイン：0 <= i < n, 0 <= j < m
// これは2次元多面体（長方形）
// スケジュール関数：theta(i,j) = (i, j) （元の順序）
// または theta(i,j) = (i+j, j) （スキュー）
// または theta(i,j) = (j, i) （交換）
5. 局所性最適化（Locality Optimization）
5.1 時間的局所性（Temporal Locality）
最近アクセスしたデータを間もなく再びアクセスする性質です。
// 時間的局所性が良いコード
for (i = 0; i < n; i++) {
sum += a[i]; // sumが毎反復再利用される
}
// 時間的局所性が悪いコード（タイリングで改善可能）
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
b[j] += a[i][j]; // b[j]が外部ループでのみ再利用
5.2 空間的局所性（Spatial Locality）
隣接するメモリ位置を連続してアクセスする性質です。
// 空間的局所性が良いコード（行優先アクセス、C配列レイアウトと一致）
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] = 0; // a[i][0], a[i][1], ... の順でアクセス
// 空間的局所性が悪いコード（列優先アクセス）
for (j = 0; j < n; j++)
for (i = 0; i < n; i++)
a[i][j] = 0; // a[0][j], a[1][j], ... の順でアクセス
// 毎アクセスごとにキャッシュラインが異なる
5.3 局所性とループ変換の関係
| 変換 | 時間的局所性 | 空間的局所性 | 並列性 |
| ---------------- | ------------ | ------------ | ------ |
| ループ交換 | 間接的 | 直接的 | 可能 |
| ループタイリング | 直接的 | 間接的 | 間接的 |
| ループ融合 | 直接的 | 間接的 | 可能 |
| ループ分裂 | 間接的 | 直接的 | 直接的 |
5.4 行列乗算の最適化効果
// 最適化なし：O(n^3) キャッシュミス
// ループ交換：空間的局所性改善
// タイリング（B x B）：O(n^3 / B) キャッシュミス
// タイリング + 交換：最適に近い性能
// 実際の性能差（n = 1000、L1キャッシュ32KB基準）：
// 最適化なし： ~10秒
// ループ交換： ~5秒
// 32x32タイリング：~1秒
// 性能差は10倍に達し得る！
6. 自動並列化の実際
6.1 DOALLループ
すべての反復が独立なループを**DOALL**ループと呼びます。
// DOALL：完全に並列化可能
for (i = 0; i < n; i++)
a[i] = b[i] + c[i];
// OpenMPへの自動変換：
// #pragma omp parallel for
// for (i = 0; i < n; i++)
// a[i] = b[i] + c[i];
6.2 DOACROSSループ
反復間に依存性があるがパイプライン方式で並列化できるループです。
// DOACROSS：依存距離分の並列性が存在
for (i = 1; i < n; i++)
a[i] = a[i-1] + b[i]; // 依存距離1
// パイプライン並列化：
// P0: a[0], a[4], a[8], ...
// P1:（待機）a[1], a[5], a[9], ...
// P2:（待機）（待機）a[2], a[6], ...
// P3:（待機）（待機）（待機）a[3], a[7], ...
まとめ
| 概念 | 説明 |
| ---------------- | -------------------------------------------------------- |
| データ並列性 | 同じ演算を異なるデータに対して同時実行 |
| 依存性分析 | ループ反復間のデータ依存関係の把握 |
| GCDテスト | 配列依存性の必要条件検査 |
| ループ交換 | ネストループの順序変更 |
| ループタイリング | ループを小ブロックに分割してキャッシュ活用を極大化 |
| ループ融合 | 複数のループを一つに統合 |
| ループ分裂 | 一つのループを複数に分離 |
| アフィン変換 | 反復空間の線形変換で並列性と局所性を最適化 |
| 局所性最適化 | キャッシュ活用を極大化するメモリアクセスパターンの最適化 |
並列性検出とループ変換はマルチコア時代の核心的なコンパイラ技術です。正確な依存性分析を基に多様なループ変換を適用すると、プログラマが明示的に並列化しなくてもコンパイラが自動的に並列コードを生成できます。次の記事では、プロシージャ間分析とポインタ分析を扱います。
현재 단락 (1/221)
マルチコアプロセッサとGPUが普及するに伴い、プログラムから**並列性**を見つけて活用することが非常に重要になりました。コンパイラはプログラムを分析して安全に並列実行できる部分を自動的に検出し、ルー...