値予測における値履歴テーブルエントリ数の削減
飯 塚
坂 井

大 介†
修 一††

角
田

田 忠
中 英

信††
彦††

値予測は真の依存関係を解消することで並列度を抽出する手法である。性能向上率を向上させるた
めに予測精度を高めた種々の予測方式が提案されているが、予測に必要なハードウェア量が膨大なため実装するのが困難となっている。特に予測履歴テーブルは大きな資源を必要とするため、タグや予測値のビット数、エントリ数を制限してハードウェア量を削減する手法が近年いくつか提案されている。本稿では静的に命令を分類し、予測候補から除外する命令を選択することですることで総予測命令数を削減し、値予測履歴テーブルのエントリ数を削減した場合の性能低下を抑制する方式を提案する。その結果、同じエントリ数の場合に性能向上率が若干向上することを確認した。

Decreasing Value History Table Entry on Value Prediction
Daisuke Iizuka, † Tadanobu Tsunoda,†† Shuichi Sakai††and Hidehiko Tanaka††
Value prediction is a technique to resolve true dependency and exploit more parallelism.
Various value prediction mechanism have been proposed to achieve high prediction accuracy.
However, those sophisticated mechanisms often require a large amount of hardware, especially for the Value History Table(VHT). Recently, several researches have been done on thetechniques to reduce the VHT size by cutting the length of tag or prediction values, or bylimiting the number of table entries. This paper proposes a technique to reduce the VHT
entries without loosing performance based on static analysis. We propose to use VHT only
for instructions that have been selected by the compiler. Evaluation results show that, using
our technique, a higher performance can be achieved with the VHT of the same number of
entries.

る性能向上を得るための条件の一つとなる。値予測の精度を向上させるための手法として、ハイブリッド型
値予測機構 10) やコンテキスト型値予測機構 6) が提案されている。これらの予測機構を用いれば高精度で予測を行うことができるが、予測機構を実装するためのハードウェア量も膨大なものになる。また、値予測でヒットする命令数を増加させるためには、予測値を格納しておく値履歴テーブル (Value History Table,
VHT) のエントリ数を大きくしておく必要がある。しかし、VHT を大きくすると大きなハードウェアコストが必要となり、また高クロックで動作させることも難しくなる。本稿では、値予測の実装可能性を高める
ために、VHT のエントリ数を削減した際に生じる性能低下を、予め静的に予測命令を選択しておくことで抑える手法を提案する。本稿の構成は以下の通りである。2 節で関連研究を述べる。3 節で評価方法を説明
し、4 節で提案手法を紹介する。5 節で評価を行い、最後に 6 節でまとめる。

1. は じ め に
アウトオブオーダ実行を行なうスーパースカラプロ
セッサは、プログラムから命令レベル並列性を動的に抽出することで、実行速度の向上を図っている。しかし、プログラム中には真の依存関係が存在するため、従来の手法では並列度の抽出には限界がある。近年、
この真の依存関係を解決するためのデータ投機手法として、命令が生成する値を予測する値予測が考案されている 5) 。値予測では予測した結果が正しければ速度向上を得ることができる。しかし、予測ミスを起こした場合は誤った予測結果を使用した全ての命令が生成した値を破棄し、予測開始時点から再実行する必要がある。従って、予測ミス率を下げることが値予測によ† 東京大学大学院 工学系研究科
Graduate School of Engineering, The University ofTokyo†† 東京大学大学院 情報理工学系研究科
Graduate School of Information Science and Technology, The University of Tokyo1

表1

2. 関 連 研 究
本節では、値予測のハードウェア量を削減する方式
や、高クロックで動作する値予測機構、VHT のポー
ト数が少ない時の性能向上方法等を提案している関連研究について述べる 2) 7)15) 。文献 12) では、VHT のタグビット幅を削減する手法を、文献 13) では、予測値を 0/1 に限定する手法を提案している。VHT を用
いずに値予測を行う方式も提案されている 4) 。文献 1)
では、Prediction Value Cache(PVC) を用意し、トレースキャッシュ上の命令をフェッチする時と同時にPVC に格納されている値をフェッチし、その値を使用して値予測を行う。これにより、高クロックかつ低消費電力で値予測が実現できるとしている。文献 3)
では、既存の分岐予測機構を値予測の確信度の評価の機構として利用し、予測値を取り出す命令と VHT を更新する命令を追加し、更にクリティカルパスを考慮
して予測命令を選択する方式を提案している。その結果、最も最適化した場合は静的に最大 136 命令だけを選択的に予測すれば十分な利得が得られるとしている。文献 11) では静的に、あるいはプロファイルを用いて、LastValue/Stride/Context のそれぞれの予測機構で予測可能な命令と予測しない命令とに分類する
方式を提案している。これにより、VHT のポート数が少ない場合には、動的に予測を行う場合よりも性能向上率が高くなることを示している。

