値予測

プロセサの性能向上のもう1つのネックが、ロード命令である。アウトオブオーダ実行とノンブロッキングキャッシュで、依存関係のない命令を先に実行することは可能になったが、ロード命令でメモリから読み込まれるデータに依存する後続の命令の実行は、メモリからデータが到着するまで待たなければならない。

この問題を軽減するために提案されているのが、値予測という手法である。分岐予測は、Taken、Not Takenの予測だけであり当たりやすいと言えるが、色々な値を取りうるデータの値の予測が出来るのかという声が聞こえそうであるが、それが、ある程度は可能なのである。

例えば、

Pai=3.141592
Do i=1、N
  S = S + Pai*A[i]*A[i]
Enddo

というようなプログラムにおいて、最初の文では3.141592という値をメモリから読んで、Paiという変数に格納する。その次のdoループの中で、メモリからPaiを読んで演算に使用する。

また、前回に計算してストアしたSを読み出して、次のPaiA[i]A[i]を加算して格納する。しかし、Paiは定数のロード、Sは前回に計算した値であり、簡単に予測できる。ただし、この例は簡単過ぎ、通常、コンパイラはSとPaiをレジスタに割り付けてしまい、ロード命令は必要が無くなってしまうので、このような単純な場合は値予測の効果は出ない。

しかし、一般的に、固定したアドレスからデータを読むロード命令の場合は、そのアドレスに格納されるデータは、限られた値だけを取る場合も多いので、このような場合は、値予測が有効に働く。

また、配列のアクセスを行う場合は、前記の例の配列A[i]のように、毎回、ロード命令のアドレスが異なり、一般には値は予測できないが、大部分の値は0.0で、非ゼロの値は僅かしか入っていないというような偏りのあるデータの場合は前回の値と同じという予測が可能である。

分岐予測と同様に、値予測の場合も予測の成功、失敗で+/-する飽和型のカウンタが用いられる。分岐予測の場合は、予測結果はTakenかNot Takenの2通りであるが、値予測の場合は、予測値を使って後続の命令の処理に進むか、自信が無いのでパスしてロード命令の完了まで待つかの2通りの予測を行うのが一般的である。そして、2ビットの分岐予測の場合はStrongly Not Takenの状態からでも2回予測成功が続けばWeakly Takenになるが、値予測の場合は、もっと慎重に4回~8回くらい成功が続くと自信をもって予測値を使用するモードに入るというのが一般的である。

自信なしとするケースをどの程度とするかの線引きにもよるが、自信ありとしたケースの値予測の成功率は80%程度に達することがある。しかし、このケースでも成功4回に対して失敗1回であり、成功のケースの1回あたりの高速化はレベル1データキャッシュの平均アクセスタイムと値予測機構のアクセスタイムの差であり、これを2サイクルとすると成功4回で計8サイクルの得であるが、1回の失敗で、予測を誤って実行してしまった後続命令を取り消し正しいロード命令の結果に基づく処理に戻るのに8サイクルのロスが出ると高速化の効果は差し引きゼロで、つぎ込んだハードウェアが無駄という感じになってしまう。ということで、筆者の知る限りでは、商用マイクロプロセサでの値予測の採用例は無い。