Vol. 44

No. 6

情報処理学会論文誌

June 2003

値予測の軽量効率化方式の提案と評価
飯
坂

塚
井

大
修

介†
一††

バルリ ニコ・デムス††
田 中 英 彦††

値予測はデータ依存関係を投機的に解消することで並列度を抽出する手法である．これまでに予測精度を高めるための種々の方式が提案されているが，そのために必要なハードウェア量とレイテンシ
が大きく実装が困難なため，値予測は現実のものとなっていない．中でも予測履歴テーブルは大きなハードウェアを必要とするためこの問題が顕著である。テーブルのタグや予測値のビット数，エントリ数を制限してハードウェア量を削減すればハードウエア量などの問題はなくなるが、これに伴う容量性ミスによる性能向上率の低下が問題となる。本論文では、値予測を現実のプロセッサに適用するための技術として，静的に命令を分類し，予測候補から除外する命令を選択することですることで総予測命令数を削減し，値予測履歴テーブルのエントリ数を削減しても性能が低下しないですむ方式を提案し、初期的な評価を行う．

A Light-Weight Efficient Value Prediction Mechanism
Daisuke Iizuka,? Niko Demus Barli,†† Shuichi Sakai††and Hidehiko Tanaka††
Value prediction is a technique to extract parallelism by predicting values and speculatively
resolving true data dependencies among instructions. Various value prediction mechanisms
have been proposed in the past and many of them employ sophisticated methods to achieve
higher prediction accuracy. However, these methods are still not considered sufficiently feasible since they require large amount of hardware and impose high access latency, especially for
Value History Table (VHT). This paper proposes a mechanism to reduce the requirements for
VHT entries , by statically classifying instructions that are unlikely useful for prediction andexclude them from prediction targets. Using the mechanism, it is shown that we can achieve
similar prediction benefits with smaller size of VHT.

可能な命令が多いほど速度向上が得られる．値予測で1. は じ め に予測可能な命令数を増やし，予測精度を向上させるた

アウトオブオーダ実行を行なうスーパースカラプロ

めに，種々の複雑な予測機構が提案されている7) ．まセッサは，プログラムから命令レベル並列性を動的にた，値履歴テーブル（Value History Table,VHT）の抽出することで実行速度の向上を図っている．しかし，サイズを大きくすると VHT にヒットしやすくなるたプログラム中にはデータ依存（真の依存）が存在する

め，予測可能命令数を増加させることができる．このため，従来の並列度の抽出技法だけでは性能向上に限ような方法によって高精度で予測を行うことができる

界がある．近年，この真の依存関係を解決するためのが，予測機構を実装するためのハードウェア量も膨大

投機手法として，命令が生成する値を予測する値予測なものになり，また予測値を取り出すまでのレイテンが考案されている6) ．値予測は，予測精度が高く予測

シも大きくなる．本論文では，値予測の実装可能性を† 東京大学大学院 工学系研究科
Graduate School of Engineering, The University ofTokyo†† 東京大学大学院 情報理工学系研究科
Graduate School of Information Science and Technology, The University of Tokyo
☆
現在，日立製作所中央研究所
Presently with Hitachi, Ltd., Central Research Laboratory

予測のみを用い，予測対象外となる命令を静的に選択高めるために，一番単純な予測機構である LastValue
しておくことで少ない VHT のエントリ数によるデメ
リットを軽減し，これによって小ハードウェアかつ低レイテンシで動作する値予測方式を提案し，評価する．

2. 値予測機構のアクセスレイテンシ
本節では，近未来のプロセッサに値予測機構を実装
1

2

June 2003

情報処理学会論文誌する場合を考える．具体的には，2001 年の SIA のロー
3)

ドマップ

より，2004 年に製作されると考えられる

798


g hSi 4 j 465/ 0132

ER%S$TR U"! '%S$'Q( `

90nm プロセス，4GHz で動作する 4way のスーパー
スカラプロセッサに値予測機構を搭載する場合につい

#;:=<

て考える．

2.1 値予測機構
値予測は命令の演算結果を演算前に予測することで，真のデータ依存関係を超えて投機的に命令を実行し実行速度を向上させる手法である．値予測の機構として>=>@?A B CED FGHFBI
J >K? D FMLNFEI

 

a+b Gdce fは，最も近い過去に得られた値を予測値とする Last-

Value 予測機構6) ，最も近い過去の 2 回の差分 Stride

_ \S] ^

O "! ( 'QP
"%&$')( *$'
7[Z&\&] ^#+!  $





 

  

VXW ' Y$h \S] ^ ( ,'$. "!
#! $_ \S] ^ R3( P

7[ZS\&] ^図 1 LastValue 予測機構と最も近い過去に得られた値 Value から今回の計算値
を Value+Stride として予測するストライド値予測機
12)

構，過去の連続した有限個の計算値を保存し，同一節で述べ，2 節では前者のアクセスレイテンシを小さくする方法について考える．

のコンテキストが繰り返されると仮定して予測を行な

2.3 LastValue 予測機構のアクセスレイテンシ

うコンテキスト・ベース値予測機構8) などがある．い一番単純な予測機構である，図 1 のような LastValue

ずれの予測機構でも，過去の演算結果を VHT に保存予測機構を考える．読込ポート数は同時に予測を行う

し，次回同一 PC の命令をフェッチした際に，VHT か命令の数だけ必要となる．リタイア時に VHT の更新

ら予測値を取得し予測を行う．予測値が本来の実行値を行うとすると，LastValue の書込ポート数はリタイと異なっていた場合（予測ミス時）は，それに依存しア幅と同じだけ必要となる．リタイア幅を 4 として，た命令を全て再実行する必要があり，実行時間にペナ

