コンピュータアーキテクチャの話 (178) トレースキャッシュ(1)

　トレースキャッシュ

　分岐先予測を使うと、分岐命令の実行時ではなくデコード時に分岐先アドレスの予測値が得られ、この予測に基づいて分岐先の命令のフェッチを始められる。しかし、最近のプロセサでは、次の命令のフェッチを行い分岐先の命令のデコードが終わるまでには少なくとも4～5サイクル程度を必要とし、命令発行にストールが生じてしまう。ということで色々な改善方式が研究されてきた。中心的に活動してきたのは、当時ミシガン大学のYale Patt教授のグループとウイスコンシン大学のJim Smith教授のグループで、それが1997年にSmith教授の門下生のRotenberg氏らのTrace Cacheという形で1つの完成を見た。

　通常の命令キャッシュは、アドレス順に命令を格納するが、トレースキャッシュは命令のアドレスとは直接は関係なく、命令が実行された順にキャッシュに格納する。この連続して実行された命令列をトレースと呼び、格納されたトレースと同じ順に命令が実行される場合は、Takenの分岐命令があり命令アドレスが不連続になってもストールなしに命令をデコードして発行を続けられる。Rotenberg氏の論文では、通常のキャッシュだけを使用する場合と比べて、トレースキャッシュを用いると平均28%性能が向上したと書かれている。

　プログラムではその中へ分岐で飛び込んでくることが無く、また、途中から外に出て行ってしまうことが無く常に連続して実行される一連の命令をベーシックブロック(Basic Block)と呼ぶ。トレースキャッシュは、図8.6に示すように、分岐を挟んで連続して実行される複数のベーシックブロックをトレースキャッシュの1つのラインに格納する。命令アドレスは連続であるベーシックブロック内だけでなく、アドレスが連続でないベーシックブロック間でも、命令を実行順に1つのキャッシュラインに連続して詰め込む点が通常の命令キャッシュとは異なる。このように実行順に命令を格納することにより、分岐による命令発行のストール無く連続して命令を発行することを可能にし、それにより性能を改善しようという機構である。

　図8.6 トレースキャッシュの概念

　ベーシックブロックの大きさはマチマチであるが、整数プログラムでは平均的に5命令程度であるので、Rotenberg氏らの論文ではトレースキャッシュのラインのサイズは16命令とし、最大3つのベーシックブロックを含むと想定されている。

　しかし、このように3つのベーシックブロックを含むキャッシュラインのすべての命令が有効利用されるためには、最初のベーシックブロックの終わりにある条件分岐命令が次のベーシックブロックの先頭に分岐し、2番目のベーシックブロックの終わりの条件分岐命令が3番目のベーシックブロックの先頭に分岐し、最後のベーシックブロックの条件分岐の成立/不成立が正しく予測されて次のキャッシュラインのフェッチが始められなければならない。これを実現するメカニズムとしてRotenberg氏は図8.7の構造を提案した。

　図8.7 Rotenberg氏のトレースキャッシュの構造

　トレースはその先頭の命令のアドレスをインデックスとするキャッシュラインに書き込まれる。トレースキャッシュは、命令フェッチ機構の命令ラッチから命令を受け取り、順にラインフィルバッファに書き込んでいく。Takenの分岐命令が出てきても、そこで終わらずにフェッチされた分岐先の命令をラインフィルバッファに続けて書き込む。そして、命令数がキャッシュラインサイズに達するか、命令フェッチ機構の分岐予測機構が予測可能な数を超えるまでこれを続け、限界に達するとラインフィルバッファの内容をトレースキャッシュのラインに書き込む。なお、無条件の分岐命令やCall命令などもベーシックブロックの切れ目となるので、これらの命令は100%正しい予測が可能な条件分岐命令として取り扱っている。

　キャッシュラインのタグには、最初の命令の上位アドレス(Tag)とともにそのキャッシュラインに纏められらた条件分岐命令の個数(Bmask)とそれらの分岐方向(Bflag)が書き込まれる。そして、さらに、キャッシュラインには、その中の命令を実行し終わった後に実行するべき命令アドレス(Next Addr)と、キャッシュライン内の最後の命令が条件分岐命令である場合、その分岐先アドレス(BR Addr)を記憶しておく。

　トレースキャッシュのアクセスは、命令アドレスの下位ビットをインデックスとして用いるが、こちらは間違った命令を実行してしまうわけには行かないので、分岐予測のテーブルとは異なり、上位アドレスのタグマッチを行う。また、トレースキャッシュに格納されている命令列が続けて実行されるのは、実行しようとしているプログラムにおいて、キャッシュラインに格納されている命令列と同じ方向の分岐が発生する場合なので、格納されているトレースのTaken/Not Takenの列とこれらの分岐命令の予測値のマッチングを行い、すべてが一致した場合だけをヒットと判定する。

　しかし、ここが問題で、トレースキャッシュをアクセスするためには、この例では、3つ先までの条件分岐のTaken/Not Takenを予測しなければならない。