ベンチマークの詳細

ベンチマーク

入力パラメータ

総実行命令数compress
gcc
go
ijpeg
li
m88ksimperl
vortex

30000 q 2131
genrecog.i
99
specmun.ppm
train.lsp
dcrand.lit
scrabbl.in.small
persons.250

127M
142M
143M
127M
217M
147M
129M
120M

を用いた。条件分岐の予測には 4k エントリ 2 レベル適応型の gshare 予測器を使用した。値予測機構としては LastValue 予測のみを用いた。その他の予測機構
は LastValue 予測機構よりも複雑で実装可能性が低
く、かつ高精度で予測される命令数が LastValue よりも少ないために本研究では使用しない。ハードウェア
量削減のため、VHT の各エントリにタグは使用しない。各エントリに 4 ビットの飽和カウンタを設け、最大値になった時にのみ予測を行う。前回と同じ値が生成された時はカウンタを 1 増加させ、違う値が生成された場合はカウンタをリセットする。値予測ミスが発生した際には、分岐予測ミス同様にパイプラインをフラッシュし、当該命令の次の命令から再実行する方式をとった。
3.2 評 価 環 境
評価には、トレースベースのシミュレータを使用した。ベンチマークは SPECint95 を用いた。ベンチマー
クは Alpha のコードを出力する GNU GCC(バージョン 2.95.2) に、最適化オプション-O3 を付けてコンパ
イルし、ライブラリを静的リンクしたものを使用した。
表 1 にあるように、ベンチマークは 100M〜200M 命
令程度で終了するように実行時の入力パラメータを調整してある。

3. 評 価 方 法
本節では評価方法について説明する。4 節で述べる
手法は本節で述べる評価方法の下で行っている。
3.1 プロセッサモデル
評価に用いるプロセッサモデルとして、リオーダバッ
ファエントリが 64 のスーパースカラプロセッサを用いた。命令セットは Compaq Alpha と互換である。パ
イプラインは 10 段である。命令フェッチ幅とデコード
幅、リネーム幅、命令発行幅は 4 である。機能ユニッ
トは、ロードストア以外の全命令が実行可能なものが4 つ、ロードストアユニットが 2 つある。ロード命令
を除く全命令の実行レイテンシは 1 サイクルである。
ロード命令はアドレス計算に 1 サイクル、データキャッシュアクセスに 2 サイクル必要とする。キャッシュミ
ス時には 6 サイクルを必要とする。データキャッシュは容量 64kB、ブロックサイズ 64B、4 ウェイセットア
ソシアティブである。先行するストア命令が完了しな
ければ後続するメモリアクセス命令は実行できない。
命令キャッシュは容量 64kB、ブロックサイズ 16B、2
ウェイセットアソシアティブである。ミスレイテンシ
は 6 である。2 次キャッシュはデータと命令で共有で、容量は無限大とした。分岐先アドレス予測には 1k エ
ントリ 2 ウェイセットアソシアティブの分岐バッファ

4. 値履歴テーブルエントリ数の削減
本節では静的に命令の種類やデータフローを解析し、予測対象命令を限定することで容量性ミスが生じる可能性を低下させ、VHT のエントリ数を削減した際に生じる性能低下を抑える方式を提案する。
4.1 高ヒット命令の分類
プログラムに含まれる命令を以下に示すクラスに分類する。クラス分けは以下に述べる順に適用され、一度特定のクラスにクラス分けされた命令は他のクラスに所属することはないものとする。
BRONLY 予測値が条件分岐命令またはレジスタ間
接分岐命令にのみ使用される命令
RETVAL サブルーチン呼び出し後のリターンアド
レスを生成する命令
GPSET グローバルポインタのセット命令
INDUC 誘導変数2

