スコアボード

スコアボードは、 CDC 6600コンピュータで初めて使用された集中型の方法で、競合がなくハードウェアが利用可能な場合に命令を順不同で実行できるように命令を動的にスケジュールします。^[1]

スコアボードでは、すべての命令のデータ依存性が記録され、追跡され、常に厳密に監視されます。スコアボードが、以前に発行された (「実行中の」) 命令との競合がないと判断した場合にのみ、命令がリリースされます。命令の発行が安全でない (またはリソースが不十分) ために停止した場合、停止した命令が発行される前にすべての依存性が解決されるまで、スコアボードは実行中の命令のフローを監視します。つまり、書き込みハザードがない場合、読み取りが続行され、読み取りハザードがない場合、書き込みが続行されます。

スコアボードは、本質的には、データフロー言語に見られる同じ基礎アルゴリズムのハードウェア実装であり、有向非巡回グラフを作成し、同じロジックがプログラミング言語ランタイムに適用されます。

命令は順番にデコードされ、次の 4 つの段階を経ます。

1. 問題: システムは、この命令によってどのレジスタが読み書きされるか、および書き込み後の読み取り(WAR)、書き込み後の読み取り(RAW)、および書き込み後の書き込み(WAW) の競合が検出される場所を確認します。RAW および WAR の危険は、次の段階で必要になるため、依存関係マトリックス (元の 6600 設計では SR NOR ラッチから構築) を使用して記録されます。同時に、2 番目のマトリックスにエントリが記録され、命令の順序が有向非巡回グラフとして記録されます。出力の依存関係 (WAW) を回避するために、同じレジスタに書き込む予定の命令が完了するまで、命令は停止されます。必要な機能ユニットが現在ビジーの場合も、命令は停止されます。命令は、最初から最後まで完全に追跡できない限り、発行されません。
2. オペランドの読み取り: 命令が発行され、必要なハードウェア モジュール (Thornton の本では計算ユニットと呼ばれています) に正しく割り当てられた後、ユニットはすべてのオペランドが使用可能になるまで待機します。読み取りは、他のすべてのユニットから書き込み依存関係 (RAW) が削除された場合にのみ実行されます。レジスタ ファイル ポートの競合を回避するために、優先度ピッカーは 1 つの計算ユニットを選択します (複数のユニットにハザードがない場合)。
3. 実行: すべてのオペランドがフェッチされると、計算ユニットが実行を開始します。結果が準備できたら、スコアボードに通知されます。
4. 結果の書き込み: この段階では、結果は準備ができていますが、まだ宛先レジスタに書き込まれていません。ユニットがすべての WAR の危険から解放されるまで、書き込みは続行できません。ここでの唯一の追加遅延は、レジスタ ファイル ポートの可用性に基づいています。6600 では、優先度ピッカーを使用して、書き込みポートごとに 1 つの結果が選択されました。書き込まれると、ユニットはビジー状態でなくなったとマークされ、すべての危険と状態が削除されます。「シャドウ」機能を備えた高度な (拡張された、正確な) スコアボードでのみ、結果の書き込みフェーズが防止 (遅延) されることに注意してください。オリジナルの 6600 にはこの機能はありませんでした。

読み取りは書き込みハザードがない場合にのみ実行され、書き込みは読み取りハザードがない場合にのみ実行されることに注意することが重要です。これは論理的ですが、予想に反しています。特に、書き込みは、他のユニットがレジスタ内の現在の値を読み取る機会を与え、新しい値で上書きする前に、読み取り後に書き込みを待機する必要があることに注意してください。これが、書き込みがWAR ハザードが なくなるまで待機する必要がある理由です。

命令の実行を制御するために、スコアボードは次の 3 つのステータス テーブルを維持します。

