Tomasuloアルゴリズム(2)

次のFADD命令はADDER側のリザベーションステーションのRA1エントリに格納される。ここでF2はBusyではないので値を読み出してRA1のOP2部に格納できるが、FDIVの結果を待っているF1は、Busyビットが"1"であり、値を読むことは出来ない。したがって、この場合はF1のTag部に格納されているRM1をリザベーションステーションRA1のタグ部に書き込む。そして、結果を格納するレジスタF4のBusyビットを"1"にセットし、タグ部にはRA1を格納しておく。そして、このFADD命令はオペランドが揃うまで、実行は開始されない。

その次のFSUB命令はオペランドのF2、F3ともにBusyではないので、レジスタの値とともにリザベーションステーションRA2に格納される。そして、結果を格納するレジスタF1のBusyビットを"1"にセットし、タグにRA2を書き込む。

このFSUB命令はオペランドが揃っているので、演算器や演算結果を格納するCDBバスの使用権が確保でき次第、前にあるFADD命令よりも先に実行される。

ここまでの説明を読んで、FSUB命令がF1のタグにRA2を書き込むことになると、FDIVの書いたタグRM1を上書きしてしまうので、どうなってしまうのかと気付かれた読者は、注意深く読んで戴いている方である。

ここでFSUBの方がFDIVよりも先に実行を終わると、その結果がRA2というタグとともにCDBに載せられる。そして、リザベーションステーションやレジスタファイルの各エントリは、Busyが"1"であれば、両方の演算器で共用されているCDBに載せられた演算結果のタグと自分のタグを比較して、タグが一致していれば値を取り込み、Busyビットを"0"にする。この例では、レジスタF1のタグとFSUBの演算結果のタグが一致するので、F1にFSUBの結果が格納される。

その後、FDIVが終了すると、その結果とRM1というタグがCDBに載せられる。このとき、レジスタF1のBusyビットは"0"であり、かつ、タグもRM1ではないので、F1はFDIVの結果を取り込まない。一方、FADD命令を格納しているADDERのリザベーションステーションのRA1エントリは、その一方のオペランドのタグがRM1になっており、このFDIVの結果を取り込む。

そして、この結果の取り込みにより双方のオペランドが揃うので、演算器やCDBの使用権を確保してFADDの実行が行われる。

そして、FADDの実行が終わると加算結果とタグRA1がCDBに載せられ、マッチするタグを持つレジスタF4がその結果を取り込む。

結果として、F1にはFSUB命令の結果が格納され、F4にはFDIVの結果を正しく反映したFADD命令の結果が格納されており、これらの命令をプログラム順に実行した場合とまったく同じ結果が得られる。

FADD命令はFDIV命令に対してRAWハザードがあり、FSUB命令はFADD命令に対してWARハザード、FDIV命令に対してWAWハザードがあり、スコアボード制御の場合は、これらのハザードを解消するためにストールが必要であるが、Tomasuloアルゴリズムでは、リザベーションステーションという構造を追加し、タグのマッチングによりCDBのデータを取り込むというメカニズムでWAR、WAWハザードを解消しているのでアウトオブオーダで実行できる範囲が広がっている。

なお、ここでは説明を簡単にするため、レジスタと演算器だけで説明したが、IBM System360 Model 91に実装された回路は、次の図6.14のようになっており、メモリからのロードデータを保持するロードバッファ(左上)とメモリへのストアデータを保持するストアバッファ(中央右)がある。そして、メモリからデータが到着すると、ロードバッファの内容をCDBや図6.14でFLB BUSと書かれたバスを経由して、レジスタファイルやリザベーションステーションに送ることが出来るようになっており、リザベーションステーションの番号以外に、このロードバッファの各エントリの番号もタグとして使用され、ロード命令の場合もレジスタ間の演算と同様にアウトオブオーダでうまく動作するようになっている。

このようにTomasuloアルゴリズムを用いるとWARハザードやWAWハザードを自動的に回避してOut of Order実行ができるのであるが、問題もある。前出の例の

FDIV F1←F2、F3
FADD F4←F1、F2
FSUB F1←F2、F3

で、FSUB命令がF1レジスタに結果を格納した時点で割り込みが入ると、F1はFSUBの結果を格納しているのに、実行時間の長いFIDV命令の結果のF1や、それに依存するF4には結果が入っておらず、プログラム順に実行した場合とは矛盾した状態となる。

割り込みに際して、プログラム順の実行と矛盾が無い状態が得られるマイクロアーキをPrecise(正確な)割り込みアーキテクチャと呼ぶ。一方、Tomasulo機構での実行のように矛盾した状態ができるのをImprecise(正確でない)割り込みアーキテクチャと呼ぶ。このようなImpreciseな割り込みの場合、割り込み処理を行ってから元の命令処理に戻ることができないという問題がある。このため、現在では、Tomasuloアルゴリズムそのままではなく、Preciseな割り込みを実現するように改良された構造が用いられる。