8.2.3 データ値予測を用いたプ
ロセッサ性能の向上手法
出典
Compiler Controlled Value Prediction using Branch Predictor
Based Confidence”,
Eric Larson and Todd Austin,
33rd International Symposium on Microarchitecture,
December 2000
概要






命令レベル並列性を抽出し、高性能プロセッサの実現を目指す。
ハードウェア量を抑えながらデータ値予測の利点を生かすため、
コンパイラによる最適化手法を議論する。
3つの最適化手法を提案する。

分岐予測を利用したデータ値予測の確信度評価

クリティカルパスを利用するデータ値予測の候補選択

予測ミスに強い分岐命令(BEQIT命令)の追加
SPEC95, SPEC2000 の8つのプログラムを負荷とするシミュレー
ションにより有効性を検証する。
ソフトウェアのみの最適化により4.6%の性能向上を達成。
ハードウェアのみの実装による32KBと比較して、1KBという非常に
小さい予測テーブルの追加のみで、15.2%の性能向上を達成。
2
データ値予測による命令レベル並列性の向上
ロード/ストア
アーキテクチャ
r3 <- load X
r4 <- add r3, r1
r5 <- sub r4, r8
load, cache miss (60 cycle)
add sub
time
load, cache miss (60 cycle)
predict the data value
add sub
3
背景 (1)








データ依存関係と、制御依存関係により生じる制約が高性能プロセッサの
設計を困難にする。
過去の研究から、多くの命令の計算結果は予測可能であることが示され、
データ値予測の提案へとつながってきた。
データ値予測は、命令の計算結果を予測することで真のデータ依存関係
を切断し、データ依存関係のある命令を並列に実行することで性能を稼ぐ。
Last-value, stride, context-base, hybrid の予測手法が提案されてきた。
これまで、多くの研究はハードウェアによるデータ値予測の実現を中心に
議論してきた。
ハードウェアでの単純な実装では、データ値予測に失敗した場合に数十サ
イクルのペナルティが課せられるため、高い精度で予測が当たる命令のみ
がデータ値予測の対象となっていた。
データ値予測の利用範囲を広げるために、確信度評価の導入が議論され
てきた。
確信度評価とはデータ値予測がヒットかミスかを評価し、ヒットすると評価
された場合のみデータ値予測を利用することで、予測ミスを削減する。
4
背景 (2)





ハードウェアによるデータ値予測の実装は高い性能をもたらすが、ハード
ウェアコストは非常に高い(キャッシュと同等かそれ以上)。
プロファイルを利用して、データ値予測の候補を選択するコンパイラ技術
が議論されてきたが、これまで、ソフトウェアベースのものは高い性能を達
成できなかった。
その理由の一つが、ソフトウェアベースのものは確信度評価をとりいれて
いなかったことにある。
もう一つの理由が、命令数の増加をおさえるために、複雑な予測アルゴリ
ズムが利用できない点にある。
これを解決するために命令セットに特別な命令を追加して、予測値の生成
はハードウェアに任せる解決策が提案されているが、この場合にも、候補
選択や予測ミスからの回復はコンパイラの仕事となっている。
5
目的

ハードウェア量を抑えながら、データ依存関係を緩和し、命令レベ
ル並列性を抽出するデータ値予測(value prediction)の実現を目
指す。

コンパイラによる次の3つの最適化手法を提案する。

分岐予測を利用したデータ値予測の確信度評価


確信度評価を利用することでデータ値予測の正確さを向上
クリティカルパスを利用するデータ値予測の候補選択

すべての命令をデータ値予測の候補とすると、オーバヘッドがおおき
くなるので、効果のありそうな命令を静的に選択する。

予測ミスに強い分岐命令(BEQIT命令)の追加
6
データ値予測の最適化手法
本章では、コンパイラが制御する次の3つの最適化手法の
詳細を検討する。

分岐予測を利用したデータ値予測の確信度評価




既存の分岐予測を確信度評価の機構として利用
高い精度を保ちつつ、データ値予測を利用する/しないの動的な
選択が可能
クリティカルパスを利用するデータ値予測の候補選択

最適化を施す命令を、クリティカルパスの位置情報により決定

コンパイラによりデータ値予測を利用する命令を静的に選択
予測ミスに強い分岐命令(BEQIT命令)の追加

