ちょっといろいろとCPUの投機実行について調べる必要があって，Runahead実行についていい資料があったのでまとめてみることにした．
資料自体は以下：Runahead Executionを最初に提案した Onur Mutlu 先生直々の講義資料なので，これを読めばまあ間違いなかろう．
前回のブログ：
- 問題：依存キャッシュ・ミス
- Ruaheadにおいて，Load2 が Load1の結果に依存する場合
- Runahead の実行では、依存するミスを並列化できない
- 業績向上の機会を逸した
- 無駄なエネルギー
- この制限が理想的に克服されれば、Runahead の性能は25％向上するだろう
- AVD 予測
- 低コストなメカニズムで、Runaheadモードでの依存L2キャッシュミスの並列化を可能にする。
- どうやって？
- L2ミスアドレス（ポインタ）ロードの値を予測する
- アドレス・ロード：アドレスをデスティネーション・レジスタにロードする。
- データ・ロードとは対照的
- AVD予測 [MICRO’05]
- ロード命令のAVD（Address-Value Delta）は、次のように定義される：
- AVD＝ロードの実効アドレス-ロードのデータ値
- アドレス・ロードによっては、AVDは安定する
- AVDプレディクタは、アドレスロードのAVDを追跡する。
- RunahedモードでロードがL2ミスした場合，AVD予測子が参照される
- もしプレディクターがそのロードに対して安定した（確信の持てる）AVDを返せば、ロードの値は予測される。
- 予測値＝実効アドレス-予測AVD
- ロード命令のAVD（Address-Value Delta）は、次のように定義される：
- 安定したAVDはなぜ起こるのか？
- データ構造の規則性
- メモリへの確保のされ方
- トラバース
- 安定したAVDを持つロードは2種類ある
- トラバーサルアドレスのロード
- アドレス・ロードによって消費されるアドレスを生成する
- リーフアドレスのロード
- データロードによって消費されるアドレスを生成する
- トラバーサルアドレスのロード
- データ構造の規則性
- トラバーサル・アドレスのロード
- リンクリストが規則的に割り当てられる場合：
- トラバーサルアドレスのロードは，次のノードへのポインタをロードすることになる
- リーフアドレスのロード
- パーサで辞書をソート：ノードは文字列（ワード）を指す文字列とノードが連続して割り当てられる
- リーフアドレスロードは、各ノードの文字列へのポインタをロードする
- AVD 予測の性能
- 実行時間を約14.3%削減し，実行命令を約15.5%削減する
