応用情報技術者 2009年 秋期 午前2 問09

パイプライン実行時間【午前2解説】

正解の理由

解法ステップ

1. 最初の命令の完了までの時間を考える：パイプラインに $D$ ステージがあり各ステージが1ピッチで処理されるため、最初の命令は $D$ ピッチかかる。時間は $D\times P$。
2. 2 命令目以降の完了間隔を考える：パイプラインが満たされた後は1命令あたり1ピッチで完了するので、残り $I-1$ 命令に対して $(I-1)\times P$。
3. 合計を足す：$D\times P+(I-1)\times P=(I+D-1)\times P$。
4. 整理して最終式：$(I+D-1)\times P$。

選択肢別の誤答解説

• ア: $(I+D)\times P$
  最初の命令の完了を $D$ ピッチと数えれば、残りは $I-1$ 命令分のピッチで足りるため、$+1$ ピッチ分だけ過大評価している（1ピッチ分の二重カウント）。
• イ: $(I+D-1)\times P$
  正しい。最初が $D$ ピッチ、その後が1ピッチずつで合計 $(D+(I-1))\times P$。
• ウ: $(I\times D)+P$
  命令ごとに $D$ ピッチかかる（逐次実行の合計）と仮定している形。だがパイプライン並列化により各命令は並列に進むため、この式は並列効果を反映しておらず過大評価。
• エ: $(I\times D-1)+P$
  括弧の位置と意味が曖昧で論理的に成り立たない。もし $(I\times D)-1+P$ と解釈しても、上と同様に逐次時間を基にした誤った計算になる。

よくある誤解

• 「初期充填時間は $D-1$ だ」と考える誤解
  文脈に注意：最初の命令が完了するまでのレイテンシは明確に $D$ ピッチです。$D-1$ は「最初の命令と2番目以降の命令の差（起動オーバーヘッド）」を指す場合に使う値で、用途を混同すると誤る。
• 各ステージの処理を命令単位で合算する誤解
  各命令が逐次に全ステージを通る時間を単純に足すと並列化効果を無視するため実際より大きな値になる。
• ピッチとステージの混同
  「ピッチ P がステージごとの時間」だが、問題文を読み違えピッチを「命令間隔」と誤認すると計算を誤る。

補足コラム

• レイテンシとスループットの整理
  レイテンシ（ある命令の完了までの時間）＝ $D\times P$。スループット（単位時間あたりの完了命令数）は理想的には $1/P$（1 命令／ピッチ）。総時間はレイテンシ＋（命令数−1）×ピッチで与えられるため、$I$ が十分大きい場合はほぼ $I\times P$（スループット主導）になりますが、短いバッチでは起動オーバーヘッド $(D-1)\times P$ が無視できません。
• ハザードやバブルがある場合
  問題ではハザード無視とあるが、実際はバブル（ストール）で「追加のピッチ」が入ると式は $(I+D-1+\mathrm{stalls})\times P$ のように修正されます。

FAQ