アウトオブオーダCPUにおいて、性能向上の生命線となるのが、分岐予測だ。現在自作CPUには、2種類の分岐予測命令を搭載させている。 * 命令分類による静的分岐予測 (beql / bnel 命令などのLikely命令による分岐) * 分岐結果に基く動的分岐予測 (beq / bne 命令などの一般的な分岐命令、そして無条件分岐命令)
動的分岐予測によるものはいくつか構成が考えられて、今回は3つの構成について考えてみた。
- 1段の動的分岐予測(分岐しない方向には学習しない)
- 1段の動的分岐予測(分岐しない方向にも学習する)
- 2段の動的分岐予測(4つのステートを持つ)
まずは分岐しない方向には学習しない分岐予測機構だが、これはハードウェアを絞るためにまずは作ってみたものだ。 分岐予測では、ループなどでは、基本的に分岐する方向がメインでヒットするが、ループの最後に一回だけ予測はヒットしない。 そして、次のループあるいは同じループを最初からもう一度やるときには、予測する前提で進める。 つまり、一度分岐したら、その学習結果は別の分岐命令により上書きされない限りは消えない方式である。
この方式を最初に作った理由は、分岐予測テーブルの中身を無効化する必要が無かったからだ。 つまり、分岐予測テーブルは書きっぱなしで良い。不成立時に分岐予測テーブルのエントリを削除するのが面倒だったため、その信号を省略していた(というか、初期の実装時にその目的に使える信号を出していなかった)
次に分岐しない方向に学習する分岐予測機構。これはハードウェア的には、一度分岐予測が不成立になると、すぐに分岐予測テーブルを更新し次回は分岐予測が成立しないようにする。連続的に分岐が成立しなくなったとしてもヒットさせることができる。
さて、それぞれでCMK値を測ってみると、以外なことに、分岐しない方向に学習しないパタンの方が成績が良かった。
- 分岐しない方向に学習しない版: 736426サイクル (CMK値: 1.36)
- 分岐しない方向に学習する版 : 760722サイクル (CMK値: 1.31)
冷静に考えてみると、この結果は別に驚くにあたらない。例えば二重ループの構造を考えると、
for (j = 0; j < 3; j++) {
for (i = 0; i < 3; i++) {
operation (j, i);
}
}
実行時の動きとしては、こうだ。
operation(0, 0) 分岐する operation(0, 1) 分岐する operation(0, 2) 分岐しない --> 最内ループ脱出 operation(1, 0) 分岐する operation(1, 1) 分岐する operation(1, 2) 分岐しない --> 最内ループ脱出 operation(2, 0) 分岐する operation(2, 1) 分岐する operation(2, 2) 分岐しない --> 最内ループ脱出
分岐しない結果が入っても、その次のループは分岐成立する。一度ループが成立したところで安易に分岐予測を変更してはいけない訳だ。この仕組みは、分岐しない方向を学習しない版だとうまく当てはまっている。
まあ、この考え方自体は分岐予測の基礎の基礎で、まあ普通の結論が出た訳だが、実際のRTLを動かしてサイクル数を測定してこの結果が出たのは面白い。やっぱりRTLを書いて確かめるのは楽しい！(めっちゃ時間かかるけど)
