ショート・リブド ・データの動的な予測に関する検討
吉瀬謙二, 高峰信, 田中洋介, 坂井修一, 田中英彦
東京大学大学院工学系研究科
1 はじめに機能ユニットが生成するデータの中で、リネーム・レジ きるデータをリネーム・レジスタに格納する必要はない
スタやレジスタ・ファイルからは一度も供給されるこ し、レジスタ・ファイルから一度も供給されないデータとなく消滅するデータのことをショート・リブド・デー をレジスタ・ファイルに書き戻す必要はない。以上の考
タと定義する。別の見方をすれば、 察から、不必要なデータの移動を削減することが本研究
ショート・リブド・データとは、生成されたが全く使わ の目的であるが、本稿では、リネーム・レジスタへ格納れないか、フォワーディング・パスのみを用いて供給され するデータ量の削減に絞って議論を進める。
リネーム・レジスタやレジスタ・ファイルへの書き戻しるデータのことであり、本来、これらのデータをリネーは、現在のスーパースカラ・プロセッサではボトルネッ
ム・レジスタやレジスタ・ファイルに格納する必要はない。本稿では生成されるデータの多くがショート・リブ クとなっていないが、今後、命令レベル並列性の向上や、ド・データであることを確認するとともに、その動的予 複数パスの同時実行といった技術によりサイクル当たりに生成されるデータ量は増加する傾向にある。リネーム・測の可能性を検討する。
レジスタへ格納するデータ量の削減は、今後予測される2 ショート ・リブド ・データボトルネックを解消するための重要な技術である。
プロセッサのデータの流れを図 に示す。機能ユニット
文献 ではレジスタ・ファイルへの書き戻しが不要なが生成したデータは、フォワーデ ィング・パスを用いて データをと定義して静的に検出する必要としている機能ユニットに供給されるとともに、リ 手法を提案しているが、本稿ではリネーム・レジスタやレオーダバッファ内のリネーム・レジスタに格納される。 ジスタ・ファイルから一度も供給されることなく消滅す
リオーダバッファはになっておりインオーダにレ るデータのことをショート・リブド・データ
ジスタ・ファイルにデータを書き戻す。と定義し、その検出機構と動的予測の可能性を検討する。

(short-lived data)

1[1]
short lived variableFIFO'LVSDWFK XQLW ZLWKLQVWUXFWLRQ TXHXH)HWFKXQLW&RPSOHWLRQ XQLW ZLWKUHRUGHU EXIIHU
5HQDPH
5HJLVWHU
5HJ)LOH,QVWUXFWLRQFDFKH)RUZDUGLQJ
3DWK,VVXH XQLW ZLWK FHQWUDO ZLQGRZ

'DWD
FDFKH

