トマスロのアルゴリズム

トマスロのアルゴリズムは、命令の動的スケジューリングを行うコンピュータアーキテクチャハードウェアアルゴリズムであり、アウトオブオーダー実行を可能にし、複数の実行ユニットをより効率的に使用できるようにします。1967年にIBMのロバート・トマスロによって開発され、 IBM System/360 Model 91の浮動小数点ユニットに初めて実装されました。^[1]

Tomasulo のアルゴリズムの主な革新には、ハードウェアでのレジスタ名の変更、すべての実行ユニットの予約ステーション、および計算された値を必要とする可能性のあるすべての予約ステーションにブロードキャストされる共通データ バス (CDB) などがあります。これらの開発により、スコアボードやその他の以前のアルゴリズムの使用では停止していた命令の並列実行が改善されます。

ロバート・トマスロは、このアルゴリズムに関する研究で1997年にエッカート・モークリー賞を受賞した。 ^[2]

Tomasulo のアルゴリズムの実装に必要な概念は次のとおりです。

共通データバス (CDB) は、予約ステーションと機能ユニットを直接接続します。Tomasulo によれば、CDB は「同時実行性を促進しながら優先順位を維持する」とのことです。^{[1] : 33}これには 2 つの重要な効果があります。

1. 機能ユニットは、浮動小数点レジスタを介さずに任意の演算の結果にアクセスできるため、結果を待機している複数のユニットは、レジスタ ファイルの読み取りポートへのアクセスの競合を解決するまで待たずに処理を続行できます。
2. ハザード検出と制御実行は分散されています。 単一の専用ハザード ユニットではなく、予約ステーションが命令の実行タイミングを制御します。

命令は順番に発行されるため、命令シーケンスの効果（これらの命令によって発生する例外など）は、順序どおりに実行されていない（つまり、順番どおりに実行されていない）という事実に関係なく、インオーダー プロセッサの場合と同じ順序で発生します。

Tomasulo のアルゴリズムは、レジスタ名の変更を使用して、アウトオブオーダー実行を正しく実行します。すべての汎用レジスタと予約ステーション レジスタは、実数値またはプレースホルダー値のいずれかを保持します。発行段階で宛先レジスタに実数値が使用できない場合は、最初にプレースホルダー値が使用されます。プレースホルダー値は、実数値を生成する予約ステーションを示すタグです。ユニットが終了し、結果を CDB にブロードキャストすると、プレースホルダーは実数値に置き換えられます。

各機能ユニットには 1 つの予約ステーションがあります。予約ステーションには、演算やオペランドなど、1 つの命令を実行するために必要な情報が保持されます。機能ユニットは、空いていて、命令に必要なすべてのソース オペランドが実数である場合に処理を開始します。

実際には、例外に関する十分なステータス情報が利用できない例外が存在する可能性があり、その場合、プロセッサは不正確な例外と呼ばれる特別な例外を発生させることがあります。プロセッサの状態はプログラム順序でのみ変更されるため、不正確な例外はインオーダー実装では発生しません ( 「クラシック RISC パイプライン § 例外」を参照)。

正確な例外が発生するプログラムでは、例外が発生した特定の命令を特定できるため、例外が発生した時点から再開または再実行できます。ただし、不正確な例外が発生するプログラムは、例外が発生した特定の命令をシステムが特定できないため、通常は再開または再実行できません。

以下にリストされている 3 つのステージは、各命令が発行されてから実行が完了するまでに通過するステージです。

• RS - 予約状況
• RegisterStat - レジスタ ステータス。レジスタに関する情報が含まれます。
• regs[x] - レジスタxの値
• Mem[A] - アドレスAのメモリの値

• rd - 宛先レジスタ番号
• rs、rt - ソース登録番号
• imm - 符号拡張即値フィールド
• r - 命令が割り当てられている予約ステーションまたはバッファ

• Op - オペランドに対して実行される演算を表します
• Qj、Qk - 関連するソースオペランドを生成する予約ステーション（0は値がVj、Vkにあることを示します）
• Vj、Vk - ソースオペランドの値
• A - ロードまたはストアのメモリアドレス情報を保持するために使用される
• ビジー - 使用中の場合は 1、使用中でない場合は 0

• Qi - このレジスタに結果を格納する予約ステーション（空白または 0 の場合、このレジスタには値が格納されません）

発行段階では、すべてのオペランドと予約ステーションが準備できていれば命令が実行用に発行され、準備できなければ命令は停止されます。このステップでレジスタの名前が変更され、WAR および WAW の危険性が排除されます。