この予測機構の VHT のエントリ数と同時予測命令数

ルティーが生じる．そのため，VHT の各エントリに(読込ポート数) を変化させた時の VHT アクセスレイ

確信度として飽和カウンタを設け，予測値がヒット/

テンシを図 2 に示す．これは CACTI3.010) を用いてミスした際にカウンタを増加/減少させ，ある閾値を計算した．計算に用いたパラメータは，1 エントリが6)超えた場合にのみ予測を行うのが普通である ．

8 バイト，タグ無しでダイレクトマップ，最速になる

2.2 値予測機構のアクセスレイテンシ

ようにサブバンクに分割，ポートは全て読み書きが独

文献1) では，プログラムを実行した際に，ある命令

立，90nm のプロセス，電圧 1.0V とした．なお、確が発行されてから，その命令が生成した値を最初に使信度の値に関しては読込ポート数が同時予測命令数と用しようとする命令が現れるまでのサイクル数を統計

リタイア幅の合計分だけ必要となるが，4 ビット程度的に求めている．その結果，ロード命令の 78-94%，整であれば予測機構全体へのレイテンシへの影響は小さ

数命令の 73-99%により生成される値については，生

いと考えられるため無視できるものとする．

成されてから 1 サイクル以内に使用されていることが

図 1 の予測機構では，命令と共に予測値をリザベーわかった．値予測を用いてこの依存関係を断ち切り速

ションステーション (RS) に格納し，予測結果の検証

度向上を得るには，前者の命令の実行完了前に予測値に利用するものとする．

を取りださなければならない．同じ文献1) によると整2.4 ストライド値予測機構のレイテンシ

数命令の 13-51%がリネームしてから 3 サイクル以内

LastValue 予測機構の次に単純であるストライド値に実行を完了している．値予測機構から予測値を取り予測機構を図 3 に示す．図 3 のストライド予測機構出すまでのアクセスレイテンシを小さくししないと予では，VHT 更新時にストライド値を計算するために，測値を取り出す前に実行が完了してしまう．

読込ポート数が同時予測命令数に加えてリタイア幅のアクセスレイテンシを小さくするには，低レイテン

分だけ余計に必要となる．リタイア幅 4，同時予測命

シな予測方式を用いて，エントリ数，ポート数，連想

令数が 4 の場合は 8 ポートになる．図 2 より，同時予度，タグビット幅を小さくすればよい．そのようにす

測命令数，リタイア幅が同じ条件の下では LastValue

ると容量性ミスが発生しやすくなる．アクセスレイテ

予測機構よりもレイテンシの面で不利になる．

ンシを小さくしたまま容量性ミスを削減するためには読込ポート数の増加を抑えるために，予測値と Last-

予測成功率の低い命令の実行結果を VHT に反映させValue を共に RS に入れておき，命令の演算終了後直ないようにすることが考えられる．後者については 3

ちに検証とストライドの計算を行うようにすれば図 1

Vol. 44No. 6

値予測の軽量効率化方式の提案と評価  
" # $ % & ' ( ) *+ ,/ # - " & ' ( ) *+ ,- 0 % & ' ( ) *+ ,  

3

測機構よりも複雑なため，更にアクセスレイテンシが- # " . & ' ( ) *+ ,0 / - & ' ( ) *+ ,/ - . & ' ( ) *+ ,必要となる．

  

エントリ数が 128 の LastValue 予測機構はレジス      

 

タファイルとほぼ同じ大きさになる (1kB 程度) ため!

ハードウェア量，レイテンシが小さく実装しやすい．
よって本論文では LastValue 予測機構のみを用いるものとする．

     



図 2 読込ポート数とエントリ数による VHT アクセスレイテンシ(wports=4)

3. 静的な予測命令選択法の提案
2 節では，低アクセスレイテンシにするため，エントリ数を小さく，タグを使用しない VHT について述べた．このような VHT では容量性ミスが起きやすい．

<2=

 
_ `a 9 b 9;: 6 87%'&() *& +  " () " ! - %

W
V
1ZY.[

D.DFE G HI'J KMLNKHO
P DQE J KSRTK'O  
fhg

LkjSl

そこで本節では静的に命令の種類やデータフローを解= AB C    ! "$# () " ! - %2) ">@?AB C
1 0 / )XX
XX  
 

U
8 

` AB C ! 3 " )54\^]>@?AB C ,.- %'/ 0
1 0 / )XXim

じる可能性を低下させ，VHT を単純化した際に生じる性能低下を抑える方式を提案する．実行バイナリ中XX

ced " %2)

析し，予測対象命令を限定することで容量性ミスが生

図 3 ストライド値予測機構の各命令には予測を行うかどうか判断するため 1 ビットの付加情報ついているものとし，静的解析結果によりこのビットの値を確定する．

3.1 命令の静的分類
静的にプログラム中のデータフローを解析し，命令を以下に示すクラスに分類する．クラス分けは以下にと同様に読込ポート数を同時予測命令数と等しくでき述べる順に適用され，一度特定のクラスにクラス分ける．しかし二つの 64bit の値を RS 内に保持しなけれされた命令を他のクラスに再分類することはないもの

ばならないために，一つの予測値を RS に格納するだとする．

けで済む 2.3 節の方式よりも RS のサイズが大きくな

BRONLY 予測値が条件分岐命令またはレジスタ間る．近年の高速に動作するプロセッサでは値の代わりに物理レジスタ番号を RS に格納する方式を採用しており，二つの 64bit の値を RS で保持すると，ソース

