アウトオブオーダーと分岐予測

はじめに

笠原一輝さんがPC Watchに連載している「笠原一輝のユビキタス情報局」ですが、この中でアウトオブオーダーについて説明する「Intel、22nm世代のAtom CPUコア「Silvermont」の詳細を公表 ~最大8コア構成で前世代から性能は3倍、電力は1-5に」におけるアウトオブオーダーの説明が根本的に間違っているのです。

掲載当時にも「うーん…」と思っていたのですが、さすがにそのうち撤回されて修正記事に変わるだろうと思っていたのですが、現在でもそのままで、さらに最近の記事「CPU、GPU性能が桁違いに向上したBay Trail ~ベンチマークでAtom Z3000の性能をチェック」においても、該当記事を参照するように書いており、誤った知識の拡散が懸念されるため、誤っている点について指摘をしたいと思います。

分岐予測

「分岐予測(Branch Prediction)」は、インオーダーかアウトオブオーダーかに関係なく、命令をパイプラインで処理するタイプのCPUにおいて、分岐に伴うペナルティを軽減する目的で搭載するものです。

パイプラインを搭載したCPUでは、取り込んだ命令を順次処理しながら、命令取り込みを行うユニットは次のサイクルでも命令取り込みを行います。仮にパイプラインが3ステージだったとすると、以下のようになります(※模式図です):

フェッチ デコード 実行

命令1    
命令2 命令1  
命令3 命令2 命令1

このように命令自体の実行は3クロック必要ですが、命令そのものは1クロックごとに処理が完了します。

この命令を取り込む「フェッチ」処理は、次の命令を次のクロックで取り込むために次の命令の位置を確定させる必要があります。これを確定しないと次の命令を取り込むことができません。分岐がない場合には次の命令はフェッチした命令の次のアドレスから始まるので自明であり問題はないのですが、ここに分岐が入ると事情は異なります。

1つ目の方法は分岐先を気にせずに次の命令をフェッチしていくという方法です。実際に分岐して取り込んだ命令の処理が不要になった場合には、取り込んだ命令をクリアして、新しい分岐先アドレスから取り込みを再開します。この方法は分岐の際に無駄になる処理が発生するという性能上の問題があります。そこで、これを改良するための技術として考案されたのが「分岐予測」です。

分岐予測では分岐命令を実際に実行する前に、分岐が実施されるかどうかを予測します。一般に予測は過去に該当する命令がどのように処理されたかを元に行います。分岐すると予測される場合には分岐したものとして取り込む命令のアドレスを分岐先のアドレスに変更します。分岐しないと予測した場合には後続の命令のアドレスをそのままとします。

これにより、必要十分に予測精度が高ければフェッチなどしたが実行しない(できない)という無駄を省き、性能を上げることができます。ここでの説明は順番に命令を実行するインオーダーで説明していますが、アウトオブオーダーであろうと同じことです。

アウトオブオーダー

「アウトオブオーダー(Out of Order / OoO)」は取り込んだ命令のうち、実行可能なものから順次実行し、結果は取り込んだ順と同じように並べなおして出力(リタイア)するタイプのCPUを指します。

実行可能な命令は、取り込んだ命令の依存関係を元に決定します。例えば、

1 : A = 0
2 : B = 200
3 : C = A + B
4 : D = 50

という計算をするとします(単純化するためにとんでもなく単純なことを書いています)。これを順番にフェッチして命令キューに入れた状態とし、これから実行すると仮定すると、1と2は並行して実行できますが、3は1と2の命令の実行が終わっていなくては実行できません。なぜならば、3でCを計算するためにはABの値が確定していなければならないからです。しかし、その次の4のDへの値代入はそれより前の命令の実行完了を待つ必要がないため、先行して実行することができます。

(実際に並行して実行できる命令は処理ユニットの構造によりますが)このように「アウトオブオーダー」は依存関係を元に、結果に矛盾が発生しない順番で命令を実行し、その結果を順番通りに出力する設計を指します(例外や割り込みなどにおいて、結果を正しく反映/取り消しを行えるようにするため、結果は順番通りに組み立てる必要があります)。

この例では、アウトオブオーダーでは1と2と4が同時に実行できますが、インオーダーの場合には1と2のあと結果が確定するまで3およびその後の4が実行できません。

笠原さんの記事による説明

前述を踏まえて、笠原さんの解説記事の以下の記述を読んでみてください:

一般的なCPUで採用されているOut-Of-Order型(分岐予測に基づき順番を入れ替えて効率よく実行していく方式)へと変更

明らかに理解に誤りがあるとわかります。アウトオブオーダーで実行することができる命令の割り出しは分岐予測に基づいて行うことではありません。何等か別のものと理解が混じっている(=つまり間違っている)のではないかと思われます。

実際に該当する記事を読み進めていくと、誤解に基づいた説明がなされています。

ただし、実際のプログラムの命令には、今実行している命令の結果を、次の命令実行に利用することがある。だが、Out of Orderで準備を入れ替えると、結果を待たなければ実行できない命令が先に実行される可能性がある。

「準備を入れ替える」というのが、よくわかりません。何を指しているのでしょうか…?

そこで、CPUには分岐予測器と呼ばれる、命令の分岐を予測するエンジンが備えられており、その予測に基づいて命令を入れ替えて効率よく実行していく。

分岐予測で「命令を入れ替えて」実行することはありません。前述のようにアウトオブオーダーでは依存関係(と待ち期間)に基づいて実行できる命令を決定します。

まとめ

以上のように、非常に残念なことではありますが笠原さんは間違った理解を元に記事を書いてしまっているように、私には思えます。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です