パイプラインのハザードとストール・CPIの計算

パイプラインの停止回数は、先行命令の値が使える時刻と、後続命令がその値を必要とする時刻を比べると判断できます。 同じレジスタが現れるだけで停止と決めず、命令ごとのIF・ID・EX・MEM・WBを横に並べます。 ここでは短い命令列で、転送なし、転送あり、ロード直後の違いを計算します。

ハザードの3種類を分ける

ハザードは、命令を予定どおりに重ねて実行すると、正しく処理できない状況です。何が足りないのかを分けると、必要な対処も変わります。

ストールは処理を待たせることです。バブルは、有効な処理を行わない空きが段を進んでいくものです。後の図では、依存する命令とその後続を止めても、値を作る先行命令は進めます。

計算に使う5段パイプラインの条件

以後の図は、1サイクルに最大1命令を投入し、命令順に進むモデルです。各段は1サイクル、命令メモリとデータメモリは別に用意します。キャッシュミスや例外は起きないものとします。

WBはサイクルの前半、IDのレジスタ読み出しは後半とし、同じサイクルに書かれた値を読めるものとします。 転送ありの例では、EX/MEMとMEM/WBのパイプラインレジスタから、後続命令のEX入力へ値を渡せます。 これはこの記事の計算条件です。問題文の読み書き時刻や転送先が違うときは、その指定を使ってください。

命令は説明用の表記で、ADD r1, r2, r3はr1へr2 + r3を書き、SUB r4, r1, r5はr4へr1 − r5を書きます。LD r1, [r2]は、r2が指すアドレスの値をr1へ読み込みます。

データハザードとフォワーディング

転送がなければ、レジスタへ書き戻すまで待つ

次の1行目はr1を更新し、2行目はそのr1を使います。停止せずに進むと、2行目のIDはサイクル3ですが、r1のWBはサイクル5です。 転送がなければ、2行目をIDにとどめ、サイクル5の後半に新しいr1を読みます。EXへ進めるのは6なので、通常のEX開始時刻4から2サイクル遅れます。

3行目も先に進めません。単純な順序実行なので、後続のIF側も保持します。サイクル4・5では、先行命令はMEM・WBへ進みますが、EXに新しい有効な命令が入らず、バブルが生じます。

WBとIDで同一サイクルの値を受け渡せない指定なら、IDで新しいr1を読めるのはサイクル6、EXは7です。その条件では停止は3サイクルになります。2か3かの違いは、この読み書き時刻から判定します。

転送があれば、ALUの結果は次のEXに間に合う

1行目の加算結果はサイクル3のEX終了時には得られています。 EX/MEMに保持した値を2行目のEXへ渡せば、サイクル4に減算できます。 IDで読んだ古い値をそのまま使わず、EXの入力を新しい値に切り替えるため、WBまで待つ必要がありません。

同じr1へ複数の先行命令が書く場合は、後続命令から見て直前の書込みを選びます。 さらに手前の命令の古い結果を転送すると、停止しなくても計算結果が誤ります。 ロードのEX結果はアドレスなので、読み出したデータの代わりに転送してはいけません。 転送経路と各時刻の関係は、UC Berkeleyのデータハザードの講義ノートでも確認できます。

RAW・WAR・WAWを読み書きの順序で区別する

同じレジスタに対するアクセスでも、守るべき順序は異なります。次のRは読出し、Wは書込みを表します。

読むだけのRARは値を変更しないので、読出し間に守るべきデータの更新順序はありません。 WAR・WAWが問題にならないのは、上記の単純なモデルの性質です。 命令が順序を変えて完了するプロセッサなどへ、そのまま一般化しないでください。 この区別はHarvardの計算機アーキテクチャ講義資料でも説明されています。

ロード直後に1サイクル待つ理由

ロードユース・ハザードは、ロードした値を、すぐ後の命令が使おうとする場合のデータハザードです。 1行目のロード結果が得られるのはサイクル4のMEM終了時。 停止なしでは2行目もサイクル4にEXへ入り、その開始時にr1を必要とします。サイクルの終わりに得られる値を、同じサイクルの始めへ戻すことはできません。

そこで2行目のEXをサイクル5へ遅らせます。MEM/WBからEXへロード結果を渡せるため、追加の停止は1サイクルです。 3行目がIF側で保持される時間も同じ停止によるものなので、これを別の1サイクルとして加算しません。

無関係な命令を間に入れると、待つ時間を使える

この例の3行目はr5へr6 − r7を書くだけで、ほかの2命令の入出力と重なりません。 2・3行目を入れ替えると、ロードを使う加算のEXはもともとサイクル5になります。ロード結果の到着を待つための追加停止がなくなり、全体は8から7サイクルへ短くなります。

これは例外や外部への作用を考えない、上記の命令列での並べ替えです。 一般のプログラムでは、レジスタ依存に加え、メモリの読書き、分岐、例外の順序も守る必要があります。 単に命令を1個挟めばよいわけではありません。また、ストアへ渡すデータやIDで比較する分岐は、値を使う段と転送先がこの例と違うため、個別に確認します。

構造ハザードは資源の同時使用を見る

