山口 健輔 †VLDP3 アーキテクチャにおけるメモリリネーミング手法の検討
入江 英嗣 †

服部 直也 †

坂井 修一 †

田中 英彦 †概要
近年、次世代アーキテクチャとして VLDP3 のように多数の ALU を規則的に並べたアーキテクチャが提案されている。アウトオブオーダ実行を行うアーキテクチャではメモリアクセス時に依存解決、アドレス計算など様々なオーバヘッドが生じるため、メモリアクセスの高速化は VLDP3 の性能を大きく左右すると考えられる。本稿では、メモリアクセス高速化手法の一つであるメモリリネーミ
ングを VLDP3 に適用する機構として Speculative Wire Promotion を提案し、既存の手法であるSpeculative Memory Cloaking と併せてシミュレータに実装し、評価を行った。

Memory Renaming Mechanisms
on VLDP3 Architecture
Kensuke Yamaguchi§
Hidetsugu Irie§
Naoya Hattori§
Shuichi Sakai§
Hidehiko Tanaka§

Abstract
In recent years, the architecture which put many ALUs in order like VLDP3 has been proposed as
the next-generation microprocessor architecture. In the architectures which adopt out-of-order execution, performance improvement is disturbed by large latency generated by dependence analysis,
address calculation, and so on, so acceleration of memory access is likely to influence performanceof VLDP3 greatly. In this paper, we describe the instruction execute model and memory accessmechanism of VLDP3 Architecture, and propose ”Speculative Wire Promotion” as a mechanism
in which we mount Memory Renaming Mechanisms in VLDP3 Architecture. We also implement iton VLDP3 simulator with the known mechanism ”Speculative Memory Cloaking”, and evaluatedthem by simulation results.

1

はじめにアウトオブオーダ実行を行うプロセッサは、ロード命令に先行するストア命令の中に参照ア

半導体デバイス技術の進歩によってマイクロドレスが確定していないストア命令が存在する

プロセッサが利用可能な半導体資源は年々増加を場合、ロード命令のキャッシュアクセスを遅らせ続けており、数年後にはさらに豊富なトランジスる必要があり、この待ち時間がオーバヘッドとタ資源を利用できると予想されている。しかし、なってしまう。その他にも、メモリアクセス時にスーパースカラに代表される従来のアーキテクはアドレス計算やメモリユニットとの通信レイテチャをそのまま大規模化しても並列性の抽出にンシなど様々なレイテンシによるオーバヘッドが限界があり、十分な性能向上ができない。そこ生じるため、メモリアクセスの高速化は VLDP3で、大規模並列実行を可能とする次世代アーキの性能を大きく左右すると考えられる。そこで本テクチャとして VLDP3(Very Large Data Path)

稿では VLDP3 の命令実行モデル及びデータ供アーキテクチャの研究開発が行われている。

給の概略を述べ、メモリアクセス高速化手法の一† 東京大学§ The University of Tokyo

つであるメモリリネーミングを VLDP3 に適用する機構として Speculative Wire Promotion をストア、ロード両方の命令のエントリを作り、そ提案し、既存の手法である Speculative Memory

れぞれの PC を記録する。また、共通の tag を生Cloaking と併せてシミュレータに実装し、評価成して両方のエントリに書き込み、valid bit をvalid に設定する (図 1-(c))。
ストア命令はフェッチされたときに毎回 DPNTの PC フィールドを参照し、依存予測情報を発見したら SF に tag を書き込んで full/empty bitを empty に設定する (図 1-(d))。そしてストア値が判明したらストア値を SF に書き込むと同時に full/empty bit を full に設定し (図 1-(e))、通常のキャッシュアクセスを行う。
ロード命令もフェッチされたときに同様に毎回 DPNT を参照し、依存予測情報を発見したらDPNT に記録されている tag をインデックスとして SF を参照し、full/empty bit が full となっていたら記録されているストア値を引き出し、ロード命令の Consumer に送る (図 1-(f))。その後ロード命令は非投機的なキャッシュアクセスを行い、正しいロード値と予測値を比較する。一致していなかったら、ロード命令以降の処理をやり直す。

