バッファの並べ替え

リオーダー バッファ( ROB ) は、 Tomasulo アルゴリズムの拡張で使用され、アウトオブオーダーおよび投機的な命令実行をサポートするハードウェア ユニットです。この拡張機能により、命令が強制的にインオーダーでコミットされます。

バッファは、配列/ベクターとして実装された循環バッファ（ FIFO命令順序付けキューを提供する）です（これにより、命令が順不同で完了したときにその結果を記録できます）。

Tomasulo アルゴリズムには、「発行」、「実行」、「結果の書き込み」の 3 つのステージがあります。アルゴリズムの拡張では、「コミット」ステージが追加されます。コミット ステージでは、命令の結果がレジスタまたはメモリに格納されます。「結果の書き込み」ステージは、結果を再順序付けバッファに配置するように変更されます。この目的のために、各命令はROB 内のインデックスを使用して予約ステーションでタグ付けされます。

バッファの内容は、バッファ内でスケジュールされている他の命令のデータ依存関係に使用されます。バッファの先頭は、その結果が有効になるとコミットされます。その依存関係は、必ずしも隣接している必要はなくとも、バッファ内の命令より前になければならないため、すでに計算され、コミットされています。命令間のデータ依存関係により、命令が依存値を待機している間、パイプラインが停止します。ROB により、パイプラインは、結果がコミットされていることを確認しながら、他の命令の処理を継続できます。これにより、書き込み前の読み取り (RAW)、読み取り前の書き込み (WAR)、書き込み前の書き込み (WAW) などの データ ハザードを防止できます。

拡張アルゴリズムをサポートするために、バッファの各エントリに次の追加フィールドがあります。

• 命令タイプ（ジャンプ、メモリへの保存、レジスタへの保存）
• 宛先（メモリアドレスまたはレジスタ番号）
• 結果（宛先に移動する値、またはジャンプの成功/失敗を示す値）
• 有効性（結果はすでに存在するか？）

リオーダー バッファの結果には、正確な例外と、ターゲット アドレスの予測ミス(分岐またはジャンプ)の簡単なロールバック制御が含まれます。ジャンプ予測が正しくない場合、または命令ストリームで回復不可能な例外が発生した場合、ROB からすべての命令がクリアされ (循環キューの末尾を先頭に設定することにより)、予約ステーションが再初期化されます。

• ハードウェアベースの推測 - Ben H. Juurlink 教授
• バッファの並べ替え