分岐予測

 分岐命令では後続の命令が破棄されてしまうが、分岐先の番地が確定すれば、分岐先の命令列をあらかじめ投入することができる。

前回の続き。

縦軸に命令列、横軸にサイクル数をおいたパイプラインの図。パイプラインは8段とする。

01■■■■■■■■
02□■■■■■■■■
03□□■■■■■☆■■→19
04□□□■■■■■■■×
05□□□□■■■■■■■
06□□□□□■■■■■■
07□□□□□□■■■■■
08□□□□□□□■■■■
09□□□□□□□□■■■
10□□□□□□□□□■■
11□□□□□□□□□□■
12□□□□□□□□□□□
13□□□□□□□□□□□
14□□□□□□□□□□□
15□□□□□□□□□□□
16□□□□□□□□□□□
17□□□□□□□□□□□
18□□□□□□□□□□□
19□□□□□□□□□□□■■■■■■■■■■
20□□□□□□□□□□□□■■■■■■■■■■
21□□□□□□□□□□□□□■■■■■■■■■■
22□□□□□□□□□□□□□□■■■■■■■■■■
23□□□□□□□□□□□□□□□■■■■■■■■■■
24□□□□□□□□□□□□□□□□■■■■■■■■■■

 命令01~03,19~24と9命令の実行に26サイクルかかった。命令03の飛び先が予測できるのは、命令をフェッチしてデコードし、飛び先のアドレスを計算した後になる。ここでは、☆印のある8サイクル目でアドレス計算が完了したものとする。

01■■■■■■■■
02□■■■■■■■■
03□□■■■■■☆■■→19
04□□□■■■■■■■×
05□□□□■■■■■■■
06□□□□□■■■■■■
07□□□□□□■■■■■
08□□□□□□□■■■■
09□□□□□□□□□□□
10□□□□□□□□□□□
11□□□□□□□□□□□
12□□□□□□□□□□□
13□□□□□□□□□□□
14□□□□□□□□□□□
15□□□□□□□□□□□
16□□□□□□□□□□□
17□□□□□□□□□□□
18□□□□□□□□□□□
19□□□□□□□□■■■■■■■■
20□□□□□□□□□■■■■■■■■
21□□□□□□□□□□■■■■■■■■
22□□□□□□□□□□□■■■■■■■■
23□□□□□□□□□□□□■■■■■■■■
24□□□□□□□□□□□□□■■■■■■■■

9サイクル目から飛び先である命令19のフェッチを開始する。命令03で分岐を実行した後はすでにパイプラインに投入済みの命令19を継続して流すだけ。26サイクルかかっていたのが21サイクルで実行完了した。

 分岐命令の飛び先が確定するまでに投入された命令は捨てられるのはしょうがないが、深いパイプラインであるほど効果は大きい。

 ただしこれは無条件で分岐する場合。条件分岐命令は飛ぶかどうかが実行するまでわからない。

分岐すると予測したのに非分岐だった場合は:

01■■■■■■■■
02□■■■■■■■■
03□□■■■■☆■■■→非分岐
04□□□■■■■■■■■
05□□□□■■■■■■■■
06□□□□□■■■■■■■■
07□□□□□□■■■■■■■■
08□□□□□□□■■■■■■■■
09□□□□□□□□□□□■■■■■■■■
10□□□□□□□□□□□□
11□□□□□□□□□□□□
12□□□□□□□□□□□□
13□□□□□□□□□□□□
14□□□□□□□□□□□□
15□□□□□□□□□□□□
16□□□□□□□□□□□□
17□□□□□□□□□□□□
18□□□□□□□□□□□□
19□□□□□□□□■■■× 捨てられた!
20□□□□□□□□□■■×
21□□□□□□□□□□■×
22□□□□□□□□□□□×
23□□□□□□□□□□□□
24□□□□□□□□□□□□

分岐した時と同じ9命令分を実行完了するのに19サイクルかかった。本来なら16サイクルで終わるはずなのに3サイクルのペナルティが発生した。

このモデルの場合、分岐と予測して外れた時は+3サイクル。非分岐と予測して外れた場合は+8サイクルのペナルティとなる。

 外れた時のペナルティが発生するので、できれば毎回正しい方向を読み込みたいのだが、これは分岐が成立するまではわからない。そこで分岐予測というメカニズムが実装された。これはソフトウェアからは見えない。

 最初の頃の分岐予測は、分岐先が戻り方向だとループ実行の終端であり、ほとんどの場合は分岐成立、分岐先が進む方向だとループからの脱出でほとんどの場合は分岐不成立とした。ただしこれは先の番地に存在するサブルーチンを頻繁に呼び出す場合は毎回ペナルティが発生することになる。

 マイクロプロセッサの内部で命令列の文脈を見ることは困難なので、単独の分岐命令について過去分岐したかどうかの履歴を保存し、それを参照して予測を立てる。予測の方式は色々あるが、履歴を取って参照する所は同じ。

 で、思い出話:分岐予測機構のデバッグは後回しだったような。というのも分岐予測が動かなくてもプロセッサは動くし、本当に分岐予測が有効に効いているかどうかは実行時間の問題で大量のコードが流せない論理シミュレーションで確認するのが難しい。メカニズム自体のデバッグは単体でやっていても、効果を確認できるのは完成後の性能評価になる。ということで分岐予測機構も完成するまでははっきりしないのでした。


 分岐予測のメカニズムについては「プロセッサを支える技術」p149~にあります。OutOfOrder実行を前提にしていますが普通のパイプラインでも分岐予測は有効。

プロセッサを支える技術  --果てしなくスピードを追求する世界 (WEB+DB PRESS plus)プロセッサを支える技術  --果てしなくスピードを追求する世界 (WEB+DB PRESS plus)
Hisa Ando

技術評論社 2011-01-06
売り上げランキング : 45250

Amazonで詳しく見る
by G-Tools



 「高性能コンピュータ技術の基礎」こちらはもっと詳しい。第三章 予測に基づく投機実行

高性能コンピュータ技術の基礎高性能コンピュータ技術の基礎
Hisa Ando

毎日コミュニケーションズ 2011-06-24
売り上げランキング : 355698

Amazonで詳しく見る
by G-Tools


ブログ気持玉

クリックして気持ちを伝えよう!

ログインしてクリックすれば、自分のブログへのリンクが付きます。

→ログインへ

なるほど(納得、参考になった、ヘー)
驚いた
面白い
ナイス
ガッツ(がんばれ!)
かわいい

気持玉数 : 0

この記事へのコメント

この記事へのトラックバック

  • ハードウェアに対する分岐ヒント

    Excerpt:  SPARC V9には条件分岐命令が分岐しそうかそうでないか、ハードウエアにヒントを与えるbitがある。調べたら他にもあった。 Weblog: 竹下世界塔の計算機よもやま話 racked: 2012-04-20 17:28