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

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

３．３．１　背景

　データ依存関係により生じる制約は、高性能プロセッサの設計を困難にする要因の一つとなっている。データ依存関係による制約の緩和を目指して研究が進められ、多くの命令の演算結果は予測可能であることが明らかになってきた。この成果は、命令の演算結果を予測することで真のデータ依存関係を切断し、予測されたデータ値を用いて投機的に処理を進めることで命令レベルの並列性を抽出するデータ値予測の提案につながっている。データ値予測に関する従来の研究では、ハードウェアによる実装を前提として、データ値予測による性能向上の可能性を検討しているものが多い。ハードウェアによる実装には高い性能を期待できる反面、必要となるハードウェアコストがデータキャッシュ程度に大きくなり現実的ではないという指摘がある。

本節で紹介する文献[1]は、１５％という高い性能向上を保ちつつハードウェア量を抑えるために、データ値予測で必要となる多くの機能をソフトウェアにより実現することを検討している。これを可能とするアイデアは、データ値予測の候補となる命令の絞込みによるハードウェアテーブルのエントリ数の削減と、既にプロセッサに組み込まれている分岐予測機構を利用してデータ値予測の確信度を評価することである。

３．３．２　調査内容

データ値予測を利用して性能向上を図るためには、３２ビットあるいは６４ビットの演算結果を正確に予測する技術に加えて、データ値予測の正しさを見積もる評価の精度が重要になる。後者の評価は、データ値予測の確信度が高いか低いかを求める１ビットの評価でありデータ値予測の確信度評価と呼ばれる。この精度を向上させることでデータ値予測のミス率を抑えることができる。従来、ソフトウェア実装によるデータ値予測により高い性能を達成できなかった理由の一つに、確信度評価を取り入れていなかったという理由がある。文献[1]では、コンパイラが制御するデータ値予測として幾つかの最適化手法を検討している。その中から、分岐予測を利用した確信度評価の提案と、最適化候補の選択手法を紹介する。

(1) 分岐予測を利用したデータ値予測の確信度評価の提案

プロセッサに組み込まれている分岐予測を確信度評価の機構として利用する手法を提案する。これにより、高い精度を保ちつつ、データ値予測をおこなうかどうかの動的な選択が可能となる。分岐予測を利用する第一の利点は、確信度を評価するための情報と予測ミスからの回復の手段が、すでにプロセッサに組み込まれていることである。加えて、ハードウェアで実装された強力な分岐予測のアルゴリズムにより、ソフトウェアの実装より高い評価精度を達成できる可能性がある。

分岐予測を利用するために、データ値予測の正解を分岐の不成立に、データ値予測の間違いを分岐の成立に対応付ける。図３．３．１に示す具体例を用いて最適化手法を説明する。図３．３．１の例では、ロード命令に最適化（データ値予測）が施されるとする。ロード命令の結果は、この領域で利用されていないレジスタr9 に格納される。予測されたデータ値はオリジナルなレジスタr3 に格納される。ロード命令の後に比較と分岐命令が加えられ、これによりデータ値予測の正当性を保証する。データ値予測にミスした場合には、分岐の成立により補償コードを実行し、適切なデータ値がレジスタr3 に格納される。データ値予測に成功した場合には補償コードが実行されることはなく、予測されたデータ値を利用して処理を進める。

図３．３．１　分岐予測を利用する確信度評価の例

図３．３．１の最適化後のコードでは、分岐命令がデータ値予測の確信度評価になっていることに注意してほしい。もし、分岐予測が分岐不成立と予測したとすると、データ値予測が正しいという高い確信度を与えたことになる。この場合には、データ依存関係を持つ命令は予測された値を用いてただちに実行される。もし、分岐予測が分岐成立と予測したとすると、データ値予測が正しいという確信度を低く評価したことになり、最適化されていないパスを実行する。ただし、データ値予測の成功と不成功に関係なく、分岐予測に失敗した場合には、分岐予測ミスのコストがペナルティとして課せられるという欠点がある。

図３．３．１の例では、predict命令と update命令を利用して、予測値の生成と、テーブルの更新をおこなう。これらの２つの命令は拡張命令として命令セットに追加される。Predict命令とupdate命令には、予測値を生成するハードウェアテーブルのインデックスを示すフィールドが存在する。命令毎に異なったインデックスを用いることで利用するテーブルを区別し、命令間の干渉を防ぐ。それぞれのpredict命令には対応するupdate命令が存在し、このupdate命令により正しい演算結果が予測機構に伝えられ、予測値を生成するための情報を更新する。

（２）最適化候補の選択手法の提案