接分岐命令にのみ使用される命令

RETADDR サブルーチン呼び出し後のリターンア
ドレスを生成する命令

レジスタの値を 2 つ格納する従来型の RS よりも規模

GPSET グローバルポインタのセット命令

が大きくなる．よって 2.3 節の場合よりも高速動作がINDUC 誘導変数

困難になる．

MULSRC 予測命令が使用する値のうち少なくとまた，パイプライン長が長い場合，ある命令がリタ

も 1 つが，複数の命令により生成される命令

イアされる前に同一 PC の命令がフェッチされる可能プログラムを実行した際に，値を生成する全実行命性が高くなる．当該命令が誘導変数の場合，VHT が最令中で，それぞれのクラスに所属する命令の占める割新の状態に更新されないままストライド値予測を行う

合を図 4 に示す．図 4 で，同一 PC を持つものを一ため，予測ミスが発生する．これを防ぐには分岐予測つとして数えたもの (静的命令) を図 5 に示す．また，と同様にフェッチ時に投機的に VHT を更新すること

VHT エントリが無限大の場合に，プロファイルを用が考えられるが，書込ポート数が同時予測命令数の分

いて LastValue 値予測で 99%以上ヒットする命令をだけ余分に必要となりレイテンシが増加する．さらに，調べ，それらをクラス分けした．値を生成する全実行

ストライド値予測機構では，予測値を得るための加算命令に対して 99%以上ヒットする命令がどの程度の割

器のレイテンシ，ストライドを計算するための減算器

合を占めるかを図 6 に示す．図 6 で 99%以上ヒットのレイテンシ，VHT の各エントリにストライド値をする命令のうち，前述したどのクラスにも属さないも保持するためのレイテンシが余分かかり，LastValueのは OTHERVPHIT として示してある．命令を静的予測機構と比較すると不利になる．ハイブリッド予測にこれらのクラスに分類した際に，特定のクラスの命機構やコンテキストベース予測機構はストライド値予令について LastValue 予測を行わないようにすること

4457678 9:;=< > 9 ? @ < A
BC=D E F G H I=JI=D K
L M7NO7P
Q=R S T U
V W X Y=Z7Z=V[=\ ]^=_ `June 2003

情報処理学会論文誌

      


A

addq

$1,1,$2B

stq$3,0($2)Cand$2,0xff,$4

D

cmple $4,2,$5



E

bne



図 7 BRONLY コード例











$5,L1


図 8 図 7 のデータフローグラフ

  % % " "  *# ( ( * ( / %  # % ,   # & "  (  ( " 0  3 # & " 0 0 (    ! " #   $   & ' (  )  )  # +  &   )  &  ' , -  ' . 0 1 & ( &  " " % ' .  + &   & (  & (  . &  ' 0 . 0 - ( ' 
%
2.
 
                         

制する．以下にこれらのクラスの詳細と，予測しないようにする理由を示す．

3.2 BRONLY: 分岐命令にのみ使用される値

図 4 値を生成する実行命令の分類 

で，VHT の容量性ミスによる性能向上率の低下を抑< = > ?7@A@7<
  576 8%97: ;B7C D = >E 7F G7HAI
J%K7L M N O P Q7R%Q7L S J%7K L M N O P L S
RUTAVAW N 

図 7 のコードを検討する．そのデータフローグラフ
は図 8 のようになる．このコードをパイプライン処理
し処理速度を向上させるには，高精度の分岐予測機構が必要となる．条件分岐は 1 ビットの値予測機構に相当し，予測精度の高い種々の機構が提案，実装されている9) ．

 

図 8 で，条件分岐命令 E の分岐予測が高精度でヒッ トする場合，プロセッサの発行幅が広く，ユニット数

変わらないと予想される．よって，命令 C，D のようが多ければ命令 C，D の値予測は行わなくても性能はに，命令の演算結果が条件分岐命令にのみ使用されて  "  $ $ + "  + 0  " $ -   " &   1   "  & 1       !   #   & ' ( ! !) *  *  " ,  & (  *  &  ( ' - .  ' / ( 1 2 & $ ( &  $ ' /  ! , & (  ( !  & ( &  4 / & ' 1 ! / 1 . ' 1 (
(
(

 
3  ! / !
      %$

243546 7
387 549 : ;4< 546 7=>4? @ : A B ? C
DE4F G H I J K4LKMF N
O PMQMR4S
T4U V W X
Y Z [ \M]4]MY^4_ `aMb c

数呼び出しによって生成されるレジスタ間接分岐命令
レジスタ間接分岐命令にのみ使用される値を生成する

       C 言語の switch〜case や関数ポインタを使用した関に関しても同様の事が言えると予想される．従って，

図 5 実行された静的命令の分類

いる場合，当該命令は値予測を行わないようにする．

命令は値予測対象から外す．

3.3 GPSET: グローバルポインタ
64 ビットプロセッサ上では，64 ビットの定数をセットする場合に汎用レジスタの一つをグローバルポイン
タ（GP）として使用する場合が多い．GP を使用せずに 64 ビット定数をセットする場合，複数の定数セッ
ト命令やシフト命令を必要とするが，メモリ上に 64

ビット定数格納領域を設け，GP がこのアドレスの近

傍を指すようにすれば，ロード 1 命令だけで値をセットすることができるからである．関数のアドレスや文  !   # # &  ( ! &  & ( & -  ! # *   $  &  .   !  $ .  &         "   $ %  '  ! )  $  '  $  % * +  % , . / $ # & $  # % ! ,  ) $  &  $ & $ &  1 , $ % . , + & % .
.
'

 
0  ,
      #