プログラムの正しさを保証しながら、必要のない分岐予測ミスを排
除する分岐命令を追加
7
分岐予測を利用したデータ値予測の確信度評価






データ値予測による利得を得るには、確信度評価が必要
過去の履歴を保存しておく必要があるためソフトウェアで実装す
るのは困難
この複雑さを回避するために、データ値予測の確信度評価として、
分岐予測を利用することを提案
第一の利点は、確信度を評価するための情報と予測ミスの手段
が、すでにプロセッサに組み込まれていること
加えて、ハードウェアで実装された強力な分岐予測のアルゴリズ
ムにより、ソフトウェアの実装より高い精度を達成
分岐予測を利用するために、データ値予測の正解を分岐の不成
立に、データ値予測の間違いを分岐の成立に対応づける。
8
分岐予測を利用する確信度評価の例 (1)
最適化前
最適化後
r3 <- load X
r4 <- add r3, r1
r5 <- sub r4, r8
r3 <- predict index
r9 <- load X
r10 <- cmpeq r9, r3
beq r10, fixup
A: update index, r3
r4 <- add r3, r1
r5 <- sub r4, r8
Load X
r3
add
r4
r1
r8
fixup: r3 <- mov r9
br A
sub
r5
Dataflow
9
分岐予測を利用する確信度評価の例 (2)






この例では、ロード命令に最適化(データ値予測)が施され
る。
ロード命令の結果は、この領域で利用されていないレジスタ
r9 に格納される。
予測されたデータ値はオリジナルなレジスタ r3 に格納され
る。
ロード命令のあとに比較と分岐命令が追加され、これによ
りデータ値予測の正当性を保証する。
データ値予測にミスした場合には、分岐が成立して、補償
コードを実行し、適切なデータ値がレジスタ r3 に格納される。
データ値予測に成功した場合には、補償コードは実行され
ず、予測された値を利用して処理が進んでいく。
10
分岐予測を利用する確信度評価の例 (3)


分岐命令がデータ値予測の確信度を評価する尺度となる。
もし、分岐予測が分岐不成立と予測したとすると、データ値
予測が正しいという高い確信度を与えたことになる。


もし、分岐予測が分岐成立と予測したとすると、データ値予
測が正しいという確信度を低く評価したことになり、最適化さ
れていないパスを実行する。


この場合には、データ依存関係をもつ命令は予測された値を用いて
直ちに実行される。
最適化されていないパスでは、ロード命令により得られる値を利用す
るので、ロード命令の結果が得られてから処理が進んでいく。
分岐予測が失敗した場合には、分岐予測ミスのコストがペナ
ルティとして課せられる。
11
分岐予測を利用する確信度評価の例 (4)






Predict命令, update命令を利用して、データ値の予測と、予測
テーブルの更新をおこなう。
これらの命令はISAに追加される。
これらの命令は、データ値を予測するハードウェア・テーブルのイ
ンデックスを指定する。
異なる predict命令で、異なったインデックスを利用することで、利
用するテーブルを区別する。
それぞれの predict命令には対応する update命令が存在し、この
update命令により正しい値が予測機構に伝えられる。
ソフトウェアのみの実現に関して、レジスタの替わりにメモリを利用
する場合を検討してみたが、メモリ操作の増加により速度向上は
得られなかった。
12
データ値予測の候補選択

次式が当てはまる場合に最適化手法を利用すべき。
OPTaccuracy × OPTbenefit >> OPTinaccuracy × OPTpenalty
OPTaccuracy = 正しく予測したデータ値予測の回数
確信度の高い予測の回数
OPTinaccuracy = 予測に失敗したデータ値予測の回数
確信度の高い予測の回数
OPTaccuracy + OPTinaccuracy = 1


確信度の低い予測の影響はそれほど大きくないとして、候補
選択においては無視
整数演算、浮動小数点演算を含むあらゆる命令を対象とする。
13
データ値予測の候補選択
OPTaccuracy × OPTbenefit >> OPTinaccuracy × OPTpenalty

アウトオブオーダ実行のプロセッサでは OPTbenefit の見
積もりが困難

OPTbenefit の計算式を得る替わりに2つの方法を検討

最適化に対して固定した利得を与える単純な方法

クリティカルパスを利用する方法
14
固定した利得を与える単純な方法
OPTaccuracy >> OPTinaccuracy × OPTpenalty





