Ephemeral Variabl es: Alu-Net によるアクセスの局所性の利用

3H-01

辻 秀典, 坂井 修一, 田中 英彦
東京大学大学院 工学系研究科と利用のために、いくつかの条件により Ephemeral
1

変数を分類する。

はじめに命令レベル並列実行によって性能を得るマイクロプロ

3.1

スーパースカラとの対応セッサが一般的となった現在、さらなる性能向上をめざ

スーパースカラ・アーキテクチャは、一般にはデータした次世代マイクロプロセッサに関するさまざまな研究依存を解消するためにリオーダバッファを用いた、レジが行われている。そのひとつとして、我々は大規模デースタリネーミングが行われている。このようなスーパータパス (Very Large Data Path { VlDp)・アーキテク スカラにおけるデータアクセスのモデルは図 1のようにチャ[3] を提案している。これは、マイクロプロセッサになる。ここでは、Ephemeral

おける命令実行の本質が演算であることに注目し、命令データアクセスパスによって処理されるかによって次の列中のデータフローを Alu-Net [ 1] と呼ぶ複数の ALU

3 種類に分類する。

によって構成される機構上で実現することによって、命令実行のスループットを向上させようとするアーキテクチャである。
本稿では、この Alu- Net を利用した局所的なデータ変数がスーパスカラのどの

1. forwarding path
2. reoder bu er { i nstructi on wi ndo w
3. reoder bu er { regi ster l e { i nstructi on wi ndo w

アクセスを可能とする Ephemeral 変数を定義し、これがどのようなものか説明したうえで分類する。
2Register
File

Ephemeral 変数

マイクロプロセッサにおける処理は、メモリ空間上のInstruction
Window

データに何らかの演算処理を施し、得られた結果を再びReorder
Buffer

メモリ空間上に書き戻すことが基本である。データの流れに着目した場合、あるデータはメモリからレジスタにFunctionalUnits

読み込まれ、レジスタを介して処理が行われる。このとき、レジスタへの値の書き戻しから次の参照までの時間は短いものから長いものまでさまざまである。これらのレジスタアクセスのうち、定義から参照までの時間が短いものは、一時的なデータの保存場所としてレジスタを利用するものとみなすことができる。
Alu- Netはこのようなデータアクセスを、ALU 同士の局所的な接続によって実現するもので、これによって、処理を高速化するとともにレジスタの有効利用を可能となる。そして、一時的なデータの保存場所としてレジスタを利用する、局所的なデータアクセスのために使われる変数を Ephemeral
3

Ephemer al変数と定義する。

変数の分類
変数を利用するためには、これを検出しなければならない。ここでは、検出
Ephemeral Variabl es: Expl oi ti ng Access Local i t yusi ng Alu-Net
GraduateSc ho olofS
AKA
I,

En
gin
eering,

3. 2

Ephemer al

Ephemeral

変数の参照数

変数は、ある命令 (pro ducer) によって生成されるデータを消費する命令 (consumer)変数である。Ephemeralに受け渡す変数はデータを消費する命令によって参照されるが、ひとつの Ephemeral変数に対して複数の参照が行われる可能性がある。図 2 では参照数

1 と 3 の例を示している。ここでは、その参照数によりEphemeral 変数を分類する。Alu- Net 上で Ephemeral
変数に対する複数の参照を可能とすれば、処理は効率化

命令列中に存在する Ephemeral

Hidenori TSUJI, Sh uichi

図 1: スーパースカラのデータアクセス・モデル

HidehikT
heUniv

3. 3

Ephemer al

Ephemeral

変数の検出変数の検出を行う際には、図 3 に示すように、最後の参照または再定義を検出することによって、

o TANAKAersit y ofできるがそれとともに Alu- Net は複雑化する。

Toky oEphemeral変数であることを決定する。理想的には最どうかの保証を考えなければならない。図Producer

5 は、あるひEphemeral 変数と検出される場合と、すべての分岐パスで Ephemeral 変数と検出される場合

Consumer

とつの分岐パスでEphemeral Variableの例である。
あるひとつの分岐パスのみでと検出された場合にEphemeral

Ephemeral変数である変数とする場合が最も楽観的であるが、これでは他の分岐パスではEphemeral変数であるかどうかを保証できない。逆に、すべての分
Producer

図Consumer

2: Ephemeral 変数の参照数

time
Variable 01

defineVariable 01

refer

Ephemeral

岐パス上で変数であると検出する方法が最も厳密な場合である。これは、どのパスが実行されてもEphemeral

Detection of Ephemeral Variable

変数として処理することができるが、検出Ephemeral 変数の割合も減に手間がかかるだけでなく、少する。

final referrence
Ephemeral
Variable

redefinition

Variable 01

refer (final refer)

Variable 01

redefine

Ephemeral
VariabledefinedefineBasic Block

Basic Block

final referfinal refer図

final refer

3: Ephemeral 変数の検出
final refer

後の参照を検出することが望まれるが、最後の参照はプログラムを最後まで実行しなければ保証できない。その図ため再定義を検出する方が容易である。
3.4

参照の距離

Ephemeral 変数を参照される距離によって

ここでは、

4

5: 複数パスにおける保証

最後にEphemeral

変数を検出した結果は文献[2] によって分類する。最も単純には、基本ブロック内に限定された述べられている。その仮定は本稿の分類によると、複数変数とする方法である。しの参照を許可、変数の再定義のによる検出、すべての分アクセスのみを

Ephemeral5

かし、基本ブロックの平均サイズは一般的に 程度と小Ephemeral

岐パスにおいて保証されるEphemeral変数である。こSPECi nt95 ベ(SPARC コード で評価) の 21%
要がある。参照の距離によっては、図 4 に示すように、 〜 34% の命令が Ephemeral 変数を生成していることある変数を例にとっても、それが Ephemeral 変数 にな が分かっている。
さいために、より多くの変数を検出して利用するためには、ある程度、参照の距離を大きくする必る場合とならない場合がある。

ンチマークプログラム

今後、本稿で分類した他の仮定を適用すれば、より多Ephemeral 変数を検出できると考えられる。また、Ephemeral 変数の分類と Alu-Net の構造の関係につくのdistancebranch inst.

Basic Blockのような基本的で厳しい仮定において、

Variable 01

defineVariable 01

refer

Not Ephemeral
Variable

いて議論する必要もある。
Ephemeral
Variable

参考文献

Variable 01

refer

Variable 01

refer (final refer)

一, 田中英彦: Alu-Net: VlDp アーキテクチャにおける命令実行機構, 情報処理学会 第 57 回全国大会, Vol. 1,

Variable 01

redefine

No. 1Q-10, pp. 40{41[1] 辻秀典, 中村友洋, 吉瀬謙二, 安島雄一郎, 高峰信, 坂井修

branch inst.

(1998).

[2] 高峰信, 辻秀典, 吉瀬謙二, 田中洋介, 坂井修一, 田中英彦:

図4: Distance of Reference

VlDp

アーキテクチャにおけるデータアクセスの軽減手法, 情報処理学会研究会 ARCH, Vol. 133,No.

6, pp.

31{36(1999).
3. 5

複数パスにおける保証

Ephemeral[3] 中村友洋, 吉瀬謙二, 辻秀典, 安島雄一郎, 田中英彦: 大規模変数の参照が基本ブロックを越える場合には、複数の分岐パス対してEphemeral

変数であるかデータパスプロセッサの構想, 情報処理学会研究会 A
R CH,
Vol. 124,

No.

3, pp.

13{18(1997).