プログラムの実行挙動と分岐予測性能を表現するエントロピーの提案

IPSJ Web Site 26 References

Bibliographic Information

Other Title
  • プログラム ノ ジッコウ キョドウ ト ブンキ ヨソク セイノウ オ ヒョウゲンスル エントロピー ノ テイアン
  • Proposal of Entropies for Representing Program Behavior and Branch Prediction Performance

Search this article

Abstract

現在のプロセッサ・アーキテクチャにおいて予測器は重要な役割を担っており，分岐予測器を中心になおさまざまな予測方式の試みがなされている．分岐予測器の性能は，分岐履歴などプログラムの実行挙動の性質に大きく影響される．この性質を定量的に表現する指標を得られれば，それがすなわち予測器の性能の基準となるはずである．本論文では，情報エントロピーの考え方を導入することにより，分岐履歴に基づくプログラムの実行挙動と，予測器の構成に基づく分岐予測挙動を，それぞれ表現する手法を議論する．そして前者の議論からプログラムの分岐履歴をもとにした分岐履歴エントロピーを提案する．このエントロピーは，その値をもとに期待可能な予測性能を理論的に求めることができることから，予測方式に依存しない予測性能の指標となりうる．また後者の議論から，表の形態をとる分岐予測器において表の各エントリの参照頻度の偏りを表す表参照エントロピーと，各エントリに分配される情報量の平均を表す表要素エントロピーを提案する．この2つのエントロピーの組により分岐予測器の特徴を表すことが可能であり，さらに，表参照エントロピーから予測器内の資源の使用効率を推測することができ，表要素エントロピーから予測機能に物理的な制約がない場合に期待しうる最大の予測性能を求めることができる．

Predictors are inevitable components in the state-of-the-art microprocessors and branch predictors are actively discussed from many aspects. Performance of a branch predictor largely depends on program behavior, however, we have no effective metric to represent the nature of program behavior. In this paper, we introduce an information entropy idea on branch predictors. We first discuss information of a branch result as an index of program behavior and propose Branch History Entropy, which induces theoretical expected hit ratio and thus becomes an index of prediction performance. We, then, discuss characteristics of table-formatted branch predictors and propose two entropies: Table Reference Entropy and Table Entry Entropy. The former represents effective amount of resources in a predictor and the latter shows maximum expected prediction performance.

Journal

References(26)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top