90%
MULSRC_LD
MULSRC_NONLDINDUCTIONGPSET
RETADDR
BRJMP

80%
70%
60%

A
B
C
D
E

50%
40%
30%
20%

addq $1,1,$2
stq$3,0($2)
and$2,0xff,$4
cmple $4,2,$5
bne
$5,L1
図3

10%

BRONLY コード例

0%
compress

gcc

go

図1

ijpeg

li

m88ksimperl

vortex

図4

値を生成する命令の分類

90%

70%
60%
50%
40%
30%
20%
10%
0%

compress

gcc

図2

go

ijpeg

li

m88ksim

perl

B

C
D
E

図 3 のデータフローグラフ

上させるには、高精度の分岐予測機構が必要となる。
条件分岐は 1 ビットの値予測機構に相当し、予測精度の高い種々の機構が提案、実装されている 8) 。図 4 で、
条件分岐命令 E の分岐予測が高精度でヒットする場
合、命令 C、D の値予測は行わなくても性能は変わらないと予想される。よって、命令 C、D のように、命令の演算結果が条件分岐命令にのみ使用されている場
合、当該命令は値予測を行わないようにする。C 言語の switch〜case や関数ポインタを使用した関数呼び出しによって生成される、レジスタ間接分岐命令に関しても同様の事が言えると予想される。従って、レジスタ間接分岐命令にのみ使用される値を生成する命令
は値予測対象から外す。
逆に、図 4 において、命令 D を値予測する場合を考えてみる。命令 E の条件分岐予測がヒットしたが、命令 D で誤った値を予測し、命令 E で誤った値を使用し分岐予測ミスが発生し、さらにその後命令 D の予測ミスが発覚し正しい値が生成され、再度命令 E で分岐予測ミスが発生するという事態が発生するということが起きる可能性がある。分岐命令にのみ使用される値は値予測を行わないようにすることで、このような値予測ミスによる誤った分岐予測ミスが起きる可能性を削減することができる。
4.3 GPSET: グローバルポインタ
64 ビットプロセッサ上では、64 ビットの定数をセットする場合に汎用レジスタの一つをグローバルポイン
タ (GP) として使用する場合が多い。GP を使用せずに 64 ビット定数をセットする場合、複数の定数セッ
ト命令やシフト命令を必要とするが、メモリ上に 64ビット定数格納領域を設け、GP がこのアドレスの近傍を指すようにすれば、ロード命令 1 命令だけで値をセットすることができる。関数のアドレスや文字列へのポインタや、C 言語の global や static な変数にアクセスする際のポインタを生成する際にも GP は使用される。図 5 では、命令 A により global 変数へのポインタを取得し、命令 C により subroutine 関数のア
ドレスを取得している。このように、GP は定数やア
ドレスが固定されているポインタを生成する命令の元となる場合が多い。GP 自身は同じコンパイル単位で

OTHERVPHITMULSRC_LD
MULSRC_NONLDINDUCTIONGPSET
RETADDR
BRJMP

80%

A

vortex99%LastValue 予測ヒット命令の分類

MULSRC NONLD 予測命令がロード命令以外であり、かつ、当該命令が使用する値のうち少な
くとも 1 つが複数の命令により生成されることがある命令
MULSRC LD 予測命令がロード命令であり、かつ、当該命令が使用する値のうち少なくとも 1 つが複数の命令により生成されることがある命令プログラムを実行した際に、値を生成する全実行命
令中で、それぞれのクラスに所属する命令の占める割合を図 1 に示す。また、VHT エントリが無限大の場合に、プロファイルを用いて LastValue 値予測で 99%以
上ヒットする命令を調べ、それらをクラス分けする。
それらが値を生成する全実行命令に対してどの程度の割合を占めるかを図 2 に示す。図 2 には 99%以上ヒットする命令のうち、前述したどのクラスにも属さないものを OTHERVPHIT として示してある。命令を静的にこれらのクラスに分類した際に、いくつかのクラスの命令についてを LastValue 予測を行わないよ
うにして、VHT の容量性ミスによる性能低下を防ぐ。
以下にこれらのクラスの詳細と、予測しないようにする理由を示す。
4.2 BRONLY: 分岐命令にのみ使用される値
図 3 にあるようなコードがあるとする。そのデータ
フローグラフは図 4 のようになる。現在のプロセッサは高クロックで動作させるためにパイプライン処理を行っている 9) 。パイプライン処理を行い処理速度を向

