コンピュータアーキテクチャの論文を読んでいたのだが、どうもよく知らない項目がある。 よく考えてみたらコンピュータアーキテクチャの最新トレンドも含め最近勉強量が不足していたので、ここらへんでもう一度復習しておきたい。 せっかくなので海外の大学の講義資料を読んでみよう。
- Advanced Computer Architecture
https://www.ece.ucsb.edu/~strukov/ece154BSpring2018/home.htm
目次
- 1. 半導体のトレンドと背景
- 2.半導体の性能向上
- 3.半導体の性能向上
- 4. キャッシュ階層
- 5. キャッシュ階層
- 6. 高度なキャッシュ最適化
- 7. ILPの向上テクニック
- 8. ILPの向上テクニック, Tomasuloのアルゴリズム
- 9. 分岐予測
- 10. 複数命令発行の技術
Advanced Computer Architecture
もう一つの動的アルゴリズム：Tomasuloのアルゴリズム
IBM 360/91に使用された手法。CDC 6600の3年後に登場した。この手法の目的はより高い性能をコンパイラの技術を借りることなく達成すること。CDC 6600 ISAとの違いは
IBMは浮動小数点レジスタの数が少なく、コンパイラによるスケジューリングには限界がある。そこで、Tomasuloはより効率的にレジスタを使用する方法を考えた。それがハードウェアでのリネーミング。
TomasuloとScoreBoardの違い
- 離散的に管理するか、スコアボードにより集中的に管理するか。
- FU Bufferはリザベーションステーションとも呼ばれる。
- 命令中のレジスタはリザベーションステーションの中で、そのレジスタの値そのもの、もしくはレジスタへのポインタで置き換えられる。「レジスタリネーミング」。
- Function Unitからリザベーションステーションへのデータ転送はレジスタを介さず、Common DataBusを使って転送される。
| コンポーネント | 説明 |
|---|---|
| Op | Function Unitで実行するオペレーション |
| Vj, Vk | ソースオペランドの値 |
| Qj, Ok | リザベーションステーションがソースレジスタを生成するか。 |
| Busy | リザベーションステーションもしくはFunction UnitがBusy |
Tomasuloアルゴリズムの3ステージ
- 発行ステージ：命令をFP Opキューから取得する。
- リザベーションステーションが空いていれば（構造ハザードは発生していない）、コントローラが命令を発行しオペランドを転送する。
- 実行：すべてのオペランドがReady状態であれば演算を実行する。
- そうでなければ、Common Data Busの結果をチェックする。
- 書き込み結果：
- Common Data Busに書き込みを行う。リザベーションステーションを開ける。
Tomasuloの弱点
TomasuloはScoreBoardに比較して複雑になりがち。また、Common Data Busに高速なデータ転送を行うことを要求される。つまり性能はCommon Data Busに制約されることが多い。また、割り込みを正確に受け付けることができない。
Tomasuloのまとめ
リザベーションステーションによって、暗黙的なレジスタリネーミングを行いレジスタセットの数を拡張することができる。これによりレジスタ数がボトルネックになることを防ぎ、WAR、WAWハザードが発生することを防ぐ。
よりILPを抽出するために
分岐予測により、ストール数を減らしILPを向上させる。分岐命令により制御依存が発生するが、これを解決するために「投機実行」を行う。投機実行では、分岐先の予測を行い、プログラムを予測したとおりに実行する。もし予測通りに実行できなければ、予測が失敗しても回復する機構を用意する。
また、コンパイラによりいくつかの投機実行も行うことができる。
ハードウェアベースの投機実行
動的スケジューリングをさらに3つのアイデアで拡張する。
動的分岐予測
- 制御依存が解決する前に、命令を投機実行する。
- 基本ブロックの異なる気見合わせを扱うための動的スケジューリング
Tomasuloによる投機実行
命令の完了とは関係なく命令を実行することを考える。命令は投機的に実行されるが、レジスタやメモリは投機的には更新されない。レジスタやメモリの更新を行うのは、「命令コミット」のタイミングで行われる。命令の実行と終了はアウトオブオーダに完了するが、命令のコミットはインオーダに行われる。
これを実装するために、リオーダバッファ（Reorder Buffer: ROB）を実装する。リオーダバッファには命令の実行が終了からコミットまでの情報が記憶されている。リオーダバッファはFIFOのように動作する。
Tomasuloとリオーダバッファ
オリジナルのTomasulo機構に対して、レジスタファイルと実行ユニットの間にリオーダバッファを挿入する。リザベーションステーションは、タグとしてROBを使用する。命令コミットは、ROBから先頭にFIFOのように行われる。
リオーダバッファの構成
- 命令タイプフィールド：命令が分岐命令・ストア命令・レジスタ書き込み命令なのかを示す。
- 書き込み先フィールド：ロード・ALU操作・ストア命令のメモリアドレスなどのレジスタ番号を示す。
- 値フィールド：命令がコミットされるまでの値を保持する。
- Readyフィールド命令が実行を終了し、値がReadyであることを示す。
メモリハザードの回避
ストア命令は、コミットが完了した場合にのみメモリの値をアップデートする。もしストア命令がアップデートする領域に、ロード命令が先にリクエストを出した場合、ロード命令はストア命令の実行が完了するまでは待たなければならない。
リオーダバッファの実装
実際には、リオーダバッファは、分岐命令の予測が外れた場合は、分岐命令がROBの先頭に来る前になるべく早く復帰しようとする。投機実行プロセッサは、分岐予測の結果に対してより繊細である。
例外に関しては、当該命令がコミットされるまでは例外は発生しない。例外よりも前の分岐命令が完了したときに例外を処理することもできるが、よりチャレンジングな実装となる。
