Scoreboarding

Scoreboarding とは、CDC 6600で用いられた、命令の衝突がなくハードウェアが利用できる状態のときにアウト・オブ・オーダー実行を行うためにパイプラインを中央管制的にスケジュールするための方法である。Scoreboarding では、すべての命令のデータ依存性が記録され、各命令は過去に発行したまだ完了していない命令との衝突がないとスコアボードが判断した場合のみ解放される。ある命令の実行が安全ではないと判断され、実行を停止した場合には、その命令が発行されたときに存在していたすべての依存関係が解決するまでスコアボードが実行のフローを監視しつづける。

ステージ

命令はインオーダーでデコードされ、以下の４つのステージを経て実行される。

1. 発行: システムは命令によりどのレジスタを読み出すか、どのレジスタに書き込むかをチェックする。この情報は以降のステージで必要になるため記憶される。書き込み同士の依存関係(WAW ) を避けるため、命令は同じレジスタに書き込もうとしている命令が完了するまで停止する。また、命令は必要な機能ユニットが使用中である場合にも停止する。
2. オペランドの読み出し: 命令が発行され、すべての必要なハードウェアモジュールに対して割り当てられると、命令はすべてのオペランドが利用できるようになるまで待機する。この処理により、読み書きの真の依存関係を解決する(書き込み後の読み込み(RAW) )。他の命令で書き込もうとしているレジスタは、実際に書き込みが終わるまで「利用可能」でないとみなせるからである。
3. 実行:すべてのオペランドが読み込まれ、機能ユニットが実行を開始する。演算結果が出ると、スコアボードは通知を受ける。
4. 結果の書き込み: このステージで、演算結果が出力先のレジスタに書き込もうとする。しかし、この処理は以前の命令—この命令が書き込むレジスタを読み出そうとする—が「オペランド読み出し」のステージを完了するまで遅延される。このようにして、いわゆるデータ依存性(WAR - 読み込みの後の書き込み）を解決することができる。

アルゴリズム

スコアボードを制御する詳細なアルゴリズムを示す:

  '''function''' issue(''op'', ''dst'', ''src1'', ''src2'')
     wait until (!Busy[FU] AND !Result[''dst'']); // FU は、操作 'op' を実行できる任意の機能ユニット
     Busy[FU] ← Yes; 
     Op[FU] ← ''op'';
     F<sub>i</sub>[FU] ← ''dst'';
     F<sub>j</sub>[FU] ← ''src1'';
     F<sub>k</sub>[FU] ← ''src2'';
     Q<sub>j</sub>[FU] ← Result[''src1''];
     Q<sub>k</sub>[FU] ← Result[''src2''];  
     R<sub>j</sub>[FU] ← not Q<sub>j</sub>;
     R<sub>k</sub>[FU] ← not Q<sub>k</sub>;
     Result[''dst''] ← FU;
  
  '''function''' read_operands(''FU'')
     wait until (R<sub>j</sub>[''FU''] AND R<sub>k</sub>[''FU'']);
     R<sub>j</sub>[''FU''] ← No;
     R<sub>k</sub>[''FU''] ← No;
  
  '''function''' execute(''FU'')
     // ''FU'' が実行するべきことをすべて行う
  
  '''function''' write_back(''FU'')
     wait until (<math>\forall</math>f {(F<sub>j</sub>[f]≠F<sub>i</sub>[''FU''] OR R<sub>j</sub>[f]=No) AND (F<sub>k</sub>[f]≠F<sub>i</sub>[''FU''] OR R<sub>k</sub>[f]=No)})
     foreach f do
         if Q<sub>j</sub>[f]=''FU'' then R<sub>j</sub>[f] ← Yes;
         if Q<sub>k</sub>[f]=''FU'' then R<sub>k</sub>[f] ← Yes;
     Result[F<sub>i</sub>[''FU'']] ← 0;
     Busy[''FU''] ← No;

注目すべき点

スコアボードの手法では、機能ユニットが一つも利用できない場合、発行のステージを停止させなければならない。この場合、この構造的な（機能ユニットによる）ハザードが解決するまで将来実行できる命令が待機する必要がある。Tomasuloのアルゴリズムのような技法では、レジスタリネーミングを用いて構造的なハザードや WAR や WAW の依存関係を解決できる。

関連項目

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

外部リンク

• Dynamic Scheduling - Scoreboard
• Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson
• EECS 252 Graduate Computer Architecture Lec XX - TOPIC, Electrical Engineering and Computer Sciences, Berkeley, University of California.