を行う。

2

関連研究
本章ではメモリアクセスによるレイテンシを隠蔽する手法の一つであるメモリリネーミング [8]を実現するための機構として、Speculative Mem-

ory Cloaking[4, 5] を紹介する。
Speculative Memory Cloaking では、DDT(Dependence Detection Table)、DPNT(Dependence Prediction and Naming Table)、SF(Synonym File) と呼ばれる 3 種類のテーブ
ルを用いる。図 1 に、これらのテーブルを用いてメモリ依存の予測及び値のフォワーディングを行う様子を示す。

DDT

address storePC

while(･･･){store a;a}load a;DDT

VLDP3 の概要

3

本章では、VLDP3 の命令実行方式およびキャッ(b)ストアの Commit時シュアクセス方式について説明する。

DPNT

address storePC

instPC tag valid PRED

storePCload a;DPNT

instPC tag valid PRED

storePC tag1 valid
loadPC tag1 valid

Pred
Pred

storePC tag1 valid
loadPC tag1 valid

SFtag1

SFtag value full/empty
fullstore a;

empty

3.1

VLDP3 の命令実行方式

実行コードは IB(Instruction Block) という単(d)ストアの Fetch時

位で与えられ [2]、この IB を ALU-Net と呼ばれinstPC tag valid PREDる命令実行機構に割り付けて命令を実行する。以DPNT

storePC tag1 valid
loadPC tag1 valid

store a;

Pred
Pred

tag value full/empty(c)ロードの Commit時

tag1 value

store a;instPC tag valid PRED(a)仮定した命令コード
astorePC

DPNT・・・

SF

Pred
Pred

tag value full/empty
tag1 value(e)ストアの値判明時

load a;full

下で IB 及び ALU-Net について述べる。

3.1.1

ALU-Net(f)ロードの Fetch時

図 1: Speculative Memory Cloaking の動作

図 1-(a) に示すような、メモリ依存関係にあるストア命令とロード命令が繰り返し実行されるようなコードを仮定する。
まず、ストア命令は Commit 後に DDT に PCとデータのアドレスを書き込む (図 1-(b))。
ロード命令は Commit 後に DDT の Address
フィールドを参照し、同じアドレスにアクセスしたストア命令のエントリが存在したら DPNT にVLDP3 の命令実行機構は、複数の ALU が網目状に並べられ、ごく短い配線 (Local Wire) で結ばれた ALU-Net 構造である。各ノードは Assignされた命令に基づいて演算を行い、結果を Local
Wire を用いて次のノードに受け渡す (図 2 右)。
各ノードには同時に複数の命令を Assign することができる。Assign された命令は、Assign された順とは無関係にオペランドが揃ったものから発火する。ALU-Net 内と外部とのデータの受け渡しは Global Wire と呼ばれる配線を用いて行われ、Local Wire によるデータ通信に比べて、レイテンシが大きい。

キャッシュアクセスは命令コード中で自らに先行addaddaddaddadd

ALUaddLocal WireNOPaddadd

データフローグラフ

ALU-Net

図 2: ALU-Net への命令 Assign の様子

するすべてのストア命令及びロード命令がキャッシュにアクセスした後で行うように制御されるので、ロード命令は依存関係にあるストア命令がキャッシュへの書き込みを終えた後でキャッシュから値を読み出して ALU-Net にあるロード命令の Consumer のノードに値を送る。
なお、VLDP3 では Wait Mask Table[3] と呼ばれるメモリ依存予測手法を用いて投機的なロー3.1.2

ド処理も行っているが、簡単のため以下では非IB投機ロードを基準に議論する。

大規模演算機構 ALU-Net 制御の単純化のために、VLDP3 では命令割り当てや解放を、複数の命令をまとめた塊を最小単位として行う。この3.3

VLDP3 の命令実行モデル

塊を IB と呼ぶ。同一 IB 内の命令に関しては、依存するデータを全て Local Wire で転送するこ

