最優秀学生発表論文

最優秀学生発表論文賞を受賞したのは、ジョージア工科大学のLoh助教授のグループのドクターコース1年のSamantika Subramaniam嬢の論文である。彼女は、美人で、かつ、マスターコースを全優(GPA4.0)で卒業した才色兼備の女性である。それはともかく、"Fire-and-Forget: Load/Store Scheduling with No Store Queue at All"と題するこの受賞論文はプロセサのロードストアユニットに関するものであるが、バックグラウンドの説明を要する。また、内容の説明もかなり端折らざるを得ないので、興味のある読者は原論文を見て戴きたい。

プロセサコアから見ると、ストアはこのデータをこれこれのアドレスに格納してくれという依頼をストアユニットに出せば終わりであるが、ロードの方はアドレスをロードユニットに渡しても、メモリからデータが到着するまでそのデータを使用する演算は実行出来ないので待ち時間が生じる。この待ち時間を短縮するため、ロードは出来るだけ早く実行を開始したいのであるが、早とちりしてキャッシュを読んでしまうと、ロードと同じ番地に書き込む先行するストア命令があるケースでは、書き込み前の値を読んでしまう恐れがある。

このため、ロード命令のアウトオブオーダ実行を行うプロセサでは、ロード命令はロードキュー(LQ)、ストア命令はストアキュー(SQ)に命令順に格納し、LQから命令を取り出して実行する時にSQをチェックして、先行するストアが同じ番地に書き込むケースがあれば、SQに格納されたストアデータをロード命令に渡すバイパス処理を行う。また、先行するストア命令の中に、アドレス計算が終わっておらず書き込み番地が未定のものがある場合は、ロード命令と同じアドレスになる可能性があるので、ロードの実行を待たせるというような処理を行う。

現在のマイクロプロセサでは、このようなLQ、SQアーキテクチャを用いるものが多いが、LQをサーチするCAM(連想メモリ)は電力を喰う、また、性能を維持して大規模化するのが難しいといった問題がある。

別のやり方としては、ロード命令はSQをチェックせずに出来るだけ早く実行を開始してキャッシュを読むが、そのロード命令をコミットする時点でその番地のメモリの内容が書き換えられていないかどうかを確認する方法がある。もし、書き換わっていると、ロード命令以降の命令をキャンセルして実行をやり直す必要があるが、この方法は、ロードの実行が早く開始でき、待ち時間が減るという利点がある。しかし、コミット時点でキャッシュを(再度)読んで、書き換えが起こっていないかどうかを確認するオーバヘッドが大きく、この2度目の読み込みの回数をどう減らすかがポイントとなる。

この論文で提案するFire and Forgetという手法は、各ストア命令のストアデータをどのロード命令が読み込むかを予測するテーブルを持ち、ストア命令を実行する時に、このテーブルを見て、LQに格納されたそのロード命令のエントリにストアデータを書き込むという動作を行う。一方、ロード命令をLQから取り出して実行する場合は、ストア命令によって書き込まれたデータがある場合には、キャッシュをアクセスせずその値を使う。そして、ロード命令をコミットする時点で、影響する可能性があるストアがロード命令によるキャッシュの読み込み時点からコミット時点までに実行されたかどうかをチェックし、書き換えられている恐れがある場合には再度キャッシュから読み込んでチェックする。影響するかどうかをチェックするのに、SSBF(Store Sequence Broom Filter)とSPCT(Store PC Table)という機構を使っているが、詳細は省略する。

このように、ストア命令は、メモリに書くという本来の動作と、その格納番地のデータを使うと予測されるLQのエントリにデータを渡してやる必要があるが、それ以降は何もする必要がない。これがFire and Forgetという名前の由来である。

この手法の効果であるが、CAMを使うLQ、SQの一般的な方式と比べて、性能はほぼ同程度であるが、構造が簡単で、CAMが不用となるので、LQ、SQの消費電力を半減できるという。但し、一般的なマイクロプロセサチップの中でSQの消費電力は2%程度であり、電力に関して詳細な評価は行っていないと述べられている。

研究としては、ストア命令がその結果を使うと予測される後続のロード命令に投機的にデータを渡すという点が新しい着想で面白い。

CAMを無くすというハード構成としては、影響するストア命令をチェックする機構を、比較的小エントリのCAMからブルームフィルタなどのエントリ数の大きいテーブルに置き換えただけという気もするが、とにかく、消費電力を半減させたのは成果である。

ストア命令のデータを暫く後のロード命令が読むケースは、レジスタが不足するために一旦メモリに退避して、その後、復元する、Spill-Fillのケースが大部分であり、この頻度はコンパイラのレジスタスケジューリングの良し悪しやレジスタ数にも依存するので、これらの点がFire and Forget方式の性能にどう影響するかが気になるところである。