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

８．２．３　　データ値予測を用いたプロセッサ性能の向上手法 出典 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％の性能向上を達成。 データ値予測による命令レベル並列性の向上 r3 - load X r4 - add r3, r1 r5 - sub r4, r8 背景 (1) データ依存関係と、制御依存関係により生じる制約が高性能プロセッサの設計を困難にする。 過去の研究から、多くの命令の計算結果は予測可能であることが示され、データ値予測の提案へとつながってきた。 データ値予測は、命令の計算結果を予測することで真のデータ依存関係を切断し、データ依存関係のある命令を並列に実行することで性能を稼ぐ。 Last-value, stride, context-base, hybrid の予測手法が提案されてきた。 これまで、多くの研究はハードウェアによるデータ値予測の実現を中心に議論してきた。 ハードウェアでの単純な実装では、データ値予測に失敗した場合に数十サイクルのペナルティが課せられるため、高い精度で予測が当たる命令のみがデータ値予測の対象となっていた。 データ値予測の利用範囲を広げるために、確信度評価の導入が議論されてきた。 確信度評価とはデータ値予測がヒットかミスかを評価し、ヒットすると評価された場合のみデータ値予測を利用することで、予測ミスを削減する。 背景 (2) ハードウェアによるデータ値予測の実装は高い性能をもたらすが、ハードウェアコストは非常に高い（キャッシュと同等かそれ以上）。 プロファイルを利用して、データ値予測の候補を選択するコンパイラ技術が議論されてきたが、これまで、ソフトウェアベースのものは高い性能を達成できなかった。 その理由の一つが、ソフトウェアベースのものは確信度評価をとりいれていなかったことにある。 もう一つの理由が、命令数の増加をおさえるために、複雑な予測アルゴリズムが利用できない点にある。 これを解決するために命令セットに特別な命令を追加して、予測値の生成はハードウェアに任せる解決策が提案されているが、この場合にも、候補選択や予測ミスからの回復はコンパイラの仕事となっている。 目的 ハードウェア量を抑えながら、データ依存関係を緩和し、命令レベル並列性を抽出するデータ値予測(value prediction)の実現を目指す。 コンパイラによる次の３つの最適化手法を提案する。 分岐予測を利用したデータ値予測の確信度評価 確信度評価を利用することでデータ値予測の正確さを向上 クリティカルパスを利用するデータ値予測の候補選択 すべての命令をデータ値予測の候補とすると、オーバヘッドがおおきくなるので、効果のありそうな命令を静的に選択する。 予測ミスに強い分岐命令（BEQIT命令）の追加 データ値予測の最適化手法 分岐予測を利用したデータ値予測の確信度評価 既存の分岐予測を確信度評価の機構として利用 高い精度を保ちつつ、データ値予測を利用する／しないの動的な選択が可能 クリティカルパスを利用するデータ値予測の候補選択 最適化を施す命令を、クリティカルパスの位置情報により決定 コンパイラによりデータ値予測を利用する命令を静的に選択 予測ミスに強い分岐命令（BEQIT命令）の追加 プログラムの正しさを保証しながら、必要のない分岐予測ミスを排除する分岐命令を追加 分岐予測を利用したデータ値予測の確信度評価 データ値予測による利得を得るには、確信度評価が必要 過去の履歴を保存しておく必要があるためソフトウェアで実装するのは困難 この複雑さを回避するために、データ値予測の確信度評価として、分岐予測を利用することを提案 第一