本節では、VLDP3 の命令実行モデルについてとを想定しており、これを保証するために IB は述べる。IB が Fetch されてから Retire するまでコンパイラが生成する。コンパイラはプログラのパイプライン処理を図 4 に示す。

ム中のデータフローを解析し、ALU-Net で実行できるように各命令の割り当て位置を決定する。

VLDP3 のキャッシュアクセス方式

3.2

時間
Store
ExecuteVLDP3 では、ロード・ストア間の依存関係の解析及びキャッシュのアクセス順序の制御をLSU(Load Store Unit) と呼ばれるユニットで行う。IB の Fetch 要求が送信されてからロードのConsumer にロード値が届くまでの、依存関係にあるストア命令とロード命令のパイプライン処理の様子を図 3 に示す。
ストア

Fetch

要求IBFetch

IBDecode

IBAssign

ロードFetch

IBFetchIB
DecodeIB
Assign要求全ての先行スト キャッシュアドレス ネットワーク
アのキャッシュ計算 レイテンシ（ ALU-LSU) 書き込み待ち 書き込みネットワーク
アドレス
キャッシュ ネットワーク
アドレス待ち 計算 レイテンシ
依存解決待ち読み出し レイテンシ（ ALU-LSU)（ LSU-ALU)
ロードの Consumerにロード値が届くタイミング
アドレス、値待ち

図 3: 依存関係にあるストア命令とロード命令のパイプライン処理の様子

IB

コード中の命令順序

IB
IB
IB
Fetch Decode Assign

Load
ExecuteIB
ExecuteIB
RetireConsumer
Execute

LSU

依存解析

Cache
Read

図 4: IB を単位とした命令実行のパイプライン処理

まず命令は IB 単位で Fetch、Decode され、得られた配置情報を元に ALU-Net に Assign される。Assign が完了した IB の各命令は、IB Ex-ecute ステージでは全て命令単位で実行される。
各命令はオペランドが揃った時点で発火し、演算を開始する。ロード命令、ストア命令はオペランドが揃ってアドレス計算が終わった時点で LSU

まず分岐予測器から Fetch Unit に Fetch 要求にキャッシュアクセス要求を送信し、依存解析がが送信され、IB が Fetch される。次に Decoder終わってからキャッシュにアクセスする。ロードに渡されて Decode され、ALU-Net に Assign さ

命令のキャッシュ読み出しが終わるとロード値れる。ストア命令はストア値、アドレスのオペはロード命令の Consumer のノードに転送され、ランドが届いてアドレス計算が終わると LSU にConsumer のノードでの演算が開始される。IB内の命令の演算が全て終わると ALU-Net 上からIB が flush され、新たな IB の Assign が可能となる。この状態において IB 内の全ての命令が例外を起こさないこと、及び直前の IB の Retire が確認されると、IB は Retire を開始する。

キャッシュ書き込み要求を送信する。ロード命令
はアドレスのオペランドが届いてアドレス計算が終わると LSU にキャッシュ読み出し要求を送信する。LSU では、ストア命令及びロード命令の及びそのロード値を使用する命令 (3 番) を予測

メモリリネーミングのVLDP3 への実装する。次に、検出されたストア命令からロード命

本章では、VLDP3 におけるストア・ロード間を指定する。そして、0 番のストア命令のストアのデータ転送を高速化することを目的として、メ値が判明し次第 3 番のノードに値がフォワーディ

モリリネーミングの VLDP3 への実装を検討すングされ、3 番の命令が演算可能となる。このこる。ストア・ロード間のデータ転送に Local Wireとにより、0 番、1 番のストア命令と 2 番のローを用いることができれば極めて高速なデータのド命令によるレイテンシの影響を全く受けずに転送が可能であるが、Local Wire を用いたデー3 番以降の命令を実行することができる。なお、
0 番のノードからフォワーディングされた値は、後で正しい値と比較するために LSU に転送しておく。そして、0 番と 1 番の命令が実行された後に 2 番のロード命令が非投機的に実行されることにより正しい値が判明し、その値が LSU で投機的にフォワーディングされた値と比較される。
一致すればそのまま後続の処理を続行し、一致しなければ、投機的フォワーディングパスを削除した上で IB の先頭から非投機的に処理をやり直す。投機が失敗していた場合は予測テーブルにそのストア命令の識別子を書き込み、以降はそのストア命令のノードからの投機的フォワーディングパスは動的に削除する。