図 6 99%LastValue 予測ヒット実行命令の分類

字列へのポインタや，C 言語の global や static な変数にアクセスする際のポインタを生成する際にも GPは使用される．図 9 では，命令 A により global 変数へのポインタを取得し，命令 C により subroutine 関
数のアドレスを取得している．

Vol. 44No. 65

値予測の軽量効率化方式の提案と評価

Aldah t1,-1(gp)B

ldq

t12,26880(t1)Cldq

t12,-32192(gp)D

jsr

ra,(t12),12018fd10 <subroutine>Eldah gp,8190(ra)

F

lda

A

bne

$1,L1

B

mov

$2,$4

C

br



D

gp,-16988(gp)
図 9 呼び出し元関数例

L2


L1:
mov

$3,$4


L2:
E

subq

$4,1,$5Fand$5,0xff,$6

<subroutine>:

図 11 MULSRC コード例

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

Gldah gp,8190(t12)H

lda

gp,-16496(gp)I

lda

sp,-112(sp)を生成するのに必要なリターンアドレス自身を値予測J

stq

ra,0(sp)

する必要はない．従って，リターンアドレスを生成すK

ldq

ra,0(sp)

3.5 INDUC: 誘導変数

L

retzero,(ra),0x1

誘導変数 (Induction Variable) はループ中で一定

図 10の値が加減される変数のことである．誘導変数はスト

る命令は値予測を行わないようにする．

...

呼び出し先関数例

ライド値予測機構を使用すれば高精度で予測すること

このように，GP は定数やアドレスが固定されていができるが，LastValue 予測機構を用いて高精度で予るポインタを生成する命令の元となる場合が多い．GP

測することは難しい．図 4 からプログラム中では多く自身は同じコンパイル単位では常に同じアドレスを指の誘導変数生成命令が実行されていることが知られる

している．そのため，GP を生成する命令は LastValueが，図 6 からわかるように LastValue でヒット率が値予測のヒット率が高い．しかし，前述したように GP

高い誘導変数は非常に少ない．ここでは，できるだけの値を使用する命令自身は定数や固定したアドレスを単純な予測機構（LastValue 予測機構）によって高い生成する命令であるので，これらも LastValue 値予性能をあげることをねらうため，誘導変数は予測対象

測のヒット率が高い命令である．従って，GP の値をから外すこととする．

使用する命令を予測すれば，GP 自身を生成する命令を予測しなくても性能低下は起きないと考えられる．

3.4 RETADDR: リターンアドレス

3.6 MULSRC: 命令が使用する 1 つの値が複数の命令によって生成される場合
図 11 のコードを検討する．図 12 に，このコード

リターンアドレスはサブルーチン呼び出し命令（図の制御フロー (破線) とデータフロー (実線) を示す．

9 の命令 D）や，呼び出し元に戻る直前にスタック上

図 12 において，命令 E が使用する値は命令 B またはに退避してあったリターンアドレスを読み込む（図 10

命令 D が生成する値のどちらかである．どちらの値の命令 K）際に生成または取得される．そして，呼びを使用するのかは条件分岐の分岐先によって決定され出し先関数でスタック上に退避されるとき（図 10 の命る．もし分岐先が一定でなく，かつ命令 B と命令 D

令 J），リターン命令で使用される（図 10 の命令 L）．

が生成する値が異なっている場合，命令 E の入力値がさらに，呼び出し元関数で GP を再セットする際に前回と異なる場合が多くなると考えられる．実際に命も使用される（図 9 の命令 E，F ）．つまり，リター

令 B と命令 D が同じ値を生成することが静的にわかンアドレスは，最終的にはリターン命令と GP セット

るのであれば，コンパイル時に最適化により A より命令に使用される．リターン命令に使用される場合を前または E より下の一命令に集約されるため，命令☆

考えると，3.2 節で説明した分岐命令の時と同様，リB と命令 D は異なる値を取ることが多いと考えられ

ターンアドレス予測のヒット率が高ければリターンア

る．命令 F に関しても同様の事が言える．命令 E，F

ドレス自身を値予測する必要はない．GP に使用されのように，ある命令が使用する一つの値が，複数の命る場合を考えると，3.3 節で説明したように，GP の令によって生成される可能性のある命令を MULSRC

値によって生成される値を予測するのであれば，GPと命名する．

3.6.1 MULSRC がロード命令以外の場合☆

Compaq Alpha の場合

ロード命令以外で MULSRC に属する命令を MUL-

6

June 2003

情報処理学会論文誌

SRC NONLD と命名する．MULSRC NONLD な命
令が LastValue 予測機構でヒットしやすいかどうかはプログラムのコンテキストに依存する．しかし，図 4，
図 6 からわかるように，MULSRC NONLD に属する

BRONLY+MULSRCMULSRC+

命令は，実行される命令としては 4.3%〜40%と多い

表 1 予測除外命令選択法
GPSET INDUC BRONLY RETADDRGPSET INDUC BRONLY RETADDRMULSRC NONLDGPSET INDUC BRONLY RETADDRMULSRC NONLD MULSRC LD

ものの，LastValue 予測機構でヒットする命令数は実行される命令数と比較すると最大の adpcm で 4%と(5)Reaching Definition17) 解析をし，各命令間の少ない．これは，MULSRC NONLD の命令の入力値

