[パタヘネ:読書メモ]第4章　プロセッサ その4

4.8　制御ハザード

制御ハザードというのは、分岐命令に起因するハザードの事を意味する。

これがなぜ発生するかというと、分岐条件が成立するかの判定はEXステージで比較演算を行い、その後のMEMステージまで決まらないから。一方で、分岐命令がMEMステージに来るころには、直後3命令分に対してそれぞれIM,ID,EX処理が行われている必要があるので、その分のクロックサイクルが無駄になるリスクがある。

これに関しては、その性質上完全に防ぐ事は出来ないので、どうすれば”よりましか”という考え方になる。

単純な分岐の予測

分岐結果が決まるまで後続の命令実行を止めるというのは、その待ち時間が完全に無駄になる。

なので、結果を捨てるのを承知で、分岐成立/不成立のどちらかを実行してしまった方がまだ”まし”になる。

そうすると、分岐が成立するかどうかを見込みで決める必要があるけど、不成立と予想しておくのが簡単(普通にPCをインクリメントしていくだけでよいので)。

この戦略をとった場合、見込みが外れたときの処理回路が追加で必要になる。
この回路は簡単で、IM,ID,EXステージのパイプラインレジスタを全クリアしてnop命令に上書きしてしまえばよい。nop命令に上書きは、前節でパイプラインがストールしたときにバブルとしてnopを入れる方法を既に考えているので、これと同じ事になる

※見込みの決め方は、以前確認したように、若いアドレスにジャンプする場合に限り、分岐成立とみなすという考え方もある。この戦略は、ループ処理で若いアドレスに分岐する事が多くなる事に起因する。

分岐予測ミス発生時のリカバリを早める

2つめの戦略は、仮に分岐予測が外れた場合でも、リカバリを早くすることを考える。

今までの話だと、IM,ID,EXステージのパイプラインレジスタのクリアが必要だったので、3クロックサイクル分の無駄が発生していた。これは、分岐が成立するかがMEMステージまで分からなかった事に起因している。

分岐の条件判定自体は、2つのレジスタ値が同じか等の簡単な比較演算なので、この演算処理だけを考慮するのなら高機能なALUを使うまでも無く、もっとシンプルな論理回路で対応する事も可能となる(比較がしたいだけなら、レジスタ値の各ビットのxorをとった結果に対してandを取って、0だったら同じ(分岐成立)、1だったら異なることが分かる)。
また、比較に使用する情報はIDステージでレジスタから取得できている。

というわけで、IDステージに分岐条件チェック用のスペシャル回路を追加してあげれば、仮に分岐予測が外れてもIFステージの破棄だけで住むようになるので、無駄となるのが3サイクル->1サイクルに減らす事が出来る。


ただ、この設計方針の転換は結構でかいので、以下のような配慮が必要となってくる。




というわけで、回路設計的には結構面倒になるけど、条件付分岐は頻発するし、この改善によって2クロックサイクルも無駄が省けるので、手間を掛けてまで対応する価値はある。

複雑な分岐の予測

今検討しているCPUはパイプラインが5段しかないので,前述の改善で1クロックサイクルの無駄だけで済んだけど、さらにチューニングしてパイプライン段数を増やす事になった場合は、分岐ミスのダメージが増えるリスクがある。
なので、分岐予測はもう少し考え直すだけの余地がある。

最初に単純な分岐予測として、”常に分岐が成立しないと予測する”という事を行ったけど、ここでは、もう少しがんばって分岐予測の精度を高めてみる。

ここで、C言語などのプログラムを考えてみると、分岐命令が入るのはforやwhileなどの繰り返し文に起因するものが多い。繰り返し文は、たいていの場合では複数回ループが実行されるので、各分岐命令に対して前回分岐命令の成立/非成立かを覚えておいて、次も同じ側が来ると予測できればかなり精度は高まる。


上記の手法をを、動的分岐予測(dynamic branch prediction)と呼ぶ。

動的分岐予測を実装するためには、最近実行された分岐命令に対して、以前の分岐結果を覚えておけばよい。これをもしC言語で実装するなら、ハッシュなどを使えば簡単だけど、今回は電子回路として実装しなければならないので、”シンプル、かつ、そこそこ妥当なもの”で妥協する必要がある。


というわけで考えられたのが,分岐予測バッファ(branch prediction buffer)になる。これは、分岐履歴テーブル(branch history table)とも呼ばれる。

