Tomasuloアルゴリズム(1)

Tomasuloアルゴリズム

1966年に発表されたIBMの初期のスーパーコンピュータである「System 360 model 91」は、後に「Tomasuloアルゴリズム」と呼ばれることになるアウトオブオーダ実行機構を実装していた。Robert Tomasulo氏のアイデアは、処理結果を格納するレジスタについて、その論理的なレジスタ番号と物理的にデータを保持する実体としてのレジスタを分離した点が卓越している。

通常の浮動小数点演算器は、次の図6.5のような構造になっている。ただし、この図では、簡単にするために、メモリへのロードストアのパスは省略している。

図6.5の左上の黄色のInst Bufと書かれた箱は、浮動小数点演算命令をプログラム順に格納するキューであり、このキューから順に命令が取り出されてデコードされる。そして、このデコードされた結果に従ってオペランドとなるFPレジスタファイルのエントリを読み出す。下側の2つの台形が浮動小数点加算器(ADDER)と浮動小数点乗除算器(MUL/DIV)であり、レジスタファイルから読み出されたオペランドに対して、デコードされた演算種別に従って演算を行い、演算結果を右上のFPレジスタファイルに格納する。

前述のWAWハザードの例である

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

の命令列において、FDIV命令の結果を格納するF1と次のFADD命令のF1は同じレジスタでなければならないが、FSUB命令の結果を格納するF1は、必ずしも、FDIV命令とFADD命令のF1と同じレジスタである必要はない。例えば、FSUB命令がF1を再利用せずFSUB F4←F2、F3とプログラムに書かれていれば、同じ処理を行ってもWAWハザードにはならない。また、WARハザードの例の

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

も後続のFADD命令がF2では無くF6に結果を書きこみ、先行するFDIV命令の入力オペランドであるF2レジスタを変更しなければWARハザードは存在しない。つまり、WAWやWARハザードは、結果を格納するレジスタ番号が同じにならないようにプログラムを書き換えてやれば解消できる。

Tomasulo氏は、このレジスタ番号の書き換えをハードウェアで行うことにより、プログラムの変更無しにWAWとWARハザードを解消する方法を考案した。

図6.6に見られるように、Tomasulo氏の構造では、演算器の前に、リザベーションステーションと呼ばれる構造(RA1～3とRM1、2)が追加されている。また、演算結果は、浮動小数点レジスタファイルに格納される以外に、この新たに追加された構造にも入力されており、さらに、浮動小数点レジスタファイルの各エントリにはBusyビットとタグが追加されている。

Tomasulo構造では、命令バッファから命令を読み出し、リザベーションステーションに空きがあれば、その空きエントリに命令を格納する。並行して、オペランドとして指定されたレジスタをアクセスする。つまり、スコアボード方式のIssueとRead Operandsを並行して実行する。ここで、アクセスされたレジスタのBusyビットが"0"の場合はレジスタはValidな値を保持していることを示しており、その値を読んでリザベーションステーションのOP1、あるいはOP2部分に格納する。

一方、アクセスされたレジスタのBusyビットが"1"の場合は、先行命令による演算結果が格納されるのを待っているエントリであり、現在、レジスタに格納されている値は正しくないことを意味している。その場合には、レジスタのタグの値をリザベーションステーションに格納する。

そして、デコードされた命令の結果を格納するレジスタは、Busyビットを"1"にセットして演算結果待ちであることを表示し、その結果を生成する命令を保持しているリザベーションステーションのエントリ番号をタグとして格納する。

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

という命令列の場合、最初のFDIV命令はレジスタF2とF3の値とともにMUL/DIV側のリザベーションステーションの最初のエントリ(ここでは、MUL/DIV側のリザベーションステーションをRM1、RM2と表す)であるRM1に格納する。

そして、結果を格納するF1レジスタのBusyビットを"1"とし、Tagには結果を生成するRM1を書き込んでおく。そして、演算器やCommon Data Bus(CDB)と呼ぶ結果のバスの使用権が確保できると、FDIV命令の実行が開始される。