利得を1に固定する。最適化が成功した回数が全体の利得と
なる。
この方法は、命令の種類やキャッシュの挙動によってレイテン
シの異なる近年のアウトオブオーダ実行のプロセッサには当て
はまらない。
例えば、依存関係の先頭となっているロード命令がキャッシュ
にミスした場合は、依存関係がなくキャッシュにヒットするロード
命令より、利得が大きい。
過去の研究から、クリティカルパスの上にある命令にデータ値
予測を利用した際に利得が大きいという結果がある。
これは、長い依存関係の鎖を半分に分割することで、2つの鎖
を並列に処理可能となり、利得が向上することを意味している。
15
クリティカルパスを利用する方法
Middle Metric: データ依存の鎖の両端からの距離の最小値
Middle Metric = min ( Distance Top, Distance Bottom)
Initial chain of dependent
instructions
lda r0 <- 40(r29)
load r3 <- 0(r0)
sub r9 <- r5, r3
sll r13 <- r9, 8
add r8 <- r6, r13
cmpeq r11 <- r8, 3
Latency Dist.
Top
1
2
1
1
1
1
1
3
4
5
6
7
Dist.
Middle
Bottom Metric
7
6
4
3
2
1
1
3
4
3
2
1
16
クリティカルパスを利用する方法
Middle Metricが最大のところをデータ値予測の候補とするこ
とで、効果的に並列性を抽出できる。
Resulting chain 1
Resulting chain 2
lda r0 <- 40(r29)
load r3 <- 0(r0)
sub r9 <- r5, r3
predict r9
sll r13 <- r9, 8
add r8 <- r6, r13
cmpeq r11 <- r8, 3
Latency: 4 cycles
Latency: 4 cycles
17
予測ミスに強い分岐命令



データ値予測が正しく予測
されているが、分岐予測が
失敗した(データ値予測を
正しくないと評価した)場合
を考える。
補償コードが実行され、正
しい値を用いて実行してい
るにもかかわらず、分岐予
測ミスによりパイプラインが
フラッシュされ、投機的な値
を用いて再実行される。
これは不必要な再実行
r3 <- predict index
r9 <- load X
r10 <- cmpeq r9, r3
beq r10, fixup
A: update index, r3
r4 <- add r3, r1
r5 <- sub r4, r8
fixup: r3 <- mov r9
br A
18
BEQIT命令の追加


BEQIT(Branch if Equal to zero Ignoring
mispredictions down the Taken Path)命令を追加する。
分岐成立と予測され、実際には不成立だった場合でも、予測
ミスからの回復をおこなわない分岐命令

正しい結果を用いて分岐予測の情報を更新する。

将来の予測では、正しく予測できる可能性がある。

わずかなデコードロジックの追加と、分岐成立で予測ミスが検
出されても回復をおこなわない制御を追加することで、比較
的、容易に実現できる。
19
評価
実験環境







整数演算と浮動小数点演算を含むSPEC95, SPEC2000の幾
つかのプログラムを利用(詳細は表1)
SimpleScalar/Alpha 3.0 ツールセット、 Alpha AXP ISA
2階層の命令とデータキャッシュを持つ4-ウェイのアウトオブ
オーダ実行プロセッサ
32エントリのリオーダバッファ、16エントリのロードストアバッ
ファ
16k gshare分岐予測により確信度を評価する。
データ値を予測するアルゴリズムには、ストライドをベースとし
たものを利用する。
2回の実行により詳細なログを取得し、最適化を施す。
20
評価に用いたマイクロアーキテクチャ (1)

4-ウェイのアウトオブオーダ実行プロセッサ

32エントリのリオーダバッファ、16エントリのロードストアバッファ

4kエントリの gshare分岐予測、ミスペナルティ6サイクル

機能ユニット


4つの整数演算ユニット
(レイテンシ:1)

2つのロードストアユニット

2つの浮動小数点加算
(レイテンシ:2)

1つの整数乗算除算
(レイテンシ:3、12)

1つの浮動小数点乗算除算
(レイテンシ:4,12)
除算を除くすべての機能ユニットは完全にパイプライン化され、毎
サイクル、1命令を投入可能
21
評価に用いたマイクロアーキテクチャ (2)

32k 2-ウェイセットアソシアティブの命令とデータキャッシュ(レイテ
ンシ1サイクル)