• 命令ステータス: 実行中の各命令が 4 つのステージのどの段階にあるかを示します。
• 機能ユニットの状態: 各機能ユニットの状態を示します。各機能ユニットはテーブル内に 9 つのフィールドを保持します。
  • ビジー: ユニットが使用中かどうかを示します
  • Op: ユニット内で実行する演算 (例: MUL、DIV、MOD)
  • F _i : 宛先レジスタ
  • F _j ,F _k : ソースレジスタ番号
  • Q _j、Q _k : ソースレジスタF _j、F _{kを生成する機能ユニット}
  • R _j、R _{k : F j}、F _kが読み取り可能かどうか、まだ読み取りが完了していないかどうかを示すフラグ。
• レジスタ ステータス: 各レジスタについて、どの機能ユニットが結果を書き込むかを示します。

元の特許で概説されているスコアボード制御の詳細なアルゴリズムを以下に説明します。

 関数issue( op , dst , src1 , src2 )
    wait until (!Busy[FU] AND !Result[ dst ]); // FUは操作opを実行できる任意の機能ユニットです。
    忙しい[FU] ← はい;
    Op[FU] ← op ;
    F i [FU] ← ds​​t ;
    F j [FU] ← src1 ;
    F k [FU] ← src2 ;
    Q j [FU] ← 結果[ src1 ];
    Q k [FU] ← 結果[ src2 ];
    Rj [FU] ← Qj [ FU ] == 0;
    Rk [FU] ← Qk [ FU ] == 0;
    結果[ dst ] ← FU;

 関数read_operands( FU )
    (R j [ FU ] AND R k [ FU ]) になるまで待機します。
    R j [ FU ] ← いいえ;
    R k [ FU ] ← いいえ;

 関数実行( FU )
    // FUが実行する必要がある
ことを実行する

 関数write_back( FU )
    (∀f {(F j [f]≠F i [ FU ] OR R j [f]=No) AND (F k [f]≠F i [ FU ] OR R k [f]=No)})となるまで待つ
    foreach f 実行
        Q j [f] = FUの場合、R j [f] ← Yes;
        Q k [f] = FUの場合、R k [f] ← Yes;
    Result[F i [ FU ]] ← 0; // 0はFUがレジスタの結果を生成しないことを意味する
    RegFile[F i [ FU ]] ←計算値;
    忙しい[ FU ] ← いいえ;

ソーントンの本は現代のコンピューター用語よりも古いものです。

• 関数ユニット (パイプライン) は「計算ユニット」と呼ばれていました。
• 「ファースト・オーダー・コンフリクト」は、すべてのユニットが多忙であることによる失速と、WAWのコンフリクトの両方をカバーしました。^[2]
• 「第二次紛争」はRAW紛争を表す用語であった。^[3]
• 「第三次紛争」は戦争紛争をカバーした。^[4]

ストールは、"First Order" の競合が検出された問題段階でのみ発生しました。Tomasuloのアルゴリズムなどの他の手法では、レジスタ名の変更によって WAW の依存関係も解決されます。元のCDC 6600 には WAW のハザード追跡機能が搭載されていなかった可能性があります。これは、設計者が製品を納品してから 7600 に移行しなければならなかったためです。代わりにストールが最も適切なオプションでした。レジスタ名の変更をスコアボードに追加しない技術的な理由はありません。

両方のアルゴリズムの分析はルーク・レイトンによって行われ、トマスロアルゴリズムと6600スコアボードアルゴリズムの同等性を示す変換プロセスが概説されました。^[5] WAWハザード解決は確かに元のアルゴリズムには欠けています。6600は書き込みハザードの最初の発生時に停止します。^[6]

• 命令レベルの並列性
• トマスロアルゴリズム
• アウトオブオーダー実行

• Glenford Myers、「マイクロプロセッサ チップ上のレジスタ スコアボード」、米国特許 4891753

• ダイナミック スケジューリング - スコアボード
• コンピュータアーキテクチャ：定量的アプローチ、ジョン・L・ヘネシー＆デビッド・A・パターソン
• EECS 252 大学院コンピュータアーキテクチャ講義 XX - トピック、電気工学およびコンピュータサイエンス、カリフォルニア大学バークレー校。
• スコアボードの例