動的スケジューリング
・Static Scheduling
- Inorder issue / In order completion
- In order issue / Out of order completion
・Dynamic Scheduling
- Out of order issue / Out of order completion
逐次実行列に、広がりを持つ命令ウィンドウを設定
命令ウィンドウ中の実行順序を動的に決定し、性能を最大化する
命令ウィンドウには、資源の許す限り逐次的に投入
命令ウィンドウからは、逐次的に終了
動的命令と静的命令
・静的命令
- プログラムのテキスト上での命令、命令実行順
- プログラマ、コンパイラからは静的命令だけが見える
・動的命令
- CPU上で実行される命令、命令実降順
- CPUの高速化は、動的命令実行の高速化で構成される
動的スケジューリングの理想形態
命令ウィンドウに投入時点において、
・命令実行が完了している命令からのレジスタ、メモリデータはレジスタ、メモリから読み出す
・実実行命令のレジスタ、メモリデータはメモリ、レジスタ経由で引き渡す
・それ以外については、可能な限り命令ウィンドウ内で直接命令間で渡す
命令ウィンドウないでは、
・各命令はデータ依存関係に基づき実行制限される(各入力オペランドが揃った時点で命令実行)
・CPU内資源が無限にある場合に最短の実行実感を得る
・実実行命令に渡すための目ノリ、レジスタでー多は、つねに命令ウィンドウ中の最新に近い命令を特定する
→命令レベル並列性(ILP)の利用
命令ウィンドウの中間から出て行くことはない
命令ウィンドウ内の条件分岐
大きな命令ウィンドウをとるためには、分岐予測をする
ILP利用に対する制御ハザード
・ILP利用 -> データ依存関係に基づく並列による高速化
・制御ハザード
・逐次化の解消
- 遅延分岐命令:遅延スロット数が限定されるため、効果が少ない
- 分岐予測:投機的に逐次実行列を作成、失敗したら巻き戻し
- 深い分岐予測:条件分岐の先の条件分岐を予測
- Dual Rail実行:分岐の両側を並列実行(分岐方向が確定するまで)
(この場合、ウィンドウはりにあでない)
- 条件分岐から条件代入への変換:演算量が急増、並列性は増加
(深い条件分岐には効果がない)
分岐予測
条件分岐に制御依存している命令列を投機的に実行
・静的分岐予測
コンパイラ等が、分岐命令毎に投機的実行を行う方向を設定
- alpha2104では、分岐の方向で設定
- spark等では、命令による登記する分岐方向を指示
- 分岐命令の次に、投機する分岐方向の命令を詰める
- 投機が成功した場合には、処理を続行
- 投機が失敗した場合には、分岐以降の処理をすべて取り消し、正しい場所から再開
- 投機中の副作用は、巻き戻し可能/仮の副作用とする
分岐命令予測の限界
・分岐命令の投機的実行
分岐側を投機する場合、ペナルティなしの設計は困難
投機に失敗したときのペナルティ大
- 仮状態の取り消し
- すでに加えた副作用の巻き戻し
- 並列計算との関連(メモリの一貫性問題)
投機の成功率(ヒット率)が低い
- ループを作る分岐命令
-- ループ毎に1回不成功
- ループ内の条件判断
-- 静的予測困難
:プロファイルに基づく分岐予測
:実行時のプログラム切り替え
- 例外処理ルーチンへの分岐
・トータルだいたい8割
でも、ペナルティの方が大きい
今日ではあまり使われない
動的分岐予測
実行時の過去の履歴から、分岐方向を予測し、投機実行する
- 局所情報:当該分岐命令の過去の分岐履歴、等
- 大局情報:当該分岐命令意外の過去の実行状況、等
- 例:ループを作る分岐を、過去の分岐方向から予測
-- 直前の方向を予測:1回のループ実行で2回ミス(最初と最後)
-- 過去N回の履歴で多い情報:1回のループで1回ミス(最後)
- 例:過去の分岐パターンで、最出のものから予測
-- 2重ループのパターン:1回のループ実行でミスなし
- 例:他の分岐命令から分岐方向を類推
-- プログラム内相関
動的分岐予測方式の歴史
分岐予測表による方向
英国マンチェスタ大, MU-5
・Instruction Accessing in High Speed Computers
Branch Target Buffer
・The MU5 instruction pipeline
2-level分岐予測
Two-Level Adaptive Branch Prediction
GShare方式の分岐予測
分岐予測表(BPT, BTB Branch Prediction Table, Branch Target Buffer)
・条件分岐命令のアドレスと、過去の分岐履歴を表(またはカウンタ)
・1ビット予測:偏った分布でミス回数が倍増
・2ビット予測:飽和カウンタが通常用いられる
飽和カウンタはどれを使ってもあまり変わらない
Branch Target Buffer
・分岐命令表は、分岐命令の成立、不成立を予測
・Branch target Buffer
分岐命令のアドレスの一部から、分岐先アドレスと分岐の予測を得る
:分岐命令の次クロックで分岐先命令のフェッチ
更なる分岐予測制度の向上
命令れべるの並列性の利用
分岐に夜性能低下(クロック)
分岐命令のBTBヒット率 * 予測ミス率 * ミス・ペナルティ
+ (1 - BTBヒット率) * 分岐成立率 * 分岐ペナルティ
+ (1 - BTBヒット率) * 分岐不成立率 * 非分岐ペナルティ
3倍くらいいい
2レベル分岐予測
分岐予測を、分岐のパターンと分岐履歴から予測
PAs方式:Pentium3
分岐パターンの繰り返しを抽出
一つの分岐でもパターン毎に2bc(信頼度カウンタ)を持つ
短い繰り返し回数のループに有効
例:4回繰り返すループの分岐(2重ループ等)
分岐方向 : TTTNTTTN
2bc : TTTTTTTT : 予測ミス率25%
PAs : TTTNTTTN : 予測ミス率0%
patternをアドレスにして、
現在のパターンに従って次を予測する
2レベル分岐予測の種々の方式