レジスタの Use-Def を調べる．これにより関数が毎回異なる確率が高いため，結果として当該命令が内のレジスタを介したデータフローグラフが完生成する値も毎回異なる値になる確率が高いためであると考えられる．そのため，これらの命令を予測しな

(6)

成する．
jmp 命令や条件分岐命令から Use-Def chain を

いようにすることは VHT の汚染を防ぐには有効であ

辿り，分岐命令にのみ値が使用されている命令

ると考えられる．

を探し BRONLY とする．BRONLY に属した命令からも同様の事を行う．これを収束するま

3.6.2 MULSRC がロード命令の場合
ロード命令で MULSRC に属する命令を MUL-

SRC LD と命名する．図 12 でノード E がロード命令の場合，決まった入力値に対して毎回決まった出力
するとは限らない．入力値から計算されるアドレスに(7)で繰り返す．
自分が生成した値を自分自身で使用している場

(8)
(9)

合，それを INDUC とする
GPSET，RETADDR を探す
MULSRC を探す．MULSRC を使っている命

格納されている値が前回から変更されている可能性が

令も MULSRC にするあるからである．逆に，入力値が異なっても，出力さ3.8 予測除外命令選択法

れる値が等しくなる場合も考えられる．アドレスが異

本節では，3.2 節〜3.6 節で説明した命令のうち，どなっていても格納されている値が等しい場合もあるかの命令を選択的に予測対象から外すのかについて述らである．このように，ロード命令で，かつ複数の命べる．まず，BRONLY，RETADDR，GPSET，IN-

令が生成した値を使用する可能性のある命令を MUL-

DUC に所属する命令は，予測対象から外す．このSRC LD に所属するものとする．MULSRC LD な命

予測除外命令選択法を BRONLY+とする．さらに，令に関しても MULSRC NONLD と同様に，実行命

BRONLY+に加えて MULSRC NONLD を予測対象

令よりも LastValue 予測機構でヒットする命令数がから外したものを MULSRC- とする．MULSRC-

少ないものが多い．そのため，このクラスに属する命に加えて MULSRC LD を更に予測対象から外したも令も値予測を行わない候補として使用する価値があるのを MULSRC+ とする．以上の 3 つの予測除外命と思われる．ロード命令は実行レイテンシが大きいた

令選択法を表 1 に示す．

め値予測がヒットした際の利得は大きい．そのため，

図 4，5 を見ることで，これらの選択法により予測

MULSRC NONLD よりも MULSRC LD の方は値予対象外となる動的/静的命令の比率を知ることができ

測除外候補としては優先度を低くする．

る．なお、図 5 は実行バイナリ全体ではなく、実行バ

3.7 静的解析法

イナリのうち実際に実行された部分を 100%として比各命令のクラス分けは，静的リンクされたバイナリ率を求めている．

を逆アセンブルして制御フロー，データフローを解析することにより行う．これによりソースコードが手に本節では，3 節で述べた提案手法を評価する方法について説明する．

入らないバイナリや，libc の関数内等についても解析

3.9 プロセッサモデルを行うことができる．本解析ではソースコードは一切

図 13 にベースラインとなるプロセッサのパイプライ

用いていない．解析は関数単位で行う．解析の流れはンを示す．各パラメータを表 2 に示す． 90nm 4GHz

以下の通りである．

ではレジスタのアクセスレイテンシが 2 サイクルに

(1)
(2)

バイナリを逆アセンブルする．
table jump(C 言語の switch〜case 文に相当)

なる．

(3)
(4)

の飛び先を jump table を読んで決定する．
制御フローを解析し，基本ブロックに分割する．
基本ブロック毎にレジスタの Use-Def を求める

値予測の動作は以下の通りである．フェッチした 4命令のそれぞれについて，静的に追加された追加ビットを調べる．追加ビットにより予測対象外となっていVol. 44

No. 6


¦ §¨




 


¡

¢¤£¥

 