3

A
B
C
D
E
F

ldah t1,-1(gp)ldq t12,26880(t1)ldq t12,-32192(gp)jsr ra,(t12),12018fd10 <subroutine>ldah gp,8190(ra)lda gp,-16988(gp)
図5

A
B
C
D

呼び出し元関数例

E
F<subroutine>:
G ldah gp,8190(t12)H lda gp,-16496(gp)I lda sp,-112(sp)J stq ra,0(sp)...
K ldq ra,0(sp)L ret zero,(ra),0x1
図6

bne
$1,L1
mov
$2,$4
br L2
L1:
mov
$3,$4
L2:
subq $4,1,$5
and$5,0xff,$6
図7

MULSRC コード例

A
D

B
E
F
図8

図 7 の制御・データ
フローグラフ

生成命令が実行されているが、図 2 からわかるように LastValue でヒット率が高い誘導変数は非常に少ない。従って、誘導変数は予測対象から外すこととする。
4.6 MULSRC: 命令が使用する 1 つの値が複数の命令によって生成される場合
図 7 のコードについて考える。このコードのの制御
フロー (破線) とデータフロー (実線) は図 8 のようになる。図 8 において、命令 E が使用する値は命令 B ま
たは命令 D が生成する値のどちらかである。どちらの値を使用するのかは条件分岐の分岐先によって決定される。もし分岐先が一定でなく、かつ命令 B と命令 Dが生成する値が異なっている場合、命令 E の入力値が前回と異なる場合が多くなると考えられる。命令 F に関しても同様の事が言える。図 E の命令がロード命令
以外の場合、ある決まった入力値に対しては、必ずある決まった値を毎回返す。従って、入力値が異なれば出
力値も異なる場合が多くなると考えられ、LastValue
予測機構でヒットしにくくなると考えられる。このよ
うに、ロード命令以外で複数の命令が生成した値を使用する可能性のある命令を MULSRC NONLD クラスに所属するものとする。MULSRC-NONLD な命
令が LastValue 予測機構でヒットしやすいかどうかはプログラムのコンテキストに依存する。これに所属する命令を値予測しないようにすると、VHT を汚染しないことにより予測した場合よりも性能向上が得られる場合と、本来ならば予測がヒットして得られるはずの利得が得られずに性能が低下する場合の両方が考えられる。しかし図 1、図 2 からわかるように、MULSRC NONLD に属する命令は、実行される命令としては多いものの、LastValue 予測機構でヒットする命
令数が非常に少ないプログラムが多い。そのため、これらの命令を予測しないようにすることは VHT の汚染を防ぐには有効であると考えられる。
図 E の命令がロード命令の場合、決まった入力値に対して毎回決まった出力するとは限らない。入力値から計算されるアドレスに格納されている値が前回から変更されている可能性があるからである。また、入力値が異なっても、出力される値が等しくなる場合も考

呼び出し先関数例は常に同じアドレスを指している。そのため、GP を生成する命令は LastValue 値予測のヒット率が高い。
しかし、前述したように GP の値を使用する命令自身は定数や固定したアドレスを生成する命令であるので、これらも LastValue 値予測のヒット率が高い命令である。従って、GP の値を使用する命令を予測すれ
ば、GP 自身を生成する命令を予測しなくても性能低下は起きないと考えられる。
4.4 RETADDR: リターンアドレス
リターンアドレスはサブルーチン呼び出し命令 (図5 の命令 D) や、呼び出し元に戻る直前にスタック上に退避してあったリターンアドレスを読み込む (図 6 の命令 K) 際に生成される。そして、呼び出し先関数でスタック上に退避されるとき (図 6 の命令 J)、リター
ン命令で使用される (図 6 の命令 L)。さらに、Alphaの場合は、呼び出し元関数で GP を再セットする際にも使用される (図 5 の命令 E、F)。つまり、リター
ンアドレスは、最終的にはリターン命令と GP セット
命令に使用される。リターン命令に使用される場合を考えると、4.2 節で説明した分岐命令の時と同様、リ
ターンアドレス予測のヒット率が高ければリターンア
ドレス自身を値予測する必要はない。GP に使用される場合を考えると、4.3 節で説明したように、GP の値によって生成される値を予測するのであれば、GPを生成するのに必要なリターンアドレス自身を値予測する必要はない。従って、リターンアドレスを生成す
る命令は値予測を行わないようにする。
4.5 INDUC: 誘導変数
誘導変数 (Induction Variable) はループ中で一定の値が加減される変数のことである。誘導変数はストラ
イド値予測機構を使用すれば高精度で予測することができるが、LastValue 予測機構を用いて高精度で予測することは難しい。図 1 のように多くの誘導変数

