８．２．３データ値予測を用いたプロセッサ性能の向上手法出典 Compiler Controlled Value Prediction using Branch Predictor Based Confidence”, Eric Larson and Todd Austin, 33rd International Symposium on Microarchitecture, December 2000 概要       命令レベル並列性を抽出し、高性能プロセッサの実現を目指す。ハードウェア量を抑えながらデータ値予測の利点を生かすため、コンパイラによる最適化手法を議論する。３つの最適化手法を提案する。  分岐予測を利用したデータ値予測の確信度評価  クリティカルパスを利用するデータ値予測の候補選択  予測ミスに強い分岐命令（BEQIT命令）の追加 SPEC95, SPEC2000 の８つのプログラムを負荷とするシミュレーションにより有効性を検証する。ソフトウェアのみの最適化により4.6％の性能向上を達成。ハードウェアのみの実装による32KBと比較して、１KBという非常に小さい予測テーブルの追加のみで、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)の実現を目指す。  コンパイラによる次の３つの最適化手法を提案する。  分岐予測を利用したデータ値予測の確信度評価   確信度評価を利用することでデータ値予測の正確さを向上クリティカルパスを利用するデータ値予測の候補選択  すべての命令をデータ値予測の候補とすると、オーバヘッドがおおきくなるので、効果のありそうな命令を静的に選択する。  予測ミスに強い分岐命令（BEQIT命令）の追加 6 データ値予測の最適化手法本章では、コンパイラが制御する次の３つの最適化手法の詳細を検討する。  分岐予測を利用したデータ値予測の確信度評価     既存の分岐予測を確信度評価の機構として利用高い精度を保ちつつ、データ値予測を利用する／しないの動的な選択が可能クリティカルパスを利用するデータ値予測の候補選択  最適化を施す命令を、クリティカルパスの位置情報により決定  コンパイラによりデータ値予測を利用する命令を静的に選択予測ミスに強い分岐命令（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 の計算式を得る替わりに２つの方法を検討  最適化に対して固定した利得を与える単純な方法  クリティカルパスを利用する方法 14 固定した利得を与える単純な方法 OPTaccuracy >> OPTinaccuracy × OPTpenalty      利得を１に固定する。最適化が成功した回数が全体の利得となる。この方法は、命令の種類やキャッシュの挙動によってレイテンシの異なる近年のアウトオブオーダ実行のプロセッサには当てはまらない。例えば、依存関係の先頭となっているロード命令がキャッシュにミスした場合は、依存関係がなくキャッシュにヒットするロード命令より、利得が大きい。過去の研究から、クリティカルパスの上にある命令にデータ値予測を利用した際に利得が大きいという結果がある。これは、長い依存関係の鎖を半分に分割することで、２つの鎖を並列に処理可能となり、利得が向上することを意味している。 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の幾つかのプログラムを利用（詳細は表１） SimpleScalar/Alpha 3.0 ツールセット、 Alpha AXP ISA ２階層の命令とデータキャッシュを持つ4-ウェイのアウトオブオーダ実行プロセッサ３２エントリのリオーダバッファ、１６エントリのロードストアバッファ 16k gshare分岐予測により確信度を評価する。データ値を予測するアルゴリズムには、ストライドをベースとしたものを利用する。２回の実行により詳細なログを取得し、最適化を施す。 20 評価に用いたマイクロアーキテクチャ (1)  4-ウェイのアウトオブオーダ実行プロセッサ  ３２エントリのリオーダバッファ、１６エントリのロードストアバッファ  4kエントリの gshare分岐予測、ミスペナルティ６サイクル  機能ユニット   ４つの整数演算ユニット（レイテンシ：１）  ２つのロードストアユニット  ２つの浮動小数点加算（レイテンシ：２）  １つの整数乗算除算（レイテンシ：３、１２）  １つの浮動小数点乗算除算（レイテンシ：４，１２）除算を除くすべての機能ユニットは完全にパイプライン化され、毎サイクル、１命令を投入可能 21 評価に用いたマイクロアーキテクチャ (2)  32k 2-ウェイセットアソシアティブの命令とデータキャッシュ（レイテンシ１サイクル）   ブロックサイズ32バイト、ライトバック、ライトアロケート、ノンブロッキング、２ポート命令とデータで共有の 512k 2-levelキャッシュ  キャッシュヒット６サイクル、ミス６０サイクルのレイテンシ  16エントリ4-ウェイのデータ用TLB  32エントリ4-ウェイの命令用TLB  PREDICT命令、UPDATE命令のためのテーブルは十分大きく、それぞれの命令が異なるエントリの競合が発生しないと仮定  最も効率的な構成において、利用したのは２２～１３６エントリ 22 適用範囲(coverage)と正確さ(accuracy)    Accuracy (%)  適用範囲とは、確信度が高いと評価された命令の割合正確さとは、予測が正しかった命令の割合閾値が用いられ、ある命令の正確さが閾値を超えた場合にデータ値予測の候補とする。閾値を上げることで、予測が当たりやすい命令のみが候補となり、正確さが向上するが、一方で、適用範囲が減少する。逆に、閾値を下げることで、適用範囲を広げることができるが、正確さが低下する。 0 0 Threshold (%) 100 100 Coverage (%)  100 0 0 Threshold (%) 100 23 適用範囲と正確さの評価結果  原論文の図３を参照  図３の上から２番目のグラフはデータがおかしいので注意。     分岐命令を用いた確信度評価を利用したデータ値予測が、適用範囲と正確さ共に良い結果を出した。閾値を０に設定しても、確信度評価を利用した場合の正確さは高く、crafty の87.6%, go の79.8%を除く６つのプログラムで94%を超えた。確信度を用いないデータ値予測では、閾値が増加するにつれて正確さが向上するが、同時に、適用範囲が減少する。これらの結果は次の考察より予測できる。  確信度評価を利用することで、全体を通じて高い正確さをもつわけではないが、予測しやすいパターンをもつ候補が追加される。 24 確信度評価を利用したデータ値予測  原論文の図４を参照  データ値予測を用いないモデルをベースラインとする。  データ値予測を用いるモデル（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 ソフトウェアによるデータ値予測の評価結果  原論文の図５を参照  ソフトウェアのみのデータ値予測では、フリーなレジスタを確保できないという理由から、compress, crafty, tomcatv では最適化を全く利用できない（性能向上 0%)。  残った５つのプログラムは art の1%から mcf の13%までの性能向上、平均では4.6%の性能向上と低い。   状態をメモリに格納するためのオーバヘッドが大きい。  レジスタの不足により、最適化を利用できる適用範囲が小さくなる。より洗練されたレジスタ割付手法を利用することでソフトウェアによるデータ値予測の性能が向上する可能性があるが、どの変数をレジスタに割りあてるかという難しい問題が生じる。 27 データ値予測の候補選択  適切な候補を選択することで、高い性能向上が得られる。  一つの基本ブロックで、１回しかデータ値予測を使わないという設定で検討（この設定は、今後の検討課題としている）。  ３つの異なる選択基準  固定した利得  Middle metric  固定した利得とmiddle metricから選択 28 データ値予測の候補選択の評価結果       原論文の図６、表２を参照それぞれの選択基準で最も性能の高かった候補集合の結果を図６に示す。多くのベンチマークで、選択基準による大きさ差は見られなかった。 Crafty, go, tomcatv では middle metric を利用することで性能が低下した。これは、データ依存関係の鎖の長さが短いことが原因ではないか。 Middle metric を利用した際に高い性能を示した m88skim, equakeでは、長い鎖を多くみることができる。それ以外では、大きな差がないが、これらでは、同様の候補が選択されているためである。 29 ハードウェア量の見積もり      原論文の表３を参照最も高い性能を達成した最適化において、データ値予測の候補となった命令の数を表３に示す。最も多くの命令が最適化された mcf の場合の命令数が 136であり、予測ハードウェアのエントリに8バイト必要とすると、データ値予測のテーブルサイズは約1KBとなる。ハードウェアのみで実装した場合の16KB～32KBと比較して、1KBは非常に小さい。ハードウェアでは平等にデータ値予測を利用する必要があるが、コンパイラが利得の大きい場所に選択的に最適化をおこなうことでハードウェアの削減が可能となった。 30 予測ミスに強い分岐命令の効果  原論文の図７を参照  BEQIT命令の追加による性能への影響を図７に示す。  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