®



  
i jDk(lm n op
qr
¶· ³

KL
 
 

®®



©8ª¬« ­
¯´µ

²³
¯°±

7

値予測の軽量効率化方式の提案と評価

B
.
1

+
F
J ; '&)&*  ; )$H(I ; , ;G % =!; C "D"$E ; ! "$#&%('&)(* , ,/.
s/t uv w vO (   D

f
C g¸:¹ º »¼ ½ ¾ º »¿ÀÁ Â º

0
, ,21
{ y
} y~

>
3
46587:9<;8= A
? @



{|
x yz


 
 

[ MON P$Q8R STUP(QWV-X:Y Z:P
Y \:]_^`]2abVbMcR d(^ Te      



.hf
, ; '

  

図 13 ベースラインプロセッサのパイプライン

る命令については予測を行わず，VHT の汚染防止のためリタイア時に VHT への更新も行わないものとする．
予測対象となっていた場合は LastValue 予測機構

表 2 プロセッサモデル
ISA
Compaq Alpha compatible
Inst. Latency
Load 1(for addr. calc), Other 1
Phy. Reg
64bit × 80
ROB
64 entries
Pipeline
11 stages
Fetch Decode
Issue Retire
Max 4 insts/cycle
Retire width
4
Res. Station
20 entries
LSQ
20 entriesEU
ALU x 4, LSU x 2
BTB1024 entries, 2 way
Branch Pred.
gshare, 4k entries
Ret. Addr. Stack
20 entries
IcacheBlock 16B, 1k entries, 2 way, latency 2
DcacheL1
Block 64B, 256 entries, 2 way, latency 2
DcacheL2
infinite size, latency 6
VHT
No tag, read 8 ports, write 4 ports,
5bit counter, 128/256 entriesにアクセスし，2 サイクル経過すると確信度と予測値が出力される．確信度が閾値以上であればリネーム
ユニットからレジスタ情報を受け取り，レジスタファ
イルの該当エントリに予測値を書き込む．図 13 の下にあるレジスタファイルは上にあるものと実体は同じであり，予測値を書き込むタイミングを示すために下にも書いてある．2 サイクル後に書込が完了し，予測値は通常の値と同様に使用される．予測値をレジスタに書き込むのと同時に，予測対象命令が入っているリ
ザベーションステーションにも予測値を書き込む．当該命令がディスパッチされると同時に予測値をパイプ
ライン上に流し，実際の値が生成された際にすぐに比較できるようにする．予測値が異なっていたら分岐予
測ミス発生時と同様，リタイア時にパイプラインをフラッシュし，状態を巻き戻す．リタイア時に実行結果
を VHT に更新する．
図 2 より，クロック周波数 4GHz の場合，VHT エ

表 3 ベンチマークの詳細
ベンチマーク

内容

099.go124.m88ksim
126.gcc
129.compress
130.li
132.ijpeg
134.perl
147.vortex
adpcm
epic
g721
ghostscript
gsm
jpeg
mesa
mpeg2
pegwit
pgp
rasta

囲碁
プロセッサシミュレータ
C コンパイラ
ファイル圧縮lisp 処理系
画像不可逆圧縮, 展開
スクリプト言語
データベース
音声可逆圧縮, 展開
画像可逆圧縮, 展開
音声不可逆圧縮, 展開
postscript エンジン
音声不可逆圧縮, 展開
画像不可逆圧縮, 展開
3D 描画ライブラリ
動画不可逆圧縮, 展開
暗号, 復号暗号, 復号
音声認識

実行命令数

143M
147M
142M
127M
217M
127M
129M
120M
12M
73M
593M
1017M
287M
287M
225M
1542M
67M
126M
28M

ントリが 128，256 のときには 2 サイクルで予測値が取り出せ，図 13 のパイプライン構成に合うためこれて静的にデータフロー解析を行い，予測対象外となるらのエントリ数で評価を行う．512 以上のエントリ数

命令を探し，追加ビットに反映する．SPECint95 に関

では VHT からレジスタに格納した予測値を取り出ししては表 3 にあるように，100M〜200M 命令程度でた時に正しい実行結果が出ている可能性があるため本終了するように実行時の入力パラメータを調整した．

論文では評価を行わない．

Mediabench は全命令実行した．

3.10 評 価 環 境
評価には，トレースベースのシミュレータを使用

4. 評

価

した．ベンチマークは SPECint95 の 8 つのプログラ

本節では，提案方式の値予測ヒット率，ヒット命令

ムと，Mediabench4) の 11 個のプログラムを使用し数，および速度向上率について評価を行う．3 節で提た．ベンチマークは Alpha21264 のコードを出力する

案した予測命令選択法に基づき，予め静的に予測対象

GNU GCC(バージョン 2.95.2) に，最適化オプショ

外命令を選択し追加ビットを修正しておく．

ン-O3 を付けてコンパイルし，ライブラリを静的リン

4.1 値予測ヒット率とヒット命令数クしたものを使用した．予めこの実行ファイルについ

VHTEntry=128 の場合において，本論文の手法を

8

情報処理学会論文誌

June 2003

適用した際の値予測ヒット率の変化を図 14 に，値予測向上し normalvp より性能が向上している．これは予でヒットした動的な命令数を図 15 に示す．図 15 は対測命令を選択することで高ヒット命令のうちいくつか数軸になっている．normalvp が通常の値予測である．

が予測対象外になったが，容量性ミスにより予測ミス

19 中 14 のプログラムでヒット率が向上した．図 14を発生させる命令がそれよりも多く予測対象外になっより，BRONLY+，MULSRC-，MULSRC+と予測たためと考えられる．

命令を制限する度にヒット率が上がるプログラムがあ以上から，VHT を簡単化してハードウェア量・レる (go, m88ksim, gcc, compress, epic, mpeg2, peg-

イテンシを小さくした際に，通常の値予測を行った場

wit)．ijpeg, vortex, jpeg, pgp では予測を行わなかっ合と比較しても性能が向上する場合があること，予測た場合よりも全ての場合においてヒット率が低下してを行わなかったときよりも性能が向上するものが多い

いるが，それ以外のものは BRONLY+，MULSRC-，

こと，予測を行わない場合と比較して通常実行時より

MULSRC+のいずれかを適用することで適用しなかっも性能低下が起きる場合でも，ただ一つの例外である

た場合よりもヒット率が上昇している．

gsm を除いては速度低下がごくわずかであることから

図 15 よ り，予 測 命 令 を 制 限 す る こ と で ，perl，

ghostscript 以外のものは予測ヒット命令数が減少している．ghostscript で BRONLY+，MULSRC-，

本方式が有利であることが示された．

5. 関 連 研 究

MULSRC+と予測命令を制限する度にヒット命令数

予測値を取り出すレイテンシを隠蔽する値予測方式が増大しているのは，本来は高精度で予測可能であるとして，VHT を用いずに値予測を行う方式1),5) が提が確信度カウンタが閾値に達する前に別の命令の内容

案されている．文献1) では，VHT の代わりに Predic-

で上書きされていたものが，命令制限により上書きがtion Value Cache（PVC）を用意し，トレースキャッ

生じなくなり閾値に達し，予測を行うようになったた

シュ上の命令をフェッチする時と同時に PVC に格納めと考えらられる．

されている予測値をフェッチする．その値を予測に使

図 14 より，perl はヒット率が悪い．perl はエント

用すると同時に Prediction Trace Queue（PTQ）に

リ数を 1024 以上にすると予測ヒット率，ヒット命令

も入れる．PTQ では命令がパイプライン中を流れて数とも大きく増加するため，本論文の VHT サイズでいくのに合わせて格納値をシフトし，リタイア時の予は容量性ミスが頻発していると考えられる．

測値更新に使用する．PVC をもちいることで，その4.2 速度向上率

トレースに合った予測値が取得でき，PTQ を使用す

速度向上率を図 16 と図 17 に示す．100% が予測をることで PVC の読み込みポート数を 1 に抑えること

行わない時の実行速度であり，これより高ければ実行速度が向上していることになる．

ができ，低レイテンシで動作可能となる．
文献11) では当該命令が上書きする論理レジスタに全体として，値予測を行った場合は行わない場合と入っている値を予測値とすることで VHT を用いずに比較すると-3.9%から 55.5%の性能向上が得られるこ

値予測を行う手法を提案している．論理レジスタの空とがわかる．いずれかの命令選択法を適用すること

きエントリを VHT として利用する形になるため，別で，go, gcc, li, g721, ghostscript, pegwit, m88ksim,に VHT を使用する場合と比較するとエントリ数が少

mpeg2 では normalvp よりも性能向上率が最大 6%向ないという問題がある．

上する．ijpeg，perl(VHTEntry=128) は, 値予測を行

VHT の 1 エントリに必要なハードウェア量を削減

わない場合よりも性能が低下するが、その程度はわずすることでも低レイテンシを実現できる．文献14) でか 0.1%である gsm は normalvp でエントリ数が無限は，VHT のタグビット幅を削減する手法を，文献15)

大の時でも性能向上率が 0.2%しかないことがわかっ

では，予測値を 0/1 に限定することでハードウェアている．そのため，命令選択によりヒット率とヒット量を削減手法を提案している．本稿ではタグは使用せ

命令数が低下した影響により最大 3.9%の速度低下がず，予測値は 64 ビットの値を予測しているが，高クおきたと考えられる．しかし MULSRC+では 2%に抑ロックで動作するように VHT のエントリ数を削減しえることができた．残りのプログラムでは normalvpているためハードウェア量が少なく，かつ低レイテンと比較すると劣るが，値予測を行わない場合よりは高シで動作するようになっている．文献2) では動的に予速に実行できている．

測命令を選択する方式を提案している．クリティカル

li の BRONLY+と go，gcc，g721，pegwit は命令パスの先頭にある命令を動的に検出し，当該命令の実選択によりヒット命令数は減少しているがヒット率は

行結果のみ VHT の更新を行う方式を提案している．

Vol. 44No. 6

# $ % & ' () *+-, .0/-1 2 3405-1 6 , 798
405-1 6 , 793


























  



^\]
^f]
^e]
^d]
^c]
^b]
^ a]
^`]
\_]
\^]
\\]



 "
