上記のパイプラインでは、条件付き分岐の方向とターゲットは 3 番目のサイクルの終わりまで使用できないため、分岐後の正しい次の命令は、4 番目のサイクルの開始まで (確実に) フェッチできません。
デザイン1
分岐後の命令アドレスの遅延可用性を処理する明白な方法は、単純に待機することです。これは、デザイン 1 が 2 サイクルの間ストールすることによって行うことです (これは、実際のプログラムの一部ではない 2 つのノーオペレーションをフェッチすることと同じです)。これは、コンパイラによって 2 つのノーオペレーション命令が挿入されたかのように、選択されたパスと選択されていないパスの両方で 2 サイクルが無駄になることを意味します。
パイプラインの図を次に示します (ST はストール、NO はノーオペレーション、XX はキャンセルされた命令、UU は役に立たない命令、I1、I2、および I3 は分岐前の 3 つの命令です [元のプログラムの順序で] BI は分岐命令、I5、I6、および I7 は分岐後のフォールスルー命令、I21、I22、および I23 は選択されたパスの先頭にある命令、IF は命令です。フェッチ ステージ、DE はデコード、BR は分岐解決、S1 は BR の後のステージです):
Taken Not taken
IF DE BR S1 ... IF DE BR S1 ...
cycle 1 BI I3 I2 I1 BI I3 I2 I1
cycle 2 ST BI I3 I2 ST BI I3 I2
cycle 3 ST ST BI I3 ST ST BI I3
cycle 4 I21 ST ST BI I5 ST ST BI
cycle 5 I22 I21 ST ST I6 I5 ST ST
デザイン 2
IF ステージの最後までに分岐の存在を検出する必要がなくなり、ハードウェアがパイプラインに no-op を効果的に挿入するのではなく (つまり、実行されなかった場合)、いくつかの有用な作業を実行できるようにするため (つまり、ハードウェアは、分岐が 3 番目のパイプライン ステージで解決されるまで、分岐を他の命令として扱うことができます。これは、すべての分岐が取られないと予測しています。分岐が行われると、分岐後にフェッチされた 2 つの命令が取り消されます (事実上ノーオペレーションに変わります)。これはデザイン2です：
Taken Not taken
IF DE BR S1 ... IF DE BR S1 ...
cycle 1 BI I3 I2 I1 BI I3 I2 I1
cycle 2 I5 BI I3 I2 I5 BI I3 I2
cycle 3 I6 I5 BI I3 I6 I5 BI I3
cycle 4 I21 XX XX BI I7 I6 I5 BI
cycle 5 I22 I21 XX XX I8 I7 I6 I5
デザイン3
分岐が行われないことを常に予測すると、分岐が行われるたびに 2 サイクルが無駄になるため、この無駄を避けるために 3 番目のメカニズムである遅延分岐が開発されました。遅延分岐では、ハードウェアは常に分岐後に遅延スロット命令を実行します (キャンセルしません) (例では 2 つの命令)。遅延スロット命令を常に実行することで、パイプラインが簡素化されました。コンパイラの仕事は、これらの遅延スロットを有用な命令で埋めようとすることです。
分岐の前から (遅延分岐のないプログラムで) 実行された命令は、実行されるパスに関係なく役立ちます (ただし、依存関係によって、分岐後にコンパイラがそのような命令をスケジュールできなくなる可能性があります)。コンパイラーは遅延スロットを取得パスまたは非取得パスからの命令で埋めることができますが、遅延スロット命令はキャンセルされないため (またはパスが結合された後)、そのような命令は他のパスによって使用される状態を上書きする命令であってはなりません (予測）。(if-then-else コンストラクトでよくあるように、両方のパスが結合する場合、遅延スロットは結合ポイントから埋められる可能性があります。ただし、そのような命令は通常、結合前のパスの少なくとも 1 つからの命令に依存します。 、この依存関係により、遅延スロットでの使用が妨げられます。
ケース 3.1 (遅延分岐設計の最悪のケース) では、コンパイラは遅延スロットを埋めるための有用な命令を見つけることができなかったため、ノーオペレーションで埋める必要があります。
Taken Not taken
IF DE BR S1 ... IF DE BR S1 ...
cycle 1 BI I3 I2 I1 BI I3 I2 I1
cycle 2 NO BI I3 I2 NO BI I3 I2
cycle 3 NO NO BI I3 NO NO BI I3
cycle 4 I21 NO NO BI I5 NO NO BI
cycle 5 I22 I21 NO NO I6 I5 NO NO
これは、デザイン 1 (ストール 2 サイクル) と同じ性能です。
ケース 3.2 (遅延分岐設計の最良のケース) では、コンパイラは分岐の前に遅延スロットを満たす 2 つの命令を見つけました。
Taken Not taken
IF DE BR S1 ... IF DE BR S1 ...
cycle 1 BI I1 ... BI I1 ...
cycle 2 I2 BI I1 ... I2 BI I1 ...
cycle 3 I3 I2 BI I1 I3 I2 BI I1
cycle 4 I21 I3 I2 BI I5 I3 I2 BI
cycle 5 I22 I21 I3 I2 I6 I5 I3 I2
この場合、すべてのパイプライン スロットは、分岐が実行されるかどうかに関係なく、有用な命令で満たされます。パフォーマンス (CPI) は、分岐の遅延解決のない理想的なパイプラインと同じです。
ケース 3.3 では、コンパイラは遅延スロットを取得したパスからの命令で埋めました。
Taken Not taken
IF DE BR S1 ... IF DE BR S1 ...
cycle 1 BI I3 I2 I1 BI I3 I2 I1
cycle 2 I21 BI I3 I2 I21 BI I3 I2
cycle 3 I22 I21 BI I3 I22 I21 BI I3
cycle 4 I23 I22 I21 BI I5 UU UU BI
cycle 5 I24 I23 I22 I21 I6 I5 UU UU
選択されないパスでは、I21 と I22 は役に立ちません。それらは実際に実行されます (そして状態を更新します) が、この状態は、選択されていないパス (またはパスの結合後) では使用されません。実行されなかったパスの場合、遅延スロットがノーオペレーションで埋められたかのようになります。
3.4 の場合、コンパイラは、使用されなかったパスから安全な命令を 1 つしか見つけることができず、他の遅延スロットをノーオペレーションで埋める必要があります。
Taken Not taken
IF DE BR S1 ... IF DE BR S1 ...
cycle 1 BI I3 I2 I1 BI I3 I2 I1
cycle 2 I5 BI I3 I2 I5 BI I3 I2
cycle 3 NO I5 BI I3 NO I5 BI I3
cycle 4 I21 NO UU BI I6 NO I5 BI
cycle 5 I22 I21 NO UU I7 I6 NO I5
選択されたパスでは、1 つの無駄な命令と 1 つのノーオペレーションが実行され、2 サイクルが無駄になります。選択されなかったパスについては、1 回の no-op が実行され、1 サイクルが無駄になります。
CPIの計算
この場合の CPI の計算式は次のとおりです。
%non_branch * CPI_non_branch + %branch * CPI_branch
CPI_branch は、分岐自体 (baseCPI_branch) にかかった時間と、分岐が行われたときに無駄なサイクルが発生した回数の割合と、分岐が行われたときに無駄なサイクルが発生した回数の割合を考慮して計算されます。取られません。したがって、CPI_branch は次のとおりです。
baseCPI_branch + (%taken * wasted_cycles_taken) +
(%not_taken * wasted_cycles_not_taken)
理想的なスカラー パイプラインでは、各命令は 1 サイクルかかります。つまり、Cycles Per Instruction は 1 です。この例では、非分岐命令はパイプラインが理想的であるかのように動作します (「プロセッサ内のすべてのストールは分岐関連」)。したがって、各非分岐命令の CPI は 1 です。同様に、baseCPI_branch (ストール、ノーオペレーションなどによる無駄なサイクルを除く) は 1 です。
上記のパイプライン ダイアグラムに基づいて、選択されたパスと選択されなかったパスで無駄になったサイクル数を判断できます。この例では、分岐のパーセンテージと、取得された分岐と取得されていない分岐のパーセンテージが示されています。
デザイン 1 の場合、選択されたパスと選択されなかったパスの両方で 2 サイクルが無駄になるため、CPI_branch は次のようになります。
1 + (0.3 * 2) + (0.7 *2) = 3
したがって、CPI の合計は次のようになります。
(0.85 * 1) + (0.15 * 3) = 1.3