ブロックサイズ32バイト、ライトバック、ライトアロケート、ノンブロッキ
ング、2ポート
命令とデータで共有の 512k 2-levelキャッシュ

キャッシュヒット6サイクル、ミス60サイクルのレイテンシ

16エントリ4-ウェイのデータ用TLB

32エントリ4-ウェイの命令用TLB

PREDICT命令、UPDATE命令のためのテーブルは十分大きく、
それぞれの命令が異なるエントリの競合が発生しないと仮定

最も効率的な構成において、利用したのは22~136エントリ
22
適用範囲(coverage)と正確さ(accuracy)



Accuracy (%)

適用範囲とは、確信度が高いと評
価された命令の割合
正確さとは、予測が正しかった命
令の割合
閾値が用いられ、ある命令の正確
さが閾値を超えた場合にデータ値
予測の候補とする。
閾値を上げることで、予測が当た
りやすい命令のみが候補となり、
正確さが向上するが、一方で、適
用範囲が減少する。
逆に、閾値を下げることで、適用範
囲を広げることができるが、正確さ
が低下する。
0
0
Threshold (%)
100
100
Coverage (%)

100
0
0
Threshold (%)
100
23
適用範囲と正確さの評価結果

原論文の図3を参照

図3の上から2番目のグラフはデータがおかしいので注意。




分岐命令を用いた確信度評価を利用したデータ値予測が、
適用範囲と正確さ共に良い結果を出した。
閾値を0に設定しても、確信度評価を利用した場合の正確さ
は高く、crafty の87.6%, go の79.8%を除く6つのプログラ
ムで94%を超えた。
確信度を用いないデータ値予測では、閾値が増加するにつ
れて正確さが向上するが、同時に、適用範囲が減少する。
これらの結果は次の考察より予測できる。

確信度評価を利用することで、全体を通じて高い正確さをもつわけで
はないが、予測しやすいパターンをもつ候補が追加される。
24
確信度評価を利用したデータ値予測

原論文の図4を参照

データ値予測を用いないモデルをベースラインとする。

データ値予測を用いるモデル(PREDICT,UPDATEを利用するコンパイラ
ベースのもの)

確信度評価を用いたデータ値予測を用いるモデル(提案手法)

確信度評価を利用しない場合の性能向上は平均で3.3%


Reference input を利用して、確信度評価を用いたデータ値予測による
性能向上は平均で15.2%、最大は m88ksimの38.1%
分岐予測を用いた確信度評価は利用する分岐予測の影響を受ける。
gshare から bimodal, hybrid に変更して評価をおこなった。

Bimodal に変更することで性能が低下、利得は 5.4%

Hybrid に変更することで性能が向上、利得は2.9%
25
ソフトウェアによるデータ値予測


PREDICT命令、UPDATE命
令を利用せず、すべてソフト
ウェアのみでデータ値予測
をおこなったばあいの性能。
この場合にはISAに変更を
加える必要はない。
r3 <- predict index
r9 <- load X
r10 <- cmpeq r9, r3
beq r10, fixup
A: update index, r3
r4 <- add r3, r1
r5 <- sub r4, r8
fixup: r3 <- mov r9
br A
26
ソフトウェアによるデータ値予測の評価結果

原論文の図5を参照

ソフトウェアのみのデータ値予測では、フリーなレジスタを確保で
きないという理由から、compress, crafty, tomcatv では最適化を
全く利用できない(性能向上 0%)。

残った5つのプログラムは art の1%から mcf の13%までの性能
向上、平均では4.6%の性能向上と低い。


状態をメモリに格納するためのオーバヘッドが大きい。

レジスタの不足により、最適化を利用できる適用範囲が小さくなる。
より洗練されたレジスタ割付手法を利用することでソフトウェアに
よるデータ値予測の性能が向上する可能性があるが、どの変数
をレジスタに割りあてるかという難しい問題が生じる。
27
データ値予測の候補選択

適切な候補を選択することで、高い性能向上が得られる。

一つの基本ブロックで、1回しかデータ値予測を使わないと
いう設定で検討(この設定は、今後の検討課題としている)。

3つの異なる選択基準

固定した利得

Middle metric

固定した利得とmiddle metricから選択
28
データ値予測の候補選択の評価結果