!
 

9

値予測の軽量効率化方式の提案と評価











nm
kl
i9j

 :;

gh

図 14

  

F G H IKJ L M N
O P9Q0R S T U
VXW S Y P Z0[
VXW S Y P Z0U<   =  >@? A 



 

; 


B


 =


 =



 





 

C =

?
 =

?
: 

DDE

 

 



?






値予測ヒット率 (VHTEntry=128)- . / 021 3 4 5
687 9 :8; < =2>8; ?87 @ A=2>8; ?87 @    ,*,)+    () *      









 









  



 

 




  

図 15



!

"#

 


 

 






$







 





 

% 

 "

"

  

 

 

"






値予測ヒット命令数 (VHTEntry=128)





. / 0 12 3 4 5
687 9;:=< > ?
@;A=< B 7 C=D@;A=< B 7 C=?

, + -*

&&'



F


()    
'%&'


E














 










    



 





  


!"


 




 
# 





 



 

$ 


!


! 

K LLM N
GHI J

OK

K PN

Q

K RPS

H

図 16 速度向上率 (VHTEntry=128)

 
 
- , .+

 / 0 1 23 4 5 6798 :<;= > ?
@<A = B 8 C D@<A = B 8 C ?

 

F 
 

)*    
(&'(
 

E 



 

 









 







 



 



 







    "! # 


 



$ 






 

図 17 速度向上率 (VHTEntry=256)



% 





! 

!

 
 

GGH

 

 



!


 



10

情報処理学会論文誌

また，予測命令や予測値を使用する命令の種類により確信度の閾値を変える方式も提案している．文献13)
では静的に，あるいはプロファイルを用いて，Last-

Value/Stride/Context のそれぞれの予測機構で予測可能な命令と予測しない命令とに分類する方式を提案している．これにより，VHT のポート数が少ない場
合には，動的に予測を行う場合よりも性能向上率が高くなることを示している．本稿では LastValue 予測のみを使用しているため，文献13) よりもハードウェア
量や VHT アクセスレイテンシに関して利点がある．

6. ま と め
本論文では，高クロックで動作するプロセッサで値予測を行う場合において，VHT のアクセスレイテン
シを低減させるためにはエントリ数を削減することが必要であることを示し，これにより生じる容量性ミスを低減するため，静的に予測命令を選択する手法を提案した．その結果，小さく単純な VHT を用いて効率よい値予測を行う可能性があることを示した．特に，gcc のように全命令を予測対象とするよりも特定の命令を選択的に予測対象とすることで速度向上率が向上するものがあることが判明した．その反面，compressのように全命令を予測した場合に比べて性能が低下してしまうものもあることがわかった．今後の課題としては，(1) 更に細かく命令をにクラス分けし，どの命令を予測対象とすれば良いのかを検討 (2) 複数命令間の依存関係を考慮し，予測による速度向上効果の得られない命令も除外するようにする方式についても調査・検討することがあげられる．