([HFXWLRQ XQLW ZLWK IXQFWLRQDO XQLWV図(short-liveddata)

1: プロセッサ内のデータの流れ

通常のプロセッサ・モデルでは、生成された全てのデータをレジスタ・ファイルに格納し、同じレジスタ番号のデータが書き戻されるまで、当該データはレジスタ・ファイル中に保存される。
しかしながら、プログラムの実行中に生成されるデータの多くが生成されてから短い間隔でのみ利用されるという性質が指摘されており 、リネーム・レジスタやレジスタ・ファイルへの書き込みが必ず必要というわけではない。フォワーデ ィング・パスのみを用いて供給で3ショート ・リブド ・データの検出機構

データが消滅するまでにリネーム・レジスタあるいはレジスタ・ファイルからアクセスされたデータはショート・リブド・データではない。このため、アクセスの有無を示すフラグを用いてショート・リブド・データを検出する。フラグは各リネーム・レジスタと、レジスタ・ファイルと同じエントリ数のアクセス履歴テーブルに保存す
る 図 。

( 2)

RegNo, Access Bit

AccessHistory Table
Short-lived data ?

RetireRegister File
Operand
Fetch

Reorder
Buffer(Access Bit)
Complete

Issue Unit with Instruction Window
Execution Unit with Functional Units[1]

図2: ショート・リブド ・データの検出機構

リオーダバッファに付加するアクセスビットは、データAn analysis of the dynamic prediction for short-lived data がリオーダバッファ内に存在する時のアクセスの有無をKenji KISE, Makoto TAKAMINE, Yosuke Tanaka, Shuichi
保存し、アクセス履歴テーブルは対応するレジスタ・ファ
SAKAI, Hidehiko TANAKA
Graduate school of Engineering, The University of Tokyo イルのデータに対するアクセスの有無を保存する。これ

らの情報を用いて、データが消滅する際に、そのデータがショート・リブド ・データであるかを検出できる。

スタ・ファイルに書き戻す必要がないとすると、データ転送量の 割以上を削減できることになる。

7

4 ショート ・リブド ・データの動的な予測

Program

Executed
Inst.

Created Data

Short-lived Data(ratio)

ある命令の生成したデータがショート・リブド・データ
cc1
120 M
60 M
49 M (82.1%)
だった場合に、その命令の次回の実行結果もショートリ
compress
54 M
27 M
22 M (81.3%)
ブド ・データである確率が高いといった偏りがあれば、 go
136 M
78 M
62 M (79.2%)
m88ksim
124 M
66 M
54 M (82.8%)
ショート・リブド・データの動的な予測の可能性が生ま
perl
101 M
52 M
40 M (78.3%)
れる。
xlisp
42 M
19 M
13 M (72.4%)
命令アドレス（プログラム・カウンタ）をインデック
表
ショート・リブド ・データの割合
スとして前回の実行の結果がショート・リブド・データであったかを保存するテーブルを用意し、前回のデータショート・リブド・データの予測について、予測成功のがショート・リブド・データだった場合に、今回の結果回数、失敗の回数、予測成功率もショート・リブド・データであると予測した場合の予を表にまとめる。ここでいう予測とは、測成功率を測定する。ここで、ショート・リブド・デー
章で説明した、前回の実行により生成されたデータがタの検出には 章で定義した機構を用いる。
ショート・リブド・データだったときに今回の実行結果
5 評価環境もショート・リブド・データであると予測する単純なもトレース・ド リブンのシミュレータを用いて、ショート・ のである。
リブド・データの割合と予測成功率を評価する。評価にProgram
HitMiss
Hit Ratio
用いるベンチマークを表 にまとめる。プログラムの入cc1
46,669,409
2,243,563
95.4%
力セットは実行命令数が１億程度に収まるように調整
compress 21,432,337
844,565
96.2%
し、コンパイルには（最適化オプショ
go58,699,172
3,052,470
95.1%
ン、ターゲットを用いた。
m88ksi
53,769,345
667,14298.8%

3:(Hit)+ Miss))

34(Miss)(Hit / (Hit41

Gnu C compiler
SPARC version 7)-O

Program
cc1
compressgo
m88ksimperl
xlisp

Description
From GCC 2.7.1
File compression
Plays the game of Go
Moto88K simulator
Manipulates strings
LISP interpreter

表Input Set
genrecog.i
small.in
99
ctl.raw\admits" in 1/8 input
6 queens

1: ベンチマークプログラム1

perlxlisp

38,778,014
12,690,702

1,567,074
719,340

96.1%
94.6%

4: ショート・リブド ・データの予測成功率
評価結果 (表 4) よりショート・リブド・データの予測成
功率は 94% 以上に達することがわかった。ショート・リブド・データである確率は 82%以下だが、前回の履歴を用いることで 94%以上の確率で予測できるという結果か表

評価には図 に示す標準的なスーパースカラのモデルを ら、前回のデータがショート・リブド・データだった場用いる。プロセッサの主なパラメタを表 にまとめる。 合には今回もショート・リブド・データであるという偏りがあることがわかる。

2

Parameter
Bandwidth ofdecode, dispatch, commit, retire
Reorder bu er
Instruction Window
Memory latency (no cache miss)
The number of Functional Unit

表Value8 instr. per cycle
32 entries
8 entries
2 cycleNo limitation

2: 評価に用いたプロセッサ・モデルのパラメタ

6 評価結果3

7

まとめと今後の課題

フォワーデ ィング・パスのみにより供給されるデータをショート・リブド・データと定義し、その検出機構と動的な予測の可能性を検討した。標準的なスーパースカラ・プロセッサを想定して評価した結果、生成されるデータの 割以上のデータがショート・リブド・データであることを確認した。また、前回の履歴を用いることにより、以上という高い確率でショート・リブド・データを動的に予測できることを示した。ただし、プロセッサ内でショート・リブド・データを予測する場合には、予測に失敗した場合の回復機構が必要となる。回復機構を含む予測機構の検討は今後の課題である。

794%

ショート・リブド ・データの検出結果を表 に示す。それぞれのプログラムについて、表 の左の列から実行命令数、生成されたデータの量、ショート・リブド・データの量（生成されたデータに対するショート・リブド ・ 参考文献データの割合）を示した。表中のはを意味している。表 の結果より、生成されたデータのかがショート・リブド ・データであることがわからる。もし、これらのデータをリネーム・レジスタやレジ

382%

3M million

72%[1] Luis A. Lozano C. and Guang R. Gao. Exploiting
Short-Lived Variables in Superscalar Processors. InProc. of MICRO-28, pages 292-302, 1995.