原論文の図6、表2を参照
それぞれの選択基準で最も性能の高かった候補集合の結果を図
6に示す。
多くのベンチマークで、選択基準による大きさ差は見られなかった。
Crafty, go, tomcatv では middle metric を利用することで性能が
低下した。これは、データ依存関係の鎖の長さが短いことが原因で
はないか。
Middle metric を利用した際に高い性能を示した m88skim,
equakeでは、長い鎖を多くみることができる。
それ以外では、大きな差がないが、これらでは、同様の候補が選
択されているためである。
29
ハードウェア量の見積もり





原論文の表3を参照
最も高い性能を達成した最適化において、データ値予測の
候補となった命令の数を表3に示す。
最も多くの命令が最適化された mcf の場合の命令数が
136であり、予測ハードウェアのエントリに8バイト必要とす
ると、データ値予測のテーブルサイズは約1KBとなる。
ハードウェアのみで実装した場合の16KB~32KBと比較し
て、1KBは非常に小さい。
ハードウェアでは平等にデータ値予測を利用する必要があ
るが、コンパイラが利得の大きい場所に選択的に最適化を
おこなうことでハードウェアの削減が可能となった。
30
予測ミスに強い分岐命令の効果

原論文の図7を参照

BEQIT命令の追加による性能への影響を図7に示す。

BEQIT命令を利用しない場合と比較して、利用することで
Compress では13%の性能向上を確認した。

M88ksim, tomcatv では、BEQIT命令が生きるような場合が
少ないので利得も小さくなっている。
31
関連研究

Lipasti[ASPLOS,1996]により、データ値予測の可能性が指摘された。

Calder[ISCA,1999]により、確信度評価の概念が値予測に導入された。

Fu[ASPLOS,1998]が初めてコンパイラによるデータ値予測を提案した。





完全にソフトウェアのみの実装

PREDICT, UPDATE命令を用いた実装

CHECKPRED命令を用いた実装
Nakra[ISCA,1999] は、VLIW計算機におけるデータ値予測の可能性を議
論した。
Marcuello[MICRO,1999] は、マルチスレッドアーキテクチャにおけるデー
タ値予測の可能性を議論した。
Lebeck[MICRO,1998]多くのロード命令は、データ値予測によりその実行
を早めることにより、性能を低下することなく実行できる。
Zilles[IACA,2000] backward sliceを利用した手法にデータ値予測を利用。
32
結論 (1)

分岐予測をデータ値予測の確信度評価として利用することで、
ハードウェアコストを抑えつつ、効率的な性能向上が得られ
ることを示した。

データ値予測を利用しない場合をベースラインとして、確信
度評価を利用した場合の性能向上 15.2%、確信度評価を
利用しない場合の性能向上 3.3% を達成できた。

完全にソフトウェアのみで実装した場合の性能向上は4.6%
とそれほど高くない。これは最適化で必要となるフリーなレジ
スタの不足が原因の一つとなっている。
33
結論 (2)





データ値予測を利用する候補の選択手法は、プログラムにおける
データ依存関係の鎖の長さや、鎖の数によって変化する。
鎖の数が少なく、鎖の長さが短い場合には、固定した利得の利用
により良い結果がえられた。
鎖の数が多く、鎖が長い場合には、クリティカルパスの利用により
良い結果が得られた。
データ値予測の候補となる命令が最も多かったプログラムは mcf
で命令数は136だった。この場合においても、1KBのテーブルを用
意することで、データ値予測を実現できる。
実装コストの低い、予測ミスに強い分岐命令(BEQIT命令)を導入
することで分岐ミスのペナルティを削減でき、compressの13%の
速度向上を含む、多くのベンチマークにおける性能向上を確認し
た。
34
今後の仕事

データ値予測の候補として最適な集合を得る。

データ値予測を利用する命令間の関係を検討する。

命令間が近すぎると、データ依存関係の鎖を分断しすぎることになり
オーバヘッドが大きくなってしまう。


命令間が大きすぎると、十分な性能向上を得ることができない。
データ値予測以外の投機手法に、分岐予測を利用した確信度評
価の手法が利用できる可能性がある。

分岐の結果に関係なく、プログラムとして正しいパスを選択するよ
うな場合には、分岐予測ミスに強い分岐命令(BEQIT命令)が利用
できる可能性がある。
35
ダウンロード

データ値予測を用いたプロセッサ性能の向上手法