これは、分岐命令の場所(アドレス)の下位nビットをキー(index)にして、前回の分岐結果を1bitを保存しておけるメモリで、大きさはn^2(bit)分必要となるする。
(例:下位3bitをキーにするなら、テーブルの領域はは8bit分必要となる)

これは、アドレスの下位nビットをキーとするハッシュテーブルという扱いになっている。
ハッシュだと、普通はキーのコリジョン対策が必要となるけど、今回はそこまで対応しない。

なぜかというと、利用目的がしょせん分岐予測なので、キー衝突時に本来とは異なる情報を引っ張ってきたせいで分岐予測がミスっても、そのデメリットはCPUサイクルを無駄遣いするだけ。それに対して、コリジョン対策まで論理回路で実装するとH/W設計ががとても複雑になってしまうことが理由となっている。


これで、かなり精度が上がるけど、以下のような良くある多重ループの場合、内側のループでの予測ミスが、最初と最後の2回発生してしまう。




これは、1回目のループの最後に分岐履歴テーブルへ分岐不成立と覚えさせたものをベースに、2回目の内側ループの初回分岐予測を行ってしまう事に起因する。
この手の処理は非常にありがちなので、対策すべきものになる。対処法としては、分岐履歴テーブルに直近1回分ではなく2回分を覚えさせておき、2回連続はずした時だけ分岐の予測を変えるように変更する。



さらに、前回分岐先のプログラムカウンタ値までキャッシュし分岐先アドレスの予測まですると、さらに高速化できる可能性がある(EXステージでの演算サイクルを省略できる可能性がある)。

その他にも応用編として、相関予測方式(局所分岐予測)や、トーナメント分岐予測方式(結合分岐予測)などもあるけど、そのあたりの詳細はWikipediaで確認してください。
分岐予測 – Wikipedia



また、条件分岐命令自体を減らす方法として、CPUの命令セットに条件付move命令を追加するという方法もある。これは、条件式が成立するときのみレジスタのコピーを行うという、良くある処理を1命令で行うもので、命令自体に分岐処理的要素を含んでいるので分岐予測自体を行う必要が無い。

これについては、MIPSでは以下の命令が用意されている。

4.9　例外

次は、イレギュラー処理を考える。
CPUからすると、イレギュラーには以下の2つが存在する。




例外と割込の呼び分けは、CPUのアーキテクチャによって異なる場合があるので、注意が必要(上記の分類はMIPSの場合)


例外の対処法は状況によって異なるので、回路設計上も複雑になりがちだし、設計方法を誤るとここが原因で性能が出なくなる危険もある。

例外がおきると、CPUは以下の処理を行う



この辺はVB6のON ERROR GOTO文に仕組みがちょっと似ている。


パイプライン化されているCPUにおいて、例外処理は制御ハザード＋分岐命令と同様の処理を行う。
なので、IF,ID用のパイプラインレジスタをクリアしnop命令に差し替えた上で、PCを適切な値に変更する。

また、例外発生時は、例外処理を行った上で対象の処理を正常に行う必要がある場合が多い。これは、該当命令を再度IFステージから実行しなおせばよい(退避されたEPCの値を,PCに戻せば実装できる)

例外の発生は、5つあるステージのどこでも発生する可能性があるし、同時に複数の例外が起きる場合がある。1クロックサイクル内で複数の例外が発生する場合、MIPSでは例外の優先順にしたがって処理が行われる。

昔のCPUでは、HWのしくみにより、例外の発生元命令(PCの値)が正確にわからないものもあった。これを不正確な割り込み(imprecise interrupt)と呼び、このようなアーキテクチャの場合は、ソフトウェア側での配慮が必要になる。

また、I/O割り込みに関しては、特定命令には紐付かないので別種の考慮が必要になるが、これは別の章(下巻)で検討する。

4.10　並列処理と高度な命令レベル並列性

並列処理について、さらに深く学びたい場合は、コンピュータ・アーキテクチャが詳しい。

並列化を増やすには、2つの方法がある。



後者の場合は、どの命令が同時に実行できるかのコントロールやハザード処理などが難しくなる。

命令の投機実行

CPUやコンパイラの機能として、後続の命令が、現在の命令に依存しない事を見込んで、先に後続の命令を実行してしまう機能のこと。

見込みが外れたときのリカバリや、見込み実行した命令で例外が発生したときなど、考慮すべき点は多い…

