竹下世界塔の計算機よもやま話

アクセスカウンタ

zoom RSS 分岐命令のペナルティ

<<   作成日時 : 2012/04/20 03:03   >>

なるほど(納得、参考になった、ヘー) ブログ気持玉 1 / トラックバック 3 / コメント 4

 パイプライン実行が前提のRISCアーキでは、分岐命令が成立して別の番地にジャンプすると後続の命令は破棄され、新しい番地から新たに命令が投入される。これはパイプラインの段数が深いほど何もできないサイクル(ペナルティ)が大きくなる。

例:4段のパイプライン(Fetch、Decode、Execute、Writeback)の実行例
縦軸は命令、命令03は分岐命令で命令10にジャンプする。横軸はサイクル。
実行される命令列はお互いに依存関係がなく、途切れなく供給されるものとする。

01■■■■
02□■■■■
03□□■■■■→10
04□□□■■■×
05□□□□■■■
06□□□□□■■
07□□□□□□■
08□□□□□□□
09□□□□□□□
10□□□□□□□■■■■
11□□□□□□□□■■■■
12□□□□□□□□□■■■■
13□□□□□□□□□□■■■■

命令03は6サイクル目のWritebackでプログラムカウンタを書き換える。次の7サイクル目から命令10のフェッチを開始する。
命令04は7サイクル目でWritebackされるとCPUの状態を変えてしまうので破棄しなければならない。命令05,06,07はWriteback以前なのでそのまま流しても問題はない。
命令01,02,03,10,11,12,13の順に実行して完了するまで14サイクルかかる。

もし分岐がなく、連続して実行した場合と比較する。

01■■■■
02□■■■■
03□□■■■■
10□□□■■■■
11□□□□■■■■
12□□□□□■■■■
13□□□□□□■■■■

7命令を10サイクルで実行完了する。このモデルでは分岐で+4サイクルのペナルティがある。


 では、10段のパイプラインではどうか。

01■■■■■■■■■■
02□■■■■■■■■■■
03□□■■■■■■■■■■→16
04□□□■■■■■■■■■×
05□□□□■■■■■■■■■
06□□□□□■■■■■■■■
07□□□□□□■■■■■■■
08□□□□□□□■■■■■■
09□□□□□□□□■■■■■
10□□□□□□□□□■■■■
11□□□□□□□□□□■■■
12□□□□□□□□□□□■■
13□□□□□□□□□□□□■
14□□□□□□□□□□□□□
15□□□□□□□□□□□□□
16□□□□□□□□□□□□□■■■■■■■■■■
17□□□□□□□□□□□□□□■■■■■■■■■■
18□□□□□□□□□□□□□□□■■■■■■■■■■
19□□□□□□□□□□□□□□□□■■■■■■■■■■

7命令を26サイクルで実行完了。命令04〜13の10個が捨てられてしまった。

01■■■■■■■■■■
02□■■■■■■■■■■
03□□■■■■■■■■■■
16□□□■■■■■■■■■■
17□□□□■■■■■■■■■■
18□□□□□■■■■■■■■■■
19□□□□□□■■■■■■■■■■

もし分岐がなかったら16サイクルで実行完了。+10サイクルのペナルティ。

 このようにパイプラインの段数が深いほどペナルティは大きい。
初期のRISCは段数が少ないが、現在のプロセッサは動作周波数が高いため1サイクル当たりに収めることができる論理回路を複雑にすることが難しい。このため、パイプラインの段数を増やして対処する。その結果、分岐によるペナルティは大きくなる。


 さっきの4段パイプラインのモデルでは、分岐命令直後の命令のWritebackを破棄した。これをモッタイナイと分岐命令直後の命令を実行することにしたのがMIPS,SPARC,PA-RISCである。これは遅延分岐と呼び、分岐命令の直後はディレイドスロットと呼ぶ。

01■■■■
02□■■■■
03□□■■■■→11
10□□□■■■★
05□□□□■■■
06□□□□□■■
07□□□□□□■
08□□□□□□□
09□□□□□□□
11□□□□□□□■■■■
12□□□□□□□□■■■■
13□□□□□□□□□■■■■

命令は01,02,03,10,11,12,13の順に実行される。命令10をディレイドスロットに移動した。これにより14サイクルから13サイクルへと改善された。

 MIPSの別の実装であるMIPS-Xではディレイドスロットは分岐命令の直後に2個ある。ただしこれをやり過ぎるとパイプラインの実装により命令コードが変わってしまうことになる。また、複数命令を同時実行するスーパースカラやアウトオブオーダ実行では取り扱いが難しくなる。このためMIPS、SPARC、PA-RISCより後の世代のRISCでは遅延分岐は採用されていない。


 ということで、ちょっとおさらいをしてみました。

テーマ

注目テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ
気持玉数 : 1
なるほど(納得、参考になった、ヘー)

トラックバック(3件)

タイトル (本文) ブログ名/日時
分岐予測
 分岐命令では後続の命令が破棄されてしまうが、分岐先の番地が確定すれば、分岐先の命令列をあらかじめ投入することができる。 ...続きを見る
竹下世界塔の計算機よもやま話
2012/04/20 13:00
ハードウェアに対する分岐ヒント
 SPARC V9には条件分岐命令が分岐しそうかそうでないか、ハードウエアにヒントを与えるbitがある。調べたら他にもあった。 ...続きを見る
竹下世界塔の計算機よもやま話
2012/04/20 17:28
遅延分岐命令の分類
 パイプライン実行が前提のRISCアーキには遅延分岐命令を持つものがある。分岐命令の直後の命令を実行してから分岐先へと制御を移す。遅延分岐命令の後にある実行される命令の場所を遅延スロットと呼ぶ。 ...続きを見る
竹下世界塔の計算機よもやま話
2014/10/07 00:45

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(4件)

内 容 ニックネーム/日時
一番上の例、文章だと命令10のフェッチが7サイクル目から始まるって書いてありますけど、図では7サイクル目にフェッチしてるのは命令07で、命令10は8サイクル目からですね。
nnn
2014/10/11 00:33
ご指摘ありがとうございます。
分岐後の命令開始サイクルがすべてズレてしまっています。
houmei
2014/10/11 02:08
すると、結局何が正しいんですか?
7サイクル目から命令10のフェッチが始まるなら命令07のフェッチはどうなるのか、とか
結局トータルサイクル数はどうなって最終的なペナルティは何サイクルなのか、とか
気になります
nnn
2014/10/11 19:29
分岐のあるサイクルが-1、分岐がなかった場合と比較した時のペナルティが1つ減ります。とりいそぎ。(おそらくお分かりになっていると思います)
houmei
2014/10/12 03:01

コメントする help

ニックネーム
本 文




分岐命令のペナルティ 竹下世界塔の計算機よもやま話/BIGLOBEウェブリブログ
文字サイズ:       閉じる