ここだけ、命令とデータで同じ1ポートのメモリを使うモデルへ変えます。 最初のロードがサイクル4にMEMでデータを読むとき、4番目の命令もIFで命令を読みたい状況を考えます。 1サイクルに一方のアクセスしか受け付けないなら、両方は進められません。ロードを優先する設計では、そのサイクルの命令取得を待たせます。

2命令が別々のレジスタを使っていても、この競合は起きます。転送でデータ依存を解消しても、メモリの受付口は増えません。 記事の基本モデルのように命令・データのメモリを分けると、このIFとMEMの競合を避けられます。UC Berkeleyの構造ハザードの説明では、メモリとレジスタファイルの両方について、同時アクセスを扱っています。

制御ハザードは分岐の確定時刻を見る

分岐の損失は、5段であることだけでは決まりません。 例えば分岐がサイクル1にIFへ入り、3のEX終了時に条件と行き先が確定する設計で、分岐しないと予測して命令を取り込む場合を考えます。

最初から正しい命令をサイクル2に取り込めた場合と比べ、正しい経路の開始は2サイクル遅れます。 これがこの条件での分岐予測失敗の損失です。捨てる2命令は、完了した命令数には含めません。 予測が当たる場合は、ほかに停止要因がなければこの損失はありません。

分岐の確定がMEMまで遅れる設計、予測せずに待つ設計、分岐条件のデータを待つ場合では、数え直す必要があります。 例えばUC Berkeleyの制御ハザードの例はMEMで分岐を反映するため、この記事のEX確定の例とは破棄する命令数が違います。 問題文の条件を読まず、分岐は常に2サイクルと覚えないでください。

サイクル数とCPI・実行時間の計算

最初のIFから、最後のWBまで数える

空の5段パイプラインへN命令を1サイクルずつずらして入れ、停止なしで最後のWBまで実行すると、N + 4サイクルです。 Nは1以上で、ループも実際に実行する回数だけ数えます。追加の停止による遅れをSとすると、次のようになります。

ロード直後の3命令の図ではN = 3、S = 1なので、C = 8、CPI = 8/3です。 並べ替えた図はS = 0なので、C = 7、CPI = 7/3。停止なしでも、短い列を最初から最後まで測ったCPIは1を超えます。 1命令の実行時間が1サイクルになったという意味でもありません。

パイプラインの充填・排出を無視する指定や、十分長い定常状態の計算では、4の項を除いて考えます。 また、複数のハザードが同じ時間帯に重なる場合は、その名前の数だけ停止を足さず、実際に増えたサイクルを表から数えます。 有効に完了した命令数をNとするなら、破棄された命令やハードウェアが挿入したバブルはNに入れません。 ソフトウェアに明示されたNOPを命令数へ含める指定なら、その定義に合わせます。

命令の割合から求めるときは、分母を確認する

充填・排出を無視し、ロードが全命令の20%、そのうち直後の命令が結果を使う割合が25%だとします。 各該当箇所で1サイクル停止し、ほかに遅れがなければ、1命令あたりの追加停止は0.20 × 0.25 = 0.05です。 CPIは1.05になります。25%は全命令に対する割合ではないので、そのまま0.25を足しません。

さらに、全命令の10%が分岐、その分岐の20%で予測が外れ、1回の損失が2サイクルなら、増分は0.10 × 0.20 × 2 = 0.04です。 この損失と先ほどの停止が重ならず、ほかに損失がない条件では、CPIは1.09です。 予測誤り率の分母が全命令なのか分岐命令なのかも、区別してください。

サイクル数とクロック周期を掛ける

単純な段間レジスタのモデルでは、クロック周期は最も遅い段の組合せ回路の遅延に、段間レジスタなどのオーバーヘッドを加えて決めます。 各段の遅延を全部足すのは、このパイプラインのクロック周期の計算ではありません。

例えば段の遅延が順に180、120、210、240、90 psで、共通のレジスタのオーバーヘッドが20 psなら、最小周期は260 psです。 8サイクルなら実行時間は2080 ps = 2.08 ns、IPCは3/8 = 0.375命令/サイクルです。 CPIだけが小さくても、クロック周期が長くなれば実行時間は短くならない場合があります。

院試の問題で確認する条件

東大コンピュータ科学・2026年度入試の問題3は、 2025年8月実施の問題です。5段、転送元と転送先、ロード直後の停止が指定され、その理由も問われています。 このように、命令名だけでなくモデルの条件を使って説明する練習が必要です。

1. 各命令の読出し先・書込み先を抜き出し、後続命令へ渡す値を結ぶ。
2. 値が得られる段、使う段、転送経路、同一サイクルの読書き可否を確認する。
3. 停止なしの時系列を置き、間に合わない箇所だけ後ろへずらす。後続命令も合わせてずらす。
4. 分岐や資源競合の条件を反映し、最初から最後まで数えるのか、定常状態だけかを確かめる。
5. サイクル数、CPI、クロック周期、秒単位の時間を分けて答える。

大学別の範囲は東大コンピュータ科学の過去問・対策と九大情報理工の専門科目ガイドで確認できます。 下の商品ページには、大学別の解答PDFの収録年度・科目、見本、価格を掲載しています。 この記事の短い命令列は仕組みを学ぶための例です。購入するPDFの収録問題は、各商品の一覧で確認してください。