単一の半導体において、単一のプログラム中から、いかに並列に計算するかを、命令レベル並列性（ILP, Instruction Level Parallelism）といいます。一方で、複数のプログラムを同時に並列に実行するスレッドレベル並列性（TLP, Thread Level Parallelism）もあり、TLPの処理のためにマルチコアの利用が進んできています。
本記事の内容
- 命令レベル並列性（ILP）の基本概念
- パイプライン処理の仕組み
- データハザードとその対策
- スーパースカラアーキテクチャ
- Pythonでのパイプラインシミュレーション
パイプライン処理の基礎
パイプライン処理は、ILPを活用する最も基本的な手法です。CPUの命令実行を複数のステージに分割し、各ステージを並列に動作させます。
5段パイプライン
RISC型プロセッサの典型的な5段パイプラインは以下の通りです。
- IF (Instruction Fetch): 命令の読み込み
- ID (Instruction Decode): 命令のデコードとレジスタ読み出し
- EX (Execute): 演算の実行
- MEM (Memory Access): メモリアクセス
- WB (Write Back): 結果のレジスタへの書き戻し
スピードアップ
パイプラインのない場合、1命令に $k$ クロックサイクルかかるとします。$n$ 個の命令を実行する場合、パイプラインなしでは、
$$ T_{\text{seq}} = n \cdot k $$
クロックサイクルが必要です。$k$ 段パイプラインでは、最初の命令が完了するまで $k$ サイクルかかりますが、以降は1サイクルごとに1命令が完了します。
$$ T_{\text{pipe}} = k + (n – 1) $$
スピードアップ比は、
$$ S = \frac{T_{\text{seq}}}{T_{\text{pipe}}} = \frac{nk}{k + (n-1)} $$
$n \to \infty$ の極限では $S \to k$ となり、理想的にはステージ数と同じ倍率の高速化が得られます。
データハザード
パイプライン処理では、連続する命令間のデータ依存により、パイプラインが停止（ストール）する場合があります。これをデータハザードと呼びます。
ハザードの種類
3種類のデータハザードが存在します。
- RAW（Read After Write）: 先行命令の書き込み結果を後続命令が読む。最も頻繁に発生
- WAR（Write After Read）: 先行命令の読み出し前に後続命令が書き込む
- WAW（Write After Write）: 同じレジスタへの2つの書き込みの順序が逆転する
フォワーディング（バイパス）
RAWハザードの主要な解決策がフォワーディングです。先行命令の演算結果を、レジスタへの書き戻しを待たずに後続命令のEXステージに直接転送します。
フォワーディングにより、多くのRAWハザードを1サイクルのストールなしで解消できます。
スーパースカラアーキテクチャ
スーパースカラプロセッサは、1クロックサイクルに複数の命令を同時に発行・実行できるアーキテクチャです。$m$ 命令同時発行のスーパースカラの理想的なスピードアップは、
$$ S_{\text{ideal}} = m \cdot k $$
実際にはデータ依存や資源の競合により、理想値に達することは稀です。実効IPC（Instructions Per Cycle）は通常1.5から3程度です。
Pythonでパイプラインをシミュレーション
import numpy as np
import matplotlib.pyplot as plt
def simulate_pipeline(n_instructions, n_stages, hazard_rate=0.0):
"""パイプライン処理のシミュレーション
Parameters
----------
n_instructions : int
実行する命令数
n_stages : int
パイプラインの段数
hazard_rate : float
ハザード発生率（0.0 ~ 1.0）
Returns
-------
total_cycles : int
総サイクル数
"""
total_cycles = n_stages # 最初の命令の完了まで
stalls = 0
for i in range(1, n_instructions):
# ハザードの確率的発生
if np.random.random() < hazard_rate:
stalls += 1 # 1サイクルのストール
total_cycles += (n_instructions - 1) + stalls
return total_cycles, stalls
# パラメータ
n_instructions = 1000
n_stages = 5
# ハザード率を変化させたシミュレーション
hazard_rates = np.linspace(0, 0.5, 50)
speedups = []
ipcs = []
np.random.seed(42)
for hr in hazard_rates:
cycles, stalls = simulate_pipeline(n_instructions, n_stages, hr)
seq_cycles = n_instructions * n_stages
speedups.append(seq_cycles / cycles)
ipcs.append(n_instructions / cycles)
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# スピードアップ
axes[0].plot(hazard_rates * 100, speedups, 'b-', linewidth=2)
axes[0].axhline(y=n_stages, color='r', linestyle='--',
label=f'Ideal ({n_stages}x)')
axes[0].set_xlabel('Hazard Rate [%]')
axes[0].set_ylabel('Speedup')
axes[0].set_title('Pipeline Speedup vs Hazard Rate')
axes[0].legend()
axes[0].grid(True)
# IPC
axes[1].plot(hazard_rates * 100, ipcs, 'g-', linewidth=2)
axes[1].axhline(y=1.0, color='r', linestyle='--', label='Ideal IPC = 1.0')
axes[1].set_xlabel('Hazard Rate [%]')
axes[1].set_ylabel('IPC (Instructions Per Cycle)')
axes[1].set_title('IPC vs Hazard Rate')
axes[1].legend()
axes[1].grid(True)
plt.tight_layout()
plt.show()
# アムダールの法則
def amdahl_speedup(f_parallel, n_cores):
"""アムダールの法則によるスピードアップ"""
return 1 / ((1 - f_parallel) + f_parallel / n_cores)
n_cores_range = np.arange(1, 65)
fig, ax = plt.subplots(figsize=(8, 6))
for f in [0.5, 0.75, 0.9, 0.95, 0.99]:
s = [amdahl_speedup(f, n) for n in n_cores_range]
ax.plot(n_cores_range, s, label=f'f = {f}')
ax.set_xlabel('Number of Cores')
ax.set_ylabel('Speedup')
ax.set_title("Amdahl's Law")
ax.legend()
ax.grid(True)
plt.tight_layout()
plt.show()
アムダールの法則
並列化可能な部分の割合を $f$、プロセッサ数を $n$ とすると、スピードアップの上限は次のように与えられます。
$$ S(n) = \frac{1}{(1-f) + \frac{f}{n}} $$
$n \to \infty$ の極限では、
$$ S_{\max} = \frac{1}{1 – f} $$
となり、逐次実行部分の割合 $1-f$ がボトルネックとなります。例えば、プログラムの5%が逐次実行の場合、いくらプロセッサを増やしてもスピードアップは最大20倍です。
まとめ
本記事では、命令レベル並列性（ILP）について解説しました。
- パイプライン処理は命令を複数ステージに分割して並列実行する基本手法である
- 理想的には $k$ 段パイプラインで $k$ 倍のスピードアップが得られる
- データハザード（特にRAW）がパイプラインの性能を制限する
- フォワーディングによりハザードの影響を軽減できる
- アムダールの法則により、並列化のスピードアップには理論的な上限がある