4

BRONLY+
MULUSEMULUSE+

表 2 予測除外命令選択法
GPSET INDUC BRONLYGPSET INDUC BRONLY MULUSE NONLDGPSET INDUC BRONLY MULUSE NONLDMULUSE LD

えられる。アドレスが異なっていてもそこに格納されている値が等しい場合もあるからである。このように、ロード命令で、かつ複数の命令が生成した値を使用する可能性のある命令を MULSRC LD に所属するものとする。MULSRC LD な命令に関しても MULSRC NONLD と同様に実行命令よりも LastValue 予
測機構でヒットする命令数が非常に少ないプログラムが多い。そのため、このクラスに属する命令も値予測を行わない候補として使用する価値があると思われる。
4.7 予測除外命令選択法式
本節では、4.2 節〜4.6 節で説明した命令のうち、どの命令を選択的に予測対象から外すのか説明する。
まず、BRONLY、RETVAL、GPSET、INDUC に所属する命令は、予測対象から外す。この予測除外命令
選択法を BRONLY+とする。次に、BRONLY+に加えて MULUSE NONLD を予測対象から外したものを MULUSE- とする。MULUSE-に加えて MULUSE LD を更に予測対象から外したものを MULUSE+とする。以上の 3 つの予測除外命令選択法を
表 2 に示す。

5. 評

容量性ミスが発生しやすく、これらアドレス生成の元となる GPSET を予測しなかったため性能が低下したと考えられる。えられる。li では BRONLY+では性能が向上するが、MULUSE-、MULUSE+では性能が低下する。特に MULUSE+では著しく性能が低下する
が、これは図 2 からわかるように li では MULUSE+に属する命令がヒットする割合が他のものに比べて大きいからである。MULUSE+を予測対象から外すことによる性能低下は m88ksim にも見られるが、これも同じ理由であると考えられる。

6. ま と め
本稿では、プログラムを静的に解析して値予測となる対象を制限することで、VHT エントリ数を削減した時に生じる容量製ミスにより性能向上率が低下する手法を提案した。その結果、エントリ数が 128 のijpeg のように、選択しなければ予測ミスによるペナ
ルティーにより通常実行よりも性能が低下するが、選択することで速度向上が得られるものがあることが判明した。その反面、compress のように全命令を予測した場合に比べて性能が低下してしまうものもあることがわかった。今後の課題としては、更に細かく命令
をにクラス分けし、どの命令を予測対象とすれば良いのかを検討する。また、これと合わせてクリティカル
パスにも注目して予測命令を選択する方式についても
検討する。

価

参

本節では、4 節で提案した予測命令選択法に基づき、静的に予測しない命令を選択しておいた上で、VHTエントリが 128,256,512,1024 の場合について、速度向上率について評価を行う。
5.1 速度向上率
速度向上率を図 9、図 10 に示す。グラフの各ベン
チマーク毎に、左から 4 本を一組と見た場合、左からVHT エントリサイズが 128,256,512,1024 の場合を示す。同じ VHT エントリサイズのグラフは 4 本あるが、その中で左から順に、通常の値予測、分岐命令に使用されるものを除外 (BRONLY+)、分岐命令と複数の入力があるもの (ロードを除く) を除外 (MULSRC-)、
分岐命令と複数の入力があるもの (ロードを含む) を
除外 (MULSRC+)、となっている。
5.2 考察
go、gcc、ijper、perl では、通常の値予測と比較して、BRONLY+、MULUSE-、MULUSE+の順に実行速度が向上している。これは予測命令数が削減されることで、VHT エントリの容量性ミスが生じる頻度が減少したことによると考えられる。compress では
他のベンチマークに比べ、global 変数と static 変数のアドレスを取得する命令が多い。そのため VHT での考