4

タ転送はコンパイル時に指定する必要があるため、同一 IB 内のデータ供給にしか適用できない。そこで、依存するストア・ロードが同一 IBに含まれる場合 (IB 内メモリ依存) と異なる IBに含まれる場合 (IB 間メモリ依存) を区別して考え、IB 内メモリ依存を高速化する手法としてSpeculative Wire Promotion を提案する。尚 IB
間メモリ依存に対しては、関連研究として紹介した Speculative Memory Cloaking を適用して高速化する。

4.1

Speculative Wire Promotionの概要

Speculative Wire Promotion では IB 内メモリ依存を静的に予測し、コンパイル時にストア命令のノードからロード命令の Consumer のノードまで Local Wire を用いた投機的なフォワーディン
グパスを構築することによってロード命令のレイテンシを隠蔽する。Speculative Wire Promotionに対応した IB 生成の様子を図 5 に示す。

(0)

*p=1;

(1)

x=*g;

(2)

y=x+1;

4.2

Speculative Wire Promotion
による命令処理のレイテンシの削減効果
Fetch

要求

IBFetchIB
DecodeIB
AssignFetch

要求

IBFetchIB
DecodeIB
Assign(B) ストア Fetch
要求

IBFetchIB
DecodeIB
Assignストア(A)

ロード

全ての先行スト キャッシュ
アドレス ネットワーク
アのキャッシュ計算 レイテンシ（ ALU-LSU) 書き込み待ち 書き込みネットワーク
アドレスキャッシュ ネットワーク
アドレス待ち 計算 レイテンシ
依存解決待ち読み出し レイテンシ（ ALU-LSU)（ LSU-ALU)
アドレス、値待ち

値待ち

Local Wireの転送レイテンシ

ロードの Consumerにロード値が・・・ 届くタイミング(A)通常の非投機処理時にロード命令の Consumerにロード値が届くタイミング(B)Speculative Wire Promotionの処理時にロード命令の Consumerにロード値が届くタイミング

…
…
…
…

*g=0;

令の Consumer まで Local Wire を用いた転送路

投機的

図 6: ロード命令の Consumer のノードにロード

local forwarding(3)

値が届くタイミング
22

投機ロード抑制

flag

x=*g;

x=*g;
0

0*g=0;*g=0

y=x+1;

y=x+1;

3

3

*p=1;

*p=1;

11

図 5: Speculative Wire Promotion に対応したIB 生成

以下で Speculative Wire Promotion の動作を示す。まず、コンパイル時に同じアドレスにアクセスするストア命令 (0 番) とロード命令 (2 番)、Speculative Wire Promotion による処理を行った時にロード命令の Consumer のノードにロード値が早いタイミングで届くようになる様子をタイミングチャートを用いて図 6 に示す。また、非投機的にキャッシュアクセスを行った場合とSpeculative Wire Promotion による予測ロード値のフォワーディングを行った場合のデータ通信の様子を図 7 に示す。
これらの図に示したように、非投機ロードによる値の転送では Global Wire を用いた値の転送を2 回行うのに対し、Speculative Wire Promotion
では Local Wire を用いた非常にレイテンシの小LSU
W riteW rite

Re q.

Re q.

Rea dva lu e

Re q.

ALU-Net

ALU-NetLoad AStore A

Load’sConsumer

Store B

Load AStore A

Load’sConsumer

Wire で接続されたネットワーク・モデルである。
VLDP3compiler の作成と ALU-Net トポロジによる IB の品質については関連論文で述べられている [2]。
シミュレーション時の各種パラメタは表 1 の通りとする。

Store Bva lu e(A)非投 機的メモリ アクセ ス時のロード 値の流 れ（ B ） Speculative Wire Promotion実 行時のロード 予測値 のフ ォワ ーディ ング