データ値予測を利用するかどうかの最終決定は確信度評価を利用して動的に決める。一方で、データ値予測の候補として図３．３．１に示した最適化を施す命令を選択する手法が必要となる。ある命令に最適化を利用するかを決める場合に、理想的には、値予測が正しかった回数とそれによる利得の積（当該命令の最適化による利得）と、データ値予測に失敗した回数とそれによるペナルティの積（当該命令の最適化による損失）を比較して、利得が損失より非常に大きくなる場合に限り、図３．３．１に示す最適化を利用すればよい。

トレースデータを用いることで予測成功と失敗の回数を見積もることができる。しかし、近年のアウトオブオーダ実行のプロセッサでは、予測成功時の利得を計算することは困難である。このため、予測成功時の利得の見積もり手法が必要となる。一つの単純な方法は固定した利得を用いる手法である。別の手法として、クリティカルパスから利得を計算する方法を提案している。この例を図３．３．２に示す。データ依存関係で繋がれた複数命令からなる鎖（データフローグラフ）があった場合に、データ値予測により鎖を半分に切断することで最も高い利得が得られるという考察から、鎖の両端からの距離の最小値（図３．３．２のMiddle Metric）を利得として利用する手法を提案している。

図３．３．２　クリティカルパスを利用した利得 Middle Metricの計算例

（３）評価結果

　２階層の命令とデータキャッシュを持つ４ウェイのアウトオブオーダ実行プロセッサのモデルを用いて提案手法を評価する。SimpleScalar/Alpha3.0ツールセットを用いたクロックレベルのソフトウェアシミュレーションにより提案手法を評価する。負荷としで、ＳＰＥＣ９５とＳＰＥＣ２０００の幾つかのプログラムを利用する。一つの基本ブロックで１命令しか最適化できないという制約を設ける。

図３．３．３　確信度評価による性能向上率の変化

データ値予測を利用しないプロセッサ性能をベースラインとして、確信度評価を用いた場合の性能向上の測定結果を図３．３．３に示す。Predict命令とupdate命令を利用するデータ値予測を利用し、データ値を生成にはストライドベースのアルゴリズムを利用した。図３．３．３の結果に示すように、確信度評価を利用しない場合の性能向上は平均で３．３％だが、確信度評価を用いたデータ値予測による性能向上の平均は１５．２％で、ｍ８８ｋｓｉｍにおいては最大の３８．１％という性能向上を達成した。

最も多くの命令が最適化されたmcfの場合でも最適化された命令は１３６個であり、このときのデータ値予測のテーブルサイズは約１KBとなる。ハードウェアのみで実装した場合の１６KB～３２KBという容量と比較して１KBは非常に小さい。ハードウェアによるデータ値予測では、すべての命令に平等に最適化の機会を与えるために多くのハードウェアが必要となるが、コンパイラが利得の大きい場所を選択することで、ハードウェアの削減が可能となっている。

図３．３．４　利得の計算手法による性能向上率

予測成功時の利得を、固定値、Middle Metric, 固定値とMiddle Metric の利用という３つの場合に変更した場合の性能向上率を図３．３．４に示す。この結果からは、多くのベンチマークで利得の計算手法による大きな差は見られない。

（４）結論

　分岐予測をデータ値予測の確信度評価として利用することで、ハードウェアコストを抑えつつ、１５％という高い性能向上が得られることを明らかにした。この時、データ値予測の候補となる命令が最も多かったプログラムはｍｃｆで命令数は１３６だった。この場合においても、１ＫＢという小さいテーブルによりデータ値予測を実現できる。

　今後の課題として次の検討が必要である。第一に、評価では１つの基本ブロックでは最大で１つの命令しかデータ値予測の候補としないという制約を用いたが、この条件を変化させデータ値予測の候補としての最適な集合を検討する必要がある。第二に、データ値予測を利用する命令間が近すぎると、データ依存関係の鎖を分断しすぎることになり、オーバヘッドが大きくなってしまう。一方、命令間が大きすぎると、十分な性能向上を得ることができない。データ値予測を利用する命令間の関係を検討する必要がある。

３．３．３　当該技術の展望

次世代プロセッサとしてVILWプロセッサ、オンチップマルチプロセッサ、マルチスレッドプロセッサ等が注目を集めている。しかし、汎用の高性能プロセッサの市場に目を移すと、依然としてスーパースカラプロセッサがそのシェアを独占している。

従来から提案されているデータ値予測により、１０％から２０％程度の性能向上が得られることが明らかになってきたが、ハードウェアの複雑化に対する懸念が強かった。本文献では、コンパイラの助けを借りることで追加するハードウェアを大幅に削減しつつ、平均１５％という高い性能向上が可能となることを明らかにした。拡張命令の追加が必要性や、コンパイラが利用するトレースの収集方法などに課題は残るが、データ値予測の実用化まであと一歩のところまできているといってよい。

参考文献

[1] Eric Larson, et.al., “Compiler Controlled Value Prediction using Branch Predictor Based Confidence”, 33^rd International Symposium on Microarchitecture, December 2000.