文 献1) Ravi Bhargava and Lizy K. John.
Latency and Energy Aware Value Prediction for
High-Frequency Processors. In 16th Annual
ACM International Conference on Supercomputing(ICS), Jun 2002.
2) Brad Calder, Gleen Reinman, and Dean M.
Tullsen.
Selective Value Prediction.
In
26th International Symposium on Computer
Architecture(ISCA-26), May 1999.
3) Eric Larson and Todd Austin. Compiler controlled value prediction using branch predictor
based conﬁdence. In Proc. 33rd Annual International Symposium on Microarchitecture, Dec
2000.
4) Sang-Jeong Lee, Yuan Wang, and PenChung Yew.
Decoupled Value Prediction
on Trace Processors. In Sixth International
Symposium on High-Performance Computer
Architecture(HPCA-6), Jan 2000.
5) John Paul Shen Mikko H. Lipasti. Exceeding the Dataﬂow Limit via Value Prediction.
In Proc. 29th Annual International Symposiumon Microarchitecture(MICRO-29), Dec 1996.
6) Tarun Nakra, Rajiv Gupta, and Mary Lou

5

5%
4%
3%

NORMAL
BRONLY+VHT Entry Num 128 256 512 1024

2%
1%

MULUSE＋
MULUSE－

0%

go

gcc

-1%

図9

ijpeg

perl

速度向上率

11%

54%

10%

52%

9%
8%

50%

7%
6%

48%

5%

46%

4%

44%

3%
2%

42%

1%

compresslivortex40%

m88ksim

図 10 速度向上率 (続き)curate data value prediction using hybrid predictors. Proc. 30th Annual International Symposium on Microarchitecture(MICRO-30), Dec
1997.
11) Qing Zhao and David J. Lilja. CompilerDirected Static Classification of Value Locality
Behavior. Laboratory for Advanced Researchin Computing Technology and Compilers Technical Report No. ARCTiC 00-07, University of
Minnesota, Jul 2000.
12) 佐藤寿倫, 有田五次郎. タグビット幅を考慮した
データ値予測機構のハードウエア量削減. 信学技
報 CPSY2000-3, Apr 2000.
13) 佐藤寿倫, 有田五次郎. 0/1 の局所性を利用した
データ値予測機構のハードウェア量削減. 情報処
理学会研究会報告 2002-ARC-146, Feb 2002.
14) 神代剛典, 佐藤寿倫, 有田五次郎. トレースレベ
ル値予測におけるハードウェア量削減方法. 並列処理シンポジウム (JSPP), May 2002.
15) 飯塚大介, 小沢年弘, 坂井修一, 田中英彦. プロ
ファイルを用いた値予測命令削減手法. 情報処理学会研究会報告 2000-HPC-82, Aug 2000.

Soﬀa. Global Context-Based Value Prediction.
In Fifth International Symposium on HighPerformance Computer Architecture(HPCA5), Jan 1999.
7) Bohuslav Rychlik, John W. Faistl, Bryon P.
Krug, Albert Y. Kurland, John J. Jung,
Miroslav N. Velev, and John P. Shen. Efficient and Accurate Value Prediction Using
Dynamic Classification. Technical Report,
CMuART-1998-01, Carnegie Mellon Microarchitecture Research Team, 1998.
8) Andre Seznec, Stephen Felix, Venkata Krishnan, and Yiannakis Sazeides. Design Tradeoﬀs
for the Alpha EV8 Conditional Branch Predictor. In 29th International Symposium on Computer Architecture(ISCA-29), May 2002.
9) Eric Sprangle and Doug Carmean. Increasing Processor Performance by Implementing
Deeper Pipelines. In 29th International Symposium on Computer Architecture(ISCA-29),
May 2002.
10) Kai Wand and Manoj Franklin. Highly ac-6