・・・ 非投機時の Requestの流 れ (Global Wire 経由 )・・・ 非投機時のロ ード値 の流れ (Global Wire 経 由 )・・・ Speculative Wire Promotion時の ロー ド
予測値の 流れ (Local Wire 経由 )図 7: 非投機的キャッシュアクセス時と Specula-tive Wire Promotion 実行時のデータ通信の様子

表 1: VLDP3 シミュレータの各パラメタ
パラメタ
IB 多重度
Reorder Buffer size
Fetch latencyDecode latency
Assign latency
Execute latency(per Node)
Local Wire network latency
ALU-Net → LSU network latency
LSU → ALU-Net network latency
ALU-Net → Cloaking Prediction Table network latency
Cloaking Prediction Table → ALU-Net network latency
Cloaking Prediction Table access latency
Cache access latency
Cache size
Prediction Table size
Branch Prediction
Cache

値
816
2 cycle2 cycle2 cycle2 cycle0 cycle3 cycle2 cycle3 cycle2 cycle4 cycle4 cycle∞∞100% hit
100% hit

さな転送を 1 回行うだけである。またストアとの依存解決を待つ必要がなく、ストア値が判明した時点で値をロード命令の Consumer のノードにフォワーディングする。このため、非常に早いタイミングでロード命令の Consumer が演算

ROB size とはプロセッサの中に保持できる最大 IB 数である。ここでは 16 とした。Local Wireによる転送レイテンシは非常に小さいため、0 cy-tive Wire Promotion 及び Speculative Memory
Cloaking を実装したときの性能の変化を示し、評価を行う。

cle とした。ALU-Net と LSU、ALU-Net と Speculative Memory Cloaking の予測テーブルの間のネットワークレイテンシは等しいものとした。また、キャッシュと Speculative Memory Cloakingの予測テーブルの書き込み、読み出しのレイテンシも等しいものとした。なお、Speculative Memory Cloaking の予測テーブルのエントリ数及びキャッシュのサイズは無限大とし、キャッシュは100%ヒットするものとした。また、分岐予測は100%当たるものとした。

4.3.1

4.3.2可能になる。

4.3

Speculative Wire Promotionの評価

本 節 で は 、VLDP simulator3 に Specula-評価環境

VLDP3compiler でコンパイルした SPECint95のバイナリ 6 種類に 7 種類の train の入力を使い、トレースベースの VLDP3 simulator で評価を行った。VLDP3 compiler は、alpha をベースにした RISC 型命令列を最大 64 個まとめて 1IBとした。IB には ALU-Net への配置情報も静的に付加している。
シミュレーションモデルは第 3 章で述べた

VLDP3 の命令実行モデルと同様である。ただし、ここではモデルの基本的傾向を知ることを目的とするため、ALU-Net のトポロジは完全結合網を仮定した。完全結合網とは、ALU-Net内の全ての Node が他の任意の Node と Local

評価

次に図 8 にメモリリネーミングを行わない場
合、Speculative Wire Promotion を実装した場
合、理想的な Speculative Wire Promotion を実装した場合、Speculative Memory Cloakingを実装した場合、理想的な Speculative Mem-

ory Cloaking を実装した場合、Speculative Wire
Promotion と Speculative Memory Cloaking を両方実装した場合の各アプリケーションにおける IPC、及びその調和平均を示す。ここで言う
理想的な Speculative Wire Promotion とは、すべての IB 内メモリ依存についてストア値が判明し次第正しい値をロード命令の Consumer に Local Wire を用いて転送する機構であり、理想的な Speculative Memory Cloaking とは、Specu-5

lative Memory Cloaking の機構においてロード・ストア間のメモリ依存をすべて正確に予測してロードの Consumer への値の転送を行うものである。

用方式として Speculative Wire Promotion を

メモリリネーミングなし

6Speculative Wire Promotion実装
理想的なSpeculative Wire Promotion実装

5

Speculative Memory Cloaking実装
理想的なSpeculative Memory Cloaking実装

4