静的な複数命令の同時実行

CPU的に同時実行可能な命令郡を用意し(H/W回路として同時実行可能な組み合わせを作る)、コンパイラの配慮でが該当する組み合わせを作るよう努力する事で、１クロックサイクルで複数の命令を同時実行させる。

一部のMIPSの実装では、２命令単位で同時に実行を行う事を試みる。
命令のフェッチは64bit単位で行われ、同時実行できない組み合わせの場合は、一方をnopにさせる事で対応する。

動的な複数命令の同時実行

複数命令を動的に発行させる事が出来るCPUのことを、スーパースカラプロセッサと呼ぶ。

仕組みとしては、動的パイプラインスケジューリング(dynamic pipeline scheduling)を用いる事が多く、これは命令の実行順序をCPU側で自動で組み替えてしまう。組み換えはもちろん実行結果が変わらない範囲において行われる。
例えば、”メモリ操作系の命令実行は遅いので、それを待っている間に次の命令を処理していってしまう”などがある。


…
ここから先の話題は、ちょっと難しいので斜め読みで終わらしておく…(なのでメモは省略)
キーワードだけメモしときますので、興味がある方は本書を確認してください。

電源効率とパイプライン処理

投機実行等によって複数の命令を１クロックで同時実行させる事はある程度可能になるけど、一方で回路が非常に複雑になってしまうというデメリットがある。
そうすると、クロックあたりの性能を向上させる事ができても、能力あたりの消費電力が増えてしまう。(消費電力は駆動するトランジスタ数に依存するので)

電力が増えると熱の発生が増え、熱の発生は半導体の寿命に影響するため、回路の複雑化による性能向上には限界がある。


なので、最近はパイプライン処理を複雑化させるのではなく、シンプルなCPUを複数用意(マルチコア化)させることで性能を上げ、消費電力と性能のバランスを取っている。

例えばPendtium4ではパイプライン段数は31もあったけど、その後のIntel Coreでは14段に減っており、消費電力(TDP)も2割以上削減できている。

4.11　実例：AMD Opteron X4 (Barcelona)のパイプライン

AMDではx86の命令セットを内部的にRISC風の命令セットに置き換えて、CPUで実行しており、これをRISCオペレーションと呼んでいる(IntelのCPUも同様の仕組みがあって、マイクロオペレーションと呼んでいる)。

また、x86のアーキテクチャ上は16個のレジスタを持っているが、これを内部的には72個の物理レジスタに割り振りなおしている。

これはJavaで行われている、”VM上の定義された命令セットでバイナリを作成し、実行時は実CPU上の命令セットに翻訳している”機能をハードウェア的に行っているようなものっぽい。

4.12　高度な話題：パイプラインの記述およびモデリング用のハードウエア設計言語を使用したディジタル設計の概要とパイプライン処理の追加図解

省略

4.13　誤信と落とし穴

誤信:パイプライン処理は容易である。

本書をここまで読んできた時点で、その誤解は既に無いです…

パイプラインの設計思想は、設計テクノロジに関係なく実現できる

設計テクノロジによって、CPUに搭載可能なトランジスタの数(大きさに依存)や、回路駆動の遅延が変わってくる。トランジスタの性能が変わるとメモリアクセスとの速度差が顕著になってくる。

その結果、回路的に複雑な事(投機実行やスーパースカラなど)を行っても、パフォーマンス的に割が合う様になってくるので、パイプラインの設計思想は設計テクノロジに依存する。

落とし穴:命令セットの設計がパイプラインに負の効果を与える事を検討し忘れる

同じレベルのテクノロジで作成されたCPUであっても、命令セットによって性能比が倍以上変わる事例もあるらしい。

4.14　おわりに

パイプライン化を行っても、1命令あたりの実行時間(レイテンシ)は速くならない(スループットは向上する)。

パイプラインは、CPIを小さくする事を目的にしている。

暫くの間パイプライン化による性能向上を目指していたが、最近では電力･発熱がボトルネックになっている。なので、複雑なCPUを1つ作るのではなく、シンプルなCPUを複数祖結合する事で性能向上を目指している。

CPUの性能向上だけを目指しても、主記憶がボトルネックになってくるのでコンピュータ全体の性能向上には限界がある。(Amdahlの法則)

4.15　歴史展望と参考文献（◎CDコンテンツ）

省略

4.16　演習問題

省略


コンピュータの構成と設計（上）