• 命令キューの先頭から次の命令を取得します。命令オペランドが現在レジスタ内にある場合は、
  • 一致する機能ユニットが使用可能な場合は、命令を発行します。
  • それ以外の場合は、利用可能な機能ユニットがないため、ステーションまたはバッファが空くまで命令を停止します。
• それ以外の場合は、オペランドがレジスタ内にないと想定して、仮想値を使用します。機能ユニットは、オペランドを生成する機能ユニットを追跡するために実際の値を計算する必要があります。

実行ステージでは、命令操作が実行されます。このステップでは、すべてのオペランドが使用可能になるまで命令が遅延され、RAW ハザードが排除されます。メモリを介したハザードを防止するために、有効なアドレス計算によってプログラムの正確性が維持されます。

• 1 つ以上のオペランドがまだ使用できない場合は、CDB でオペランドが使用できるようになるまで待機します。
• すべてのオペランドが利用可能な場合、命令がロードまたはストアの場合
  • ベースレジスタが利用可能なときに実効アドレスを計算し、ロード/ストアバッファに格納します。
    • 命令がロードの場合: メモリユニットが利用可能になったらすぐに実行する
    • それ以外の場合、命令が保存である場合は、値が保存されるまで待ってからメモリユニットに送信します。
• それ以外の場合、命令は算術論理ユニット（ALU）操作であり、対応する機能ユニットで命令を実行します。

書き込み結果ステージでは、ALU 操作の結果がレジスタに書き戻され、ストア操作がメモリに書き戻されます。

• 命令がALU演算の場合
  • 結果が利用可能な場合は、それをCDBに書き込み、そこからレジスタとこの結果を待っている予約ステーションに書き込みます。
• それ以外の場合、命令がストアだった場合は、このステップでデータをメモリに書き込みます。

Tomasulo のアルゴリズムにおける予約ステーション、レジスタ名の変更、共通データ バスの概念は、高性能コンピュータの設計に大きな進歩をもたらします。

予約ステーションは、データ依存性や、ストレージアクセス時間や回路速度の変動などの不整合がある場合にオペランドを待つ責任を引き受け、機能ユニットを解放します。この改善により、長い浮動小数点遅延とメモリアクセスが克服されます。特に、アルゴリズムはキャッシュミスに対してより寛容になります。さらに、プログラマーは最適化されたコードを実装する必要がなくなります。これは、共通データバスと予約ステーションが連携して依存性を維持し、並行性を促進する結果です。^{[1] : 33}

予約ステーション内の命令のオペランドを追跡し、ハードウェアでレジスタ名を変更することで、このアルゴリズムは書き込み後の読み取り(RAW) を最小限に抑え、書き込み後の書き込み(WAW) と読み取り後の書き込み(WAR) というコンピュータアーキテクチャの 危険性を排除します。これにより、停止に必要な無駄な時間が削減され、パフォーマンスが向上します。^{[1] : 33}

このアルゴリズムの同様に重要な改良点は、設計が特定のパイプライン構造に限定されないことです。この改良により、このアルゴリズムは、マルチイシュープロセッサでより広く採用されるようになりました。さらに、このアルゴリズムは分岐投機を可能にするために簡単に拡張できます。^{[3] : 182}

Tomasulo のアルゴリズムは、System/360 Model 91 アーキテクチャに実装されました。IBM 以外では、数年間使用されていませんでした。しかし、1990 年代には、次の 3 つの理由から、使用が大幅に増加しました。

1. キャッシュが一般的になるにつれて、キャッシュ ミスによって発生する予測不可能なロード時間中に同時実行性を維持するアルゴリズムの能力がプロセッサにとって重要になりました。
2. アルゴリズムからの動的スケジューリングと分岐推測により、プロセッサが発行する命令が増えるにつれてパフォーマンスが向上します。
3. 大量販売ソフトウェアの普及により、プログラマーは特定のパイプライン構造に合わせてコンパイルする必要がなくなりました。アルゴリズムはどのパイプラインアーキテクチャでも機能するため、ソフトウェアにはアーキテクチャ固有の変更がほとんど必要ありません。^{[3] : 183}

多くの現代のプロセッサは、人気のIntel x86-64チップを含む、Tomasuloのオリジナルアルゴリズムのバリエーションである動的スケジューリング方式を実装しています。^{[5] [検証失敗] [6]}

• リオーダーバッファ（ROB）
• 命令レベルの並列処理(ILP)

• Savard, John JG (2018) [2014]. 「パイプラインとアウトオブオーダー実行」. quadibloc . 2018-07-03 にオリジナルからアーカイブ。2018-07-16に取得。

• ダイナミック スケジューリング - Wayback Machineの Tomasulo のアルゴリズム(2017 年 12 月 25 日アーカイブ)
• Tomasulo アルゴリズムの HASE Java アプレット シミュレーション