Speculative Wire PromotionとSpeculative MemoryCloaking実装
CPI

3

2

10

compressgoijpeg

lim88ksimperl(primes) perl(scrabbl)

harmonicmean

図 8: メモリリネーミングの実装と IPC の変化

おわりに
本稿では VLDP3 へのメモリリネーミング適提案し、Speculative Memory Cloaking と共に

VLDP3 simulator に実装して IPC の変化を計測し、評価した。
Speculative Wire Promotion は、IB 内メモリ依存に対してそのロード命令のキャッシュアクセスのレイテンシの大部分を隠蔽できることが示された。それに対して Speculative Memory Cloaking はある程度の性能向上は見られたものの、まだ性能向上の余地が残されており、今後予測精度の向上を検討する必要があることが分かった。

謝辞
本論文の研究は、一部、21 世紀 COE 情報技術戦略コア研究費によります。

参考文献
Speculative Wire Promotion を実装した場合には平均 22%程度の IPC の向上が見られる。理
想的な Speculative Wire Promotion を実装した場合との差は 4%程度である。Speculative Wire
Promotion ではストア値が判明し次第すぐに Local Wire を用いて値をロード命令の Consumerのノードに転送しており、図 6 に示すように、通常のキャッシュアクセスにおいてロード命令の Consumer にロード値を送る過程でのレイテンシの大部分を削減している。よって理想的なSpeculative Wire Promotion に近い IPC が実現できているということは、ストア命令と IB 内メモリ依存関係にあるロード命令のキャッシュアクセスのレイテンシを大部分隠蔽することができたと言える。
Speculative Memory Cloaking を単体で実装した場合では 14%程度の IPC の向上が見られるが、Speculative Wire Promotion と同時に実装しても大きな IPC の向上は見られない。これは、Speculative Memory Cloaking による依存予測がIB 間については外れやすく、高速化できている部分が Speculative Wire Promotion と重複しているためと考えられる。また理想的な SpeculativeMemory Cloaking との差が大きいという点でも依存予測があまり的中していないことが分かる。
そこで今後は、IB 間メモリ依存について依存予測の精度向上を検討する。

[1] 入江英嗣, 服部直也, 坂井修一, 田中英彦. ”VLDP3:
データフローを高速実行する大規模アーキテクチ
ャ”. 情報処理学会研究会報告 ARC 2003-ARC-151,Vol.2003, No.10, pp.49-54 (Jan. 2003)[2] 服部直也, 入江英嗣, 坂井修一, 田中英彦. ”VLDP3
アーキテクチャに対するコード生成の検討”. 情報処
理学会研究会報告 ARC 2003-ARC-151, Vol.2003,No.10, pp.55-60 (Jan. 2003)[3] 谷地田瞬, 山口健輔, 田中裕治, 服部直也, 入江英嗣,飯塚大介, 坂井修一, 田中英彦. ”VLDP3 アーキテク
チャの構想 (4)〜メモリ依存に関する初期検討〜”. 情
報科学技術フォーラム 2002 講演論文集 C-17. (Sep.
2002)[4] Andreas Moshovos and Guri Sohi.”Streamlining
Inter-operation Memory Communication via
Data Dependence Prediction”.In the Proc. ofMICRO-30. (Dec. 1997)[5] Andreas Moshovos and Guri Sohi.”Speculative
Memory Cloaking and Bypassing”.Invited. To
appear in the International Journal of Parallel
Programming.(Oct. 1999)[6] R.E.Kessler, E.J.McLellan, and D.A.Webb.”TheAlpha 21264 Microprosessor Architecture”.inInternational Conference on Computer Design.(Dec. 1998)[7] Mikko H.Lipasti, Christopher B.Wilkerson, andJohn Paul Shen.”Value Locality and Load ValuePrediction”.in 17th International Conference onArchitectural Support for Programming Languages and operating Systems, pp. 138-147.(Oct.
1996)[8] Brad Calder, Glenn Reinman.”A Comparative Survey of Load Speculation Architectures”.Journal of Instruction-Level Parallelism
1.(2000)