参 考 文

献

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) ITRS. International Technology Roadmap for
Semiconductors 2001 Edition, 2001. http://public.itrs.net/.
4) Chunho Lee, Miodrag Potkonjak, and WilliamH.
Mangione-Smith. MediaBench: A Tool for
Evaluating and Synthesizing Multimedia andCommunications Systems. MICRO, Vol. 30, ,1997.

June 2003

5) 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.
6) Mikko H. Lipasti and John P. Shen. Exceeding the Dataflow Limit via Value Prediction. In
Proc. 29th Annual International Symposium on
Microarchitecture(MICRO-29), Dec 1996.
7) Tarun Nakra, Rajiv Gupta, and Mary Lou
Soffa. Global Context-Based Value Prediction.
In Fifth International Symposium on HighPerformance Computer Architecture(HPCA5), Jan 1999.
8) Yiannakis Sazeides and James E. Smith. The
Predictability of Data Values. In Proc. 30th
Annual International Symposium on Microarchitecture, Dec 1997.
9) Andre Seznec, Stephen Felix, Venkata Krishnan, and Yiannakis Sazeides. Design Tradeoffs
for the Alpha EV8 Conditional Branch Predictor. In 29th International Symposium on Computer Architecture(ISCA-29), May 2002.
10) Premkishore Shivakumar and Norman P.
Jouppi. CACTI 3.0: An Integrated Cache Timing, Power, and Area Model. WRL Research
Report 2001/2, COMPAQ, Western ResearchLaboratory, Feb 2001.
11) Dean M. Tullsen and John S. Seng. StoragelessValue Prediction using Prior Register Values.
In 26th International Symposium on Computer
Architecture(ISCA-26), May 1999.
12) Kai Wand and Manoj Franklin. Highly accurate data value prediction using hybrid predictors. Proc. 30th Annual International Symposium on Microarchitecture(MICRO-30), Dec
1997.
13) 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.
14) 佐藤寿倫, 有田五次郎. タグビット幅を考慮した
データ値予測機構のハードウエア量削減. 信学技
報 CPSY2000-3, Apr 2000.
15) 佐藤寿倫, 有田五次郎. 0/1 の局所性を利用した
データ値予測機構のハードウェア量削減. 情報処
理学会研究会報告 2002-ARC-146, Feb 2002.
16) 飯塚大介, 角田忠信, 坂井修一, 田中英彦. 値予測における値履歴テーブルエントリ数の削減. 情報処理学会研究会報告 2002-ARC-149, Aug 2002.
17) 中田育男. コンパイラの構成と最適化. 朝倉書店, 1999.

Vol. 44

No. 6

11

値予測の軽量効率化方式の提案と評価(平成 14 年 9 月 20 日受付)

坂井 修一（正会員）(平成 15 年 0 月 0 日採録)

昭和 56 年東京大学理学部情報科学科卒業．昭和 61 年同大学院工学飯塚 大介（学生会員）

系研究科情報工学専門課程修了．工1975 年生．1998 年東京大学工学

学博士．同年工業技術院電子技術総部電気工学科卒業．2003 年同大学院合研究所入所．この間平成 3〜4 年，

工学系研究科情報工学専攻博士課程

米国マサチューセッツ工科大学招聘研究員，平成 5〜

終了．同年，日立製作所中央研究所

8 年 RWC 超並列アーキテクチャ研究室室長．平成 8に入社．現在に至る．投機実行，プ〜10 年筑波大学電子・情報工学系助教授．平成 10 年

ロセッサアーキテクチャなどの研究に従事．

東京大学大学院工学系研究科助教授，平成 13 年より同大学院情報理工学系研究科教授．計算機システム一般，特にアーキテクチャ，並列処理，スケジューリン
グ問題，マルチメディアなどの研究に従事．平成 2 年
本会論文賞，平成 3 年日本 IBM 科学賞，平成 7 年市村学術賞，ICCD Outstanding Paper Award など受賞．電子情報通信学会，人工知能学会，IEEE，ACM
各会員．

バルリ

ニコ・デムス

田中 英彦（正会員）

1975 年生．1999 年東京大学工学

昭和 40 年東京大学工学部電子工部電気工学科卒業．2001 年同大学

学科卒業．昭和 45 年同大学院工学院工学系研究科情報工学専攻修士課

系研究科博士課程修了．工学博士．

程終了．現在，同大学情報理工学系

同年同大学工学部講師．昭和 46 年

研究科電子情報学専攻博士課程在学

同助教授．昭和 62 年同教授．平成中．プロセッサアーキテクチャなどの研究に従事．

13 年より同大学院情報理工学系研究科教授・研究科長．
この間昭和 53〜54 年米国ニューヨーク市立大学客員教授．計算機アーキテクチャ，並列処理，自然言語処理，メディア処理，分散処理，CAD 等の研究に興味を持っている．著書「非ノイマンコンピュータ」，「情報通信システム」，共著書「計算機アーキテクチャ」，「VLSI コンピュータ I,II」，「ソフトウェア指向アーキ
テクチャ」．本会フェロー．電子情報通信学会，人工知能学会，日本ソフトウェア科学会，IEEE，ACM 各会員．