Vol. 0

情報処理学会論文誌

No. 0

1959

クラスタ型プロセッサのための分散投機メモリフォワーディング
入江 英 嗣†1,†2 服 部 直 也†1,†3 高 田 正 法†1
坂 井 修 一†1 田 中 英 彦†1,†4

クラスタ型アーキテクチャでは, 実行コアを複数のクラスタに分散し, 広い実行幅と高クロック動作の両立を目指している. クラスタ型アーキテクチャを前提とした様々な要素技術の研究が行われる
一方で, 分散処理の難しいメモリ参照命令がボトルネックとなることが指摘されている. 本研究では,
クラスタ型スーパスカラ・プロセッサのメモリ参照処理に着目し, 依存予測を用いたオーバヘッド隠蔽手法を提案する.

Distributed Speculative Memory Forwarding
for Clustered Superscalar Processors
Hidetsugu Irie,†1,†2 Naoya Hattori, †1,†3 Masanori Takada, †1
Shuichi Sakai†1 and Hidehiko Tanaka†1,†4
Clustered microarchitecture aims at coexistence of wider execution width and higher clock
rate by distributing execution core to clusters. While research of various techniques on theclustered microarchitecture is performed, it is pointed out that memory instructions are hardto distribute and become a bottleneck. In this paper, memory instructions processing of aclustered superscalar processor are focused and the technique that conceals memory reference
overhead by using dependence prediction is proposed.

1. 序

発行キュー レジスタ

論

発行キュー

情報処理の中核となるマイクロプロセッサには常にレジスタ

1cycle

性能向上が期待されている. マイクロプロセッサは,
デバイス微細化, スーパパイプライニング技術, 並列

1cycle

クラスタ化

クラスタ間
通信遅延
発行キュー レジスタ

実行技術によって性能を向上させてきた. しかし, 現行のスーパスカラ方式は, 肥大したデータパスに配線

図 1 クラスタ型実行コア
Fig. 1 Clustered Execution Core

遅延が大きく影響することが予想され, 性能向上の限界が指摘されている1) .
この問題に対し, 次世代プロセッサの選択肢としてる3),11) . クラスタ型プロセッサでは実行コアを複数の注目されている方式がプロセッサのクラスタ化であクラスタに分割し, 発行キュー, レジスタ, データパス
等を局所化する（図 1）. 処理が複数クラスタに分散†1 東京大学大学院 情報理工学系研究科
Graduate School of Information Science and Technology, University of Tokyo†2 現在, 科学技術振興機構
Presently with Japan Science and Technology Agency†3 現在, 日立製作所中央研究所
Presently with Hitachi, Ltd., Central ResearchLaboratory†4 現在, 情報セキュリティ大学院大学
Presently with Institute of Information Security

することによってオーバヘッドが生ずるが, タイミン
グ・クリティカルパスとなっていたユニットが小型化
し, 更なるスーパパイプライニング効果が期待できる.
このような利点を背景にスーパスカラ・プロセッサをクラスタ化した時, クラスタ化による恩恵を受けないメモリ参照処理の遅延は相対的に大きくなることが
1

予想される. メモリ参照遅延は現行のスーパスカラ・

プログラム

プロセッサでも主要なオーバヘッドとなっており, こStore aStore bStore cStore dLoad xの影響を無視してクラスタ化の有効性は議論できない.
本研究では高クロック指向のクラスタ型スーパスカ
ラ・プロセッサを想定し, メモリ参照処理オーバヘッ

実際の
依存関係

ドの増加について議論する. また, このオーバヘッ
ドの隠蔽手法として, 投機メモリフォワーディング技
術9),10),15) をクラスタ型プロセッサに適用した “分散投機メモリフォワーディング” を提案する. 提案手法

Store aStore cStore dRAWチェインWAWチェインStore boverhead

Load x

図 2 曖昧なメモリ依存のチェイン
Fig. 2 Ambiguous Dependence Chain of Memory

Instruction

では, メモリ依存予測と動的ステアリングを利用して,参照をクラスタ内に局所化する.

幅の活用が妨げられる可能性がある. 分散された発行

以下, 本論文の構成は次のようになっている. 第 2

キューを持つ方式では, 発行前に実行クラスタを選択

節では関連研究についてクラスタ型アーキテクチャとする必要があり, この選択を行うステアリングロジッ

メモリ参照処理の二つの点から紹介する. 第 3 節では

クが性能を大きく左右する. プロセッサのポテンシャ

クラスタ型スーパスカラ・プロセッサにおけるメモリ

ルを活用するためのステアリング手法の研究は様々に参照処理のオーバヘッドについて議論する. 第 4 節で行われている4),7),13),17),18) .

は, “分散投機メモリフォワーディング” を提案する.

2.2 メモリ参照処理の高速化
ロード命令は通常のレジスタ演算命令に比べてステージ数が長く, 更に, 曖昧なメモリ依存関係の影響を受け, 先行するストア命令が発行するまで発行できないため大きなボトルネックとなっている. このため,依存関係に注目してメモリ参照の高速化を目指す手法が提案されている.
2.2.1 依 存 予 測
メモリ参照命令の発行は, 依存のあるストア命令を追い越しては行われない. しかし, メモリ参照命令同

ここでは, メモリ参照を局所化するための戦略と, 高速性を損なわない実装方法について述べる. 第 5 節では提案手法の適用率と, 実行性能への影響を評価する.
第 6 節でまとめを述べる.

2. 関 連 研 究
2.1 クラスタ型スーパスカラ・プロセッサ
一般に実行並列幅を増加させると, 回路の複雑さが増し, 動作クロックは低下する. プロセッサ設計時には, 双方の最適なバランスを考慮しなければならない.
Palacharla ら11) は, 演算器のフォワーディングデー
タパスや発行キューについて回路レベルの解析を行い,
デバイス技術が進むほど, 実行幅を増やすことによるタイミング・クリティカルパスの増加が大きくなることを示している.
このため, 小さな発行幅の実行クラスタを複数接続して構成された, クラスタ型のプロセッサ構成が注目されている. 現行のプロセッサにおける例として, DEC
Alpha 212648) では, 実行コアを 2 つのクラスタに分士の依存関係は実行ステージまで判明しないため, フ割し, 高クロック化を図っている. 各クラスタには物のロード命令は実行中のストア命令に依存関係がない

ロントエンド処理における発行条件解析では, 予防的に全てのメモリ参照命令同士に依存関係を仮定しなければならない. この結果, 図 2 のような発行条件のチェ
インが形成される. 図 2 では, ロード命令は実際にはStore b にのみ依存があり, Store b が発行された後であれば, 正しい処理を行うことができる. しかし, その
情報はフロントエンド時点では判明しないため, ロー
ド命令の発行は Store a から始まるチェインが順番に解決する事を待たなければならない. 実際には, 多く

理レジスタと 2 つの演算器, 局所化されたデータパス

ことが知られており, 不必要な待機によってロード命が備わっている. 近年では, データパスだけでなく発令処理の遅延が増やされている.

行キューも局所化されたクラスタ型モデルが, 要素技

DEC Alpha 212648) では, ロード命令は基本的に実行中のストア命令と依存がないとして, 先行するスト
ア命令の有無に関わらず, オペランドが揃い次第投機的に発行される. 依存関係のあるストア命令を不当に追い越していたことが判明した場合はパイプライン・
フラッシュにより実行をやり直す. このとき, このロード命令の PC について 1 ビットのフラグを立て, 次回

術のベースライン・プロセッサとして利用されるようになってきた2),12) .
クラスタ型プロセッサでは, 各クラスタは高速に動作するが, 依存のある命令が異なるクラスタに割り当てられた場合, クラスタ間の通信遅延がオーバヘッドとなる. また, クラスタの負荷に偏りが生じると実行load PC, store PC

依存予測器

依存検出器
parentstore ID(for load)PC

発行条件へ追加

fetch

decoderenameissue

execute依存予測器

load PC, store PC(store set)Synonymstore ID Filevalue (for load)
PC
fetch

retiredecoderenameissue

store value

依存検出器

address

verifyexecuteretire

図 4 Moshovos らの手法
Fig. 4 Speculative Memory Cloaking

図 3 メモリ依存予測
Fig. 3 Memory Dependence Predicton

実行時からは投機を行わず, 先行するストア命令の発ドするために, Synonym File にストア命令のリザベー行を待つように制御する. このフラグは Wait Table

ションステーションへのポインタを保持するアイデアと呼ばれるテーブルに保持され, デコード時に参照さを示している. また, 更に積極的な手法として, ストれる. 一度のミスを元に投機が慎重になりすぎる事を

ア値を生成する “プロデューサ命令” からロード値を防ぐために, Wait Table は一定サイクル期間で全ての使用する “コンシューマ命令” へのフォワーディング

ビットが初期化される.

を行う, “Speculative Memory Bypassing” という手

更に精度の高いアプローチとして, ロード命令と依法を提案している.

存関係にある親ストア命令を予測する手法が提案され投機メモリフォワーディングを集中型のスーパスカている. この方式では, ロード命令の発行条件を, 予

ラプロセッサに適用した評価では, 全ロード命令の約測された親ストア命令に設定することで, 発行のタイ40%がフォワーディングの対象となる一方, IPC はミス・フォワーディングの影響により逆に 5.63%低下したことが示されている.

ミングを最速化することができる.
一度依存関係のあったストア命令とロード命令のPC 対は再び依存関係にある可能性が高く, 親ストア
予測はこの性質を利用する. 親ストア命令とロード命
令の PC 対の学習はリタイア時に行われ, 予測テーブ
ルが更新される（図 3）. Chrysos らのストア・セッ

3. メモリ参照処理によるオーバヘッド
3.1 クラスタ化によるオーバヘッドの増加
クラスタ型スーパスカラ・プロセッサでは, キャット予測5) では, ロード命令に過去依存のあった複数の

シュ, ストアキューなどのメモリ参照ユニットも分散ストア命令 (ストア・セット) を保持することによって局所化されることが自然であるが, メモリ参照命令は,予測の適用範囲を広げている.

依存関係が曖昧なため局所化が難しい. クラスタ型プ2.2.2 投機メモリフォワーディング
Moshovos ら9),10) の提案した “Speculative Memory Cloaking” は, 依存予測結果を利用し, 予測された親ストア命令のストア値をロード命令の実行結果として使用することにより, ロード命令の発行遅延とキャッ
シュ参照遅延の双方を短縮する. また同時期に Tyson
ら15) が同様の手法 “Memory Renaming” を提案してロセッサの先行研究では, クラスタ外にある集中型のいる. 図 4 に Moshovos らのモデルを示す.

ストア

キャッシュとストアキューが全てのメモリ参照を処理する方式で近似されている事が多い.
本節では, 集中型の D1 キャッシュ構成についてオー
バヘッド評価を行い, どの部分の高速化が求められているか解析する. 特に, 実行コアがクラスタ化されることにより, 傾向にどのような変化が現れるかに注目する.

命令実行後ストア値は Synonym File と呼ばれるバッ

メモリ参照処理のオーバヘッド要素は, 命令発行がファに書き込まれる. ロード命令はメモリ依存予測を遅れることによる発行遅延と, アドレス計算後の参照

利用して親ストア命令の ID を得, 更にその ID をキー遅延に分けて考えることができる.

として Synonym File から予測値を得る.
この手法ではストア命令のバックエンドで書き込ん

発行遅延は, ストア命令とロード命令の依存関係が完全には予測できないことから, ロード命令が不必要だ値を, ロード命令のフロントエンドで読み出すため,に発行を遅らされることによって生ずる. 曖昧なメモ

ストア命令とロード命令の実行タイミングが離れていリ依存チェイン（図 2）の解決は, クラスタ化によっなければフォワードできない. Moshovos らは実装のて更に遅れることが予想される. 依存があると予測さオプションとして, 実行中のストア命令からフォワー

れたメモリ参照命令同士が異なるクラスタに割り当てfrontend(fetch/decode/
rename)steering
logic

tag
forwardissue queue
register filecluster×8

表 1 ベースライン・パラメタ
Table 1 Baseline Parameters

data
forward

LSQ
D1
cache

issue queue
register filenumber of clusters
components ofeach cluster
fetch/retire width
I-cachebranch predictor
memory disambiguation

図5

シミュレーション・モデル
Fig. 5 Simulation Model

られた場合, メモリ発行条件の伝播にクラスタ間通信
遅延が伴うためである.
参照遅延は, 実行ステージにおけるアドレス計算終了後のメモリステージの長さである. 大きなキャッシュアレイの参照遅延に加えて, 実行ユニットとキャッシュの間の通信遅延等がオーバヘッドとなる. 配線遅延に

D-cachetotal pipeline depth
frontend latency
issue to issue latency
execute(int)
execute(int MULT)
execute(ﬂoat)
inter cluster forwarding

8
64entry IQ, 256physical registers
execute 1 instruction/cycle
up to16insts/cycle
perfect
gshare predictor
16k-entry, 10bit history
16k entry wait table,
100k cycle refresh interval
64kB, 2-waySA,
8cycle hit latency
64byte lines
3 read ports
1read/write port
16stages
11cycles1cycle1cycle15cycles4cycles2cycles

耐性のない要素であるため, 高クロック指向に設計された実行コア部分に比べて相対的に長い遅延を生ずるは, 実行ステージにおけるアドレス計算までは他の命ことが予想される.

令と同様にクラスタで処理される. その後, アドレス

3.2 評 価 環 境
評価は, 図 5 に示す構成の高クロック指向クラスタ型スーパスカラ・プロセッサをトレースシミュレータに実装して行った. 議論で用いるシミュレーション・
モデルの設定を表 1 に示す. 特に表記がない場合は,やストア値が D1 キャッシュ及びストアキューへ送ら

次節以降もこの設定を用いる.
シミュレーション・モデルは 1 命令実行幅のクラス
タ 8 個による構成となっている. それぞれのクラス
タは発行キュー, 複製されたレジスタファイル, ALU,
フォワーディングデータパスを持つ. 各クラスタは高速な動作が可能であるが, 異なるクラスタ間での実行結果の反映にはクラスタ間通信遅延の 2 サイクルを要する. メモリ参照に焦点を当てるため, クラスタのトポロジについては簡略化し, 任意のクラスタ間で一律の通信遅延を仮定している. クラスタの位置に応じて通信遅延が異なる場合のステアリング最適化は文献
13) で議論されている.
命令をどのクラスタで実行するかは, ディスパッチ
処理に加えられるステアリングロジックによって動的に決定される. ステアリングロジックには, 命令間の依存関係とクラスタ負荷分散の 2 つの指標を基に実行
クラスタを選択する Parcerisa 方式12) を用いた.
D1 キャッシュ及びストア・キューはクラスタ外に存在する集中型ユニットとなっており, 全てのクラスタ
におけるメモリ参照処理を処理する. メモリ参照命令

れ参照処理を行う. ロード命令の場合, アドレスを計算してからロード値を得るまでに, 往復の通信遅延やキャッシュアレイの参照遅延等の影響があり, 参照遅延を 8 サイクルに設定している.
シミュレーション・モデルの命令セットは DEC Alpha21264 に準じ, 実行トレースを入力とする. 評価には SPEC95int(train) から compress, gcc, go, ijpeg,
li, m88ksim, perl(jumble, primes, scrrable), vortexの 10 種類を用い, 先頭から最大 256M 命令について
動作を計測した.
3.3 ロード命令の発行遅延によるオーバヘッド
クラスタ型アーキテクチャにおけるロード命令の発行遅延オーバヘッドを評価するため, 現在用いられている Wait Table を用いたモデルと, フロントエンド
時に全てのメモリ依存が判明しているモデルとの性能比較を行った. Wait Table を用いたモデルは, 小容量の追加ハードウェアで実現可能だが, ロード命令の不正な追い越しによるパイプラインフラッシュが発生す
る, wait と判断されたロード命令が不必要に発行を遅らされる等のオーバヘッドが生ずる. 一方, フロントエンドで全てのメモリ依存が判明するモデルは理想モデルであり, ロード命令は, 親ストア命令の発行を的確に待ち, 最速のタイミングで発行される.
この比較を, 8 命令実行幅のユニット 1 つによる集

2
1.8
1.6
1.4
1.2
C
P 1
I
0.8
0.6
0.4
0.2
0

perfect memory
disambiguration
Wait Table

1.4
1.3
1.2
C
P
I

1.1
1
0.9

集中型

分散型

図 6 メモリ命令発行遅延を理想化したときの性能向上
Fig. 6 Performance Improvement of Perfect Memory
Disambiguration

0.8
1

2

3

4

5

6

D1キャッシュ参照遅延

7

図 7 D1 参照遅延を変化させたときの IPC
Fig. 7 D1 Access Latency vs IPC

中型の場合と, 1 命令実行幅のクラスタ 8 つによるク

り, 往復で 2 × 2 サイクルである. キャッシュアレイのラスタ型の場合でそれぞれ行った. 性能の指標には

参照遅延は配線遅延に耐性がないため, 現行の参照遅

総リタイア命令数を総実行サイクル数で割った, IPC

延より大きい 3 サイクルを仮定した. 更に, 複数クラ（Instructions Per Cycle）を用い, 10 種類のベンチ

スタから発せられる参照リクエストのポート調停に 1

マークについて調和平均を求めた.

サイクルを見込んでいる.

図 6 に, 評価結果を示す. ロード命令の発行遅延に

D1 参照遅延の大幅な増加が見込まれる上, 図 7 のよって, 性能が制限されていることが分かる. 集中型

ように D1 参照遅延は IPC にリニアに影響する要素とクラスタ型で同じ遅延パラメタを用いているため,となっていることから, クラスタ化によりメモリ参照

集中型の IPC が有利となっている.

遅延のオーバヘッドが増大することが予想される.

クラスタ型では, メモリ発行条件の伝搬に通信遅延

このように, クラスタ型スーパスカラ・プロセッサが加わるため, ロード命令発行遅延の影響が増大する.

におけるメモリ参照処理は, 発行遅延, 参照遅延双方

Wait Table の値と理想モデルの値との比率に注目す
ると, クラスタ型では集中型に較べて, オーバヘッドの影響が増大していることが確認できる.
3.4 参照遅延によるオーバヘッド
キャッシュの参照遅延は, フロアプランや回路最適化, デバイス世代等によって決定されるため, 正確に見積もることが難しい. そこで, ここでは参照遅延を 1
サイクルから 8 サイクルまで変化させ, センシティビ
ティに注目する. 性能指標には発行遅延と同じく IPCを用いた.

共に増大し, 性能を制限する事が予想される.

4. 分散投機メモリフォワーディング
クラスタ化によってメモリ参照のオーバヘッドが増大する主な理由は処理が分散することによる通信遅延である. クラスタ型スーパスカラ・プロセッサでは,
D0 キャッシュにあたる小容量のバッファをクラスタ内に設け, メモリ処理を局所化する手法が適していると言える.
このようなバッファの構成法はいくつか選択肢が考図 7 に D1 参照遅延を変化させた時の IPC の変化

えられ, それぞれに得失がある. 小容量の D0 キャッを示す. グラフはほぼ線形であり, D1 参照遅延が 1 サシュの複製を各クラスタが持つ方式の場合, 機構は単イクル減る毎に IPC が約 4%向上している.

純になるが, 複製のため, 容量効果が低い. また各ク

クラスタ化によって実行コアが高クロック指向にな

ラスタによる更新を反映させるためライトポートが多ると集中型 D1 の参照遅延は大きく増加することが予く必要となってしまう. 一方, アドレスでバンク分け想される. 例えば, シミュレーションモデルで設定しされたキャッシュをクラスタ内に持つ方式の場合, スている 8 サイクルは次のような概算から決定していテアリングが問題となる. また, これらの方式では予る. まず, クラスタと D1 との通信遅延が, クラスタ間

測スケジューリングや発行遅延の軽減が難しい.

通信遅延と同じ値であると仮定する. この遅延はロー

そこで本論文では小容量バッファを利用する別のア

ド命令の場合, アドレスの送信, ロード値の受信とな

プローチとして, 参照遅延, 発行遅延双方を改善する

8

依存予測器(store set)
PC
fetch

Fig. 8store IDload PC, store PC
store
bank

decoderename steerID
store value
issue LFB executeverifyID
store value
issue LFB executeverify依存検出器

address

依存予測器

store set

loadPC storePC

storePC

confidence
counter

LFSID steeredcluster

図 9 予測器 1 エントリの保持情報
Fig. 9 An Entry of Prediction Table

retire

図 8 分散投機メモリフォワーディング
Distributed Speculative Memory Forwarding

メモリ依存が学習される. 予測器の保持内容は図 9 のようになっている.

依存予測器のエントリはロード

命令の PC について 1 対 1 に作成される. 各エントリにはロード命令の PC, そのロード命令に過去依存の投機メモリフォワーディング技術に注目し, 予測スケあったストア命令, 確信度カウンタ, 最後にフェッチさ

ジューリングを行うクラスタ型スーパスカラ・プロセッ

れた該当ストア命令の ID(LFSID) とそのステア先が保持される. メモリ依存の履歴の中では, 一つのローサへの適用を考える.

4.1 提案手法の概要
クラスタ内小容量バッファを投機メモリフォワーディ
ングに用いるための, フォワーディング局所化手法をド命令に複数のストア命令が依存関係を持つ可能性があり, 過去依存のあったストア命令は, ストア・セット
として保持される.

提案する. また, クラスタ型スーパスカラ・プロセッサ

LFSID はストア命令のフロントエンド処理時に更では実行中の命令が多いため, 実行中のストアからの新される. メモリ依存予測器をストア命令の PC につフォワードは必須となる. 先行研究における実行中ス

いて参照し, 該当する PC を含んでいるエントリが存

トアからのフォワーディングのアイデアは, リザベー在した場合には, そのエントリの LFSID にこのスト

ションステーションを想定したデータ駆動的なものでア命令の ID を保持する. また, このストア命令が割あった. 本論文では, 高クロック指向のプロセッサにり当てられたクラスタ番号を保持する. 予測器エント

おける投機メモリフォワーディング制御を提案する.

リはロード PC に対して 1 対 1 に作られるため, 複数

提案手法である “分散投機メモリフォワーディング”のロード命令の親にあたるストア命令では, 複数のエの概念図を図 8 に示す.

ントリが該当する場合がある. このため, この操作は提案手法ではフォワードされるストア値は, 各クラスタ内のローカルフォワード

全エントリを対象として行われる.

バッファ（図 8 中の “LFB”）に保持され, 同じクラス

予測器にエントリが存在したストア命令は, その後

タに割り当てられたコンシューマ命令からのみ参照さの処理でローカルフォワードバッファにストア値と命れる. また, 発行キューを拡張して, ストア命令の発行

令 ID の保持を行うように制御される.

を監視し, 最速のタイミングのフォワーディング制御

一方, ロード命令のフロントエンド処理時に, 予測を行う. フォワーディング制御はクラスタ内に局所化

テーブルをロード命令の PC について参照することにされ, 通信遅延やポート競合の影響を受けない.

より, 親と予測されるストア命令の動的 ID とステア先更に, ステアリングロジックでメモリ依存予測情報

クラスタを得る. 確信度カウンタにより投機可能と判を利用することにより, 局所化されたフォワーディン

断されれば, そのロード命令について投機メモリフォ

グ機構を支援する.

ワーディングを行う.

4.2 メモリ依存予測機構
依存のあるストア命令とロード命令を予測する予測機構には関連研究5),10) と同様の機構を用いる. 予測
機構は大きく検出器と予測器に分けられ, それぞれリ
タイア処理とフロントエンド処理に追加される. フロ
ントエンド処理やバックエンド処理の増加は, 実行のクリティカルパスとなりにくいため, 一般に実行性能にそれほど影響しない11),14) .
検出器では, 参照アドレスを比較することで, メモ
リ依存の検出を行う. 検出結果は予測器に保持され,投機メモリフォワーディングの適用となったロード
命令の値は, ローカルフォワードバッファを親ストア

ID について参照することにより, 高速に得ることができる. フォワーディング制御については後述する.
予測器エントリには確信度カウンタが設けられ, ミスフォワーディングを起こした場合インクリメントされる. この値が閾値を越えると, 予測は適用されない.
予測適用が慎重になりすぎる事を避けるために, 確信度カウンタは一定期間でリフレッシュされる.

consumer PC

レジスタ依存解析
load PC

LSQ

cluster

親store ID
親store ステア先
ステア先の決定

メモリ依存予測

D1
cache

register fileUcluster

local forward buffer

store ID value
store ID value

X

issue queue

Local Forward
BufferM

issue queue

store ID value
store ID value

store ID value
store ID value

extention

tag forward to other nodes

図 10 依存予測を利用したメモリ参照の局所化
Fig. 10 Memory Access Localization with Dependence

Prediction

4.3 フォワーディングの局所化
分散投機メモリフォワーディングでは, メモリ依存予測情報を利用して, メモリ依存関係にある命令を同じクラスタへ割り当てる（図 10）.
ステアリング時に, メモリ依存予測テーブル（図 9）を参照することで, 親ストア命令の割り当て先のクラ

図 11 フォワーディング機構の構成
Fig. 11 Components of Forwarding Mechanism

extension

speculative
ready bitparentSTID

speculative
ready bitparentSTID

speculative
ready bitparentSTID

スタ番号を得ることができ, コンシューマ命令は親ス
トア命令と同じクラスタへ割り当てられる. と同じクラスタを選択する. 他の命令は, 通常通りのステアリ
ングロジックに従う.

tag from other nodes

=
=

=
=

=
=

sourceoperand L

ready
bit

sourceoperand L

ready
bit

sourceoperand L

ready
bit

s
e
l
e
c
t
l
o
g
i
c

Rも

同様

tag broadcast
issue

このステアリングを利用することにより, クラスタ

図 12 発行キューの拡張
Fig. 12 Extension of Issue Queue

内のみから参照される高速なバッファを介して投機メ
モリフォワーディングを行うことが可能となり, 高速
参照, 小ポート, 容量効果等, 分散局所化の利点を得る
事ができる. また, メモリ発行条件の伝播にクラスタなる条件は, i）ソースレジスタに書き込むロード命令

間通信遅延が加わる影響を抑える事ができる.

が発行され, 予測される参照遅延分のサイクルが経っ

一方, 欠点として, ステアリングの自由度を下げてた場合（正規 wake up）, ii）ソースレジスタに書きしまう点が挙げられる. しかし, メモリ参照命令はク込むロード命令の親ストア命令が発行された場合（投リティカルパスとなりやすく, メモリ参照に重点を置

機 wake up）, の二通りが可能となる. この ii）の条

いたステアリングを優先する事が性能向上につながる件を監視するために, 発行キューを図 12 のように拡と考えられる.

張し, コンシューマ命令の発行条件に親ストア命令を

なお, フォワーディング制御に関して, 本研究では,
ロード命令のディスティネーションに値をフォワード

関連付ける.
ストア命令は発行されると, オペランドを読み出し,するのではなく, コンシューマ命令のソースへ値をフォ

クラスタ内でアドレス計算を行い, ストア情報をクラワードする実装を考える. この実装は, ローカルフォ

スタ外部のキャッシュ階層へ転送する. また, フォワー

ワードバッファの参照のタイミングをレジスタと同様

ドのソースとなるストア命令の場合は, ストア値を命の制御にすることができ, 発行スケジューラとの親和

令 ID と関連付けてローカルフォワードバッファへ書

性が高い.

き込む.

4.4 フォワーディング機構
図 11 に分散投機メモリフォワーディング機構を備えたクラスタのブロック図を示す. 追加されたハード
ウェアは, ローカルフォワードバッファとその参照のためのデータパス, 及び親ストア命令の発行を監視するための発行キュー拡張である. 提案手法を導入した場合, コンシューマ命令のオペランドについて, ready と一方, ストア命令の発行はコンシューマ命令から監視されており, 投機 wake up の条件となる. 投機 wakeup 状態で発行された命令は, オペランドをローカル
フォワードバッファまたはフォワーディングデータパ
スから読み出し, 演算を行う. 演算結果はレジスタに書き込まれ, 後続の命令から参照される. なお, 投機
wake up 状態は, ソースレジスタ値が利用可能となっa)close casestore inst.

ISSUEb)distant casestore inst.

ISSUE

REG
READ

EXE
CUTE

REG
READ

EXE
LFB
CUTE WRITE

data
tag
speculative forward
forwardwake upREG
EXE
ISSUE READ
consumer inst.
CUTE

tag
forwardconsumer inst.

LFB
scoreboard

speculative
wake upDISPATCH ISSUE

LFB
READ

EXE
CUTE

図 13 提案手法によるパイプラインタイミング
Fig. 13 Pipeline Timing with Forwarding

表 2 予測機構パラメタ
Table 2 Predictor Parameters
依存検出器エントリ数
依存予測器エントリ数

128
4k

） 45%
40%
数
ドー35%
ロ30%
行25%
実20%
全
/（ 15%
率10%
用 5%
適 0%

predicted
forwarded
yr
t
n
e
1

yr
t
n
e
2

yr
t
n
e
4

yr
t
n
e
8

yr
t
n
e
6
1

yr
t
n
e
2
3

yr
t
n
e
4
6

yr
t
n
e
8
2
1

図 14 ローカルフォワードバッファのサイズとフォワード率
Fig. 14 Forwarding Coverage versus Local Forwad Buﬀer
Size

もミスを起こしたロード命令には以降フォワーディン
グを適用しない. ただし, 10 万サイクル毎に全てのエた後は通常の wake up 状態に上書きされる.
ロード命令は通常のタイミングで発行され, キャッ

ントリについて一斉に確信度カウンタのリフレッシュを行い, 値を 0 に戻す.

4.5 提案手法によるゲイン
メモリ依存予測に基づく投機フォワーディングが成功した場合のパイプラインを図 13 に示す. 提案手法

5.1 提案手法の適用率
参照遅延やフロアプランの面から, ローカルフォワー
ドバッファのエントリ数を少なく抑えられることが望ましい. 一方, ローカルフォワードバッファのエントリ数が少なすぎると, ストアの書き込んだ値がコンシューマによって取得される前に上書きされてしまう. 図 14にローカルフォワードバッファのエントリ数とフォワー

では, メモリ依存予測に基づいてコンシューマ命令がド適用率の関係を示す. グラフの点線は予測の適用さ発行され, ロード命令発行遅延の影響を軽減する. メ

れたロード命令の数を全実行ロード命令で割った値でモリデータはクラスタ内のフォワーディングデータパ

あり, 35%程度のロード命令について親ストア命令予

シュ参照処理を行い, 投機フォワーディング結果が正しかったかをチェックする. 間違った値を後続命令に渡していた場合は, コンシューマ命令以降をパイプラ
インフラッシュする.

ス（図 13（a））或いはローカルフォワードバッファ測が適用されていることが分かる. この値がフロント（図 13（b））から取得される. ローカルフォワード

エンドにおける予測適用率である. 一方, 菱形でプロッバッファの参照遅延は小さく, レジスタ参照が並行しトした線が, ローカルフォワードバッファから値を得てて行われるため隠蔽される. また, メモリ依存予測に正しく実行されたコンシューマ命令の数であり, 同じ

従って, 親ストア命令とコンシューマ命令が同じクラく全ロード命令に対する割合で表している. この値にスタへステアされ, クラスタ間通信遅延のオーバヘッ

含まれているフォワードは性能向上に直接寄与する適ドを軽減する. これは, 通常のレジスタ依存関係に注用率を示している. 依存予測が成立していても, ロー

目したステアリングでは得られない効果である.

ド命令とコンシューマ命令の距離が離れていると, コ

5. 提案手法の評価

ンシューマ命令がディスパッチされた時点で既に先行

3 章で用いたクラスタ型スーパスカラ・プロセッサ

合は投機フォワーディングよりも通常のレジスタリーのロード処理が完了している可能性があるが, この場に, 分散投機メモリフォワーディングを実装し, シミュ

ドが優先され, フォワーディングが成立しないためでレータによる評価を行った. 依存予測機構パラメタは,ある. このグラフでは, ローカルフォワードバッファ

シミュレーションによって調べた最適なものを用いた.

エントリ数が増加するとフォワード率も上昇し, 逆に

表 2 にパラメタを示す. また, 確信度カウンタの動作予測適用率は下がっている. フォワード率の上昇は容は, シミュレーション結果による知見から, 以下のよ

量効果であり, 32 エントリでほぼ飽和, 64 エントリでうな動作を採用した. まず, 閾値を 1 に設定し, 一度で最大値となっている. これは D1 キャッシュと比較し） 0.40%
数0.35%
ドー0.30%
ロ
行0.25%
実0.20%
全/（ 0.15%率0.10%
ドー0.05%
ワ0.00%
ォ
フ
・
ス
ミ

1.4

)e 1.2
nli 1
es
ab 0.8/( 0.6
CPI
対0.4
相0.2
yr
t
n
e
1

yr
t
n
e
2

yr
t
n
e
4

yr
t
n
e
8

yr
t
n
e
6
1

yr
t
n
e
2
3

yr
t
n
e
4
6

0

yr
t
n
e
8
2
1

図 15 LFB サイズとミス・フォワード率
Fig. 15 Miss Forwarded Ratio versus Local Forward
Buﬀer Size

ryt
n
e
1

ryt
n
e
2

ryt
n
e
4

ryt
n
e
8

ryt
n
e
6
1

いった非常に小容量の構成でも良好な適用率を示して

1.6

いる. 一方, 予測適用率が下がる原因は, フォワード率

1.5

度カウンタによる判定が慎重になり, 不必要に予測適用を止めてしまうケースが増えるためである. 全ロー
ド命令に対するミス・フォワード回数の割合を図 15 に

1.3
C
P
I

1.2
1.1
1
0.9

しまい, パイプラインフラッシュを発生させてしまう

0.8

5.2 性能への影響
図 16 に LFB サイズと IPC の関係を示す. IPC は,

ryt
n
e
8
2
1

分散投機メモリ
フォワーディング
ベースライン

1.4

示す. 間違った予測に基づいてフォワーディングして確率は全実行ロード命令に対し 0.35%程度であった.

ryt
n
e
4
6

図 16 LFB サイズと提案手法の効果
Fig. 16 Eﬀect of Forwarding versus Local Forward Buﬀer
Sizeて十分に小規模であり, また 4 エントリ, 8 エントリとの上昇に伴ってミス・フォワード率も増えるため, 確信

ryt
n
e
2
3

1

2

3

4
5
D1参照遅延678

図 17 D1 キャッシュレイテンシと提案手法の効果
Fig. 17 Eﬀect of Forwarding versus D1 Cache Latency

同じプロセッサ構成で分散投機メモリフォワーディン
グを適用しなかった場合に対する相対 IPC で示している. 提案手法により, このプロセッサ構成では 28%程

一方, D1 参照遅延が 1 サイクルの設定でも提案手の IPC 向上を見込める事が分かる. また, エントリ数

法は 16%の性能向上を得ている, 依存予測に基づくスが少ない時でも IPC 向上を得ている.

テアリング及び発行によって, 発行遅延が改善してい次に 3 節と同様に, キャッシュ参照遅延を 1 サイクルから 8 サイクルまで変化させたときの IPC の様子

ることが分かる.
提案手法は, メモリ参照命令の主要なオーバヘッド

を図 17 に示す. 四角でプロットした線はベースライである発行遅延と参照遅延の双方を改善し, 性能向上

ンプロセッサにおける IPC であり, 菱形でプロットしに効果があると言える. また非常に少ないバッファ容

た線は, 同じプロセッサモデルに分散投機メモリフォ

量でも効果が高い特徴がある.

ワーディングを適用した場合の IPC である.

5.3 クラスタ台数効果の改善
図 18 に実装するクラスタ台数と IPC の関係を示す. 1 命令幅の実行クラスタ 1 個の構成から 16 個接続した構成まで変化させ, IPC を調べた. プロセッサの動作モデルや遅延パラメタは 3 節, 5 節で使用したものと同じ値になっている. この比較では, メモリ参照処理に焦点を当てるため, クラスタ間通信遅延を 2サイクルに固定して単純化している. 実際はクラスタ台数が増えると一般にクラスタ間通信遅延が増加する

フォワーディングにより参照遅延が改善するため,

D1 参照遅延が大きくなるほど, フォワーディングを利用する効果が大きくなっている. 8 サイクルの D1 参
照遅延では分散投機メモリフォワーディングを適用することにより 28%の性能向上を得ている. グラフの傾きに注目すると, 提案手法を適用した場合の方が傾きが緩く, D1 参照遅延が増加することによる性能低下に耐性があることが分かる.

ミュレータを用いて評価を行い, フォワード用のバッ

ideal setting

3.5

ファは小エントリで構成できることを示した. また,baseline setting+ memory ideal
baseline setting+ dSMFbaseline setting

3
2.5

発行の早期化と参照の高速化双方が性能の向上に影響していることを示した.
一方, ステアリングの制約にメモリ依存を加えるこ

2とによる自由度の低下がどのような悪影響を与えるか,

C
P
I

1.5

最適なステアリングロジックの観点から評価する必要がある. これらの提案, 評価は今後の課題である. ま1

た, クラスタ間遅延の厳密な評価や, 本手法で導入し0.5た発行キューの拡張による, タイミング・クリティカ0

ルパスの増加等, 回路的な解析も今後の課題である.
1

2

4

クラスタ台数816

図 18 クラスタ台数と IPC
Fig. 18 IPC versus Number of Cluster

ため, 台数効果は, 図 18 よりも悪化する.
菱形でプロットした “ideal setting” の線はクラスタ化によるオーバヘッドとメモリ参照によるオーバヘッ
ドを理想化した場合の IPC であり, シミュレーション
したパイプライン構成における並列性抽出のほぼ限界点を示している. 理想化設定は, クラスタ間通信遅延

0 サイクル, 集中型の発行キュー, メモリ依存関係を
フロントエンド時点で取得, キャッシュ参照遅延 1 サ
イクル, となっている. 次に, 三角形でプロットした“baseline setting + memory ideal” の点線は, メモリ
参照処理に関する, 発行遅延と参照遅延のオーバヘッ
ドを理想化した場合の IPC である.
これらの値に比べて, 現実的な設定である “baseline” の線は性能が大きく乖離している. 台数効果は 2
クラスタ構成でほぼ飽和し, 8 クラスタ以上では逆に性能低下を招いている. 分散投機メモリフォワーディ
ングを導入することにより, 台数効果は改善し, 4 クラスタから 8 クラスタまでの性能向上を達成している.

6. 結

論

スーパパイプラインの限界を押し上げるクラスタ型構成が注目されているが, メモリ参照処理が高速化に追随できず, ボトルネックとなる可能性がある. 本論
文では, 高速な実行コアと長い通信遅延を持つクラス
タ型スーパスカラ・プロセッサを仮定し, メモリ参照
処理のオーバヘッドを調べた. また, 投機メモリフォ
ワーディングの考え方を利用し, ロード命令発行の早期化と参照の局所化を実現する, 分散投機メモリフォ
ワーディングを提案した. 提案手法はストア依存予測を利用してステアリングを行い, 効果を高めている. シ

謝辞 本論文の研究は, 一部, 21 世紀 COE 「情報技術戦略コア」による.

参

考

文 献

1) V. Agarwal, M. S. Hrishikesh, S. W. Keckler,
and D. Burger. Clock Rate versus IPC:TheEnd of the Road for Conventional Microarchitectures. 27th Int.Symp.on Computer Architecture, pp. 248–259, 2000.
2) R. Balasubramonian, S. Dwarkadas, andD. H. Albonesi. Dynamically Managing theCommunication-Parallelism Trade-oﬀ in Future Clustered Processors. 30th Int.Symp.on
Computer Architecture, pp. 275–286, 2003.
3) R. Canal, J. M. Parcerisa, and A. Gonzalez. A Cost-Eﬀective Clustered Architecture.
Int.Conf.on Parallel Architectures and Compilation Techniques, pp. 160–168, 1999.
4) R. Canal, J. M. Parcerisa, and A. Gonzalez.
Dynamic Cluster Assignment Mechanisms. 6th
Int.symp.on High-Performance Computer Architecture, pp. 132–140, 2000.
5) G. Z. Chrysos and J. S. Emer. Memory Dependence Prediction using Store Sets. 25th
Int.Symp.on Computer Architecture, pp. 142–
153, 1998.
6) B. Fields, S. Rubin, and R. Bodik. Forcusing
Processor Policies via Critical-Path Prediction.
28th Int.Symp.on Computer Architecture, pp.
74–85, 2001.
7) R. Kessler. The Alpha 21264 Microprocessor.
IEEE Micro, Vol. 19, No. 2, pp. 24–36, 1999.
8) A. Moshovos and G. Sohi. Streamlining Interoperation Memory Communication via Data
Dependence Prediction. 30th Int.Symp.on Microarchitecture, pp. 235–245, 1997.
9) A.Moshovos and G.Sohi. Speculative Memory
Cloaking and Bypassing. International Journalof Parallel Programming, 1999.
10) S. Palacharla, N. P. Jouppi, and J. E. Smith.

Complexity-Eﬀective Superscalar Processors.
24th Int.Symp.on Computer Architecture, pp.
1–13, 1997.
11) J. M. Parcerisa and A. Gonzalez. Reducing
Wire Delay Penalty through Value Prediction.
33rd Int.Symp.on Microarchitecture, pp. 317–
326, 2000.
12) J. M. Parcerisa, J. Sahuquillo, A. Gonzalez,
and J. Duato. Eﬃcient Interconnects for Clustered Microarchitectures. Int.Conf.on Parallel
Architectures and Compilation Techniques, pp.
291–390, 2002.
13) J. Stark, M. D. Brown, and Y. N. Patt.
On pipelining dynamic instruction scheduling
logic. 33rd Int.Symp.on Microarchitecture, pp.
57–66, 2000.
14) G. Tyson and T. M. Austin. Improving theaccuracy and performance of memory communication through renaming. 30th Int.Symp.on
Microarchitecture, pp. 218–227, 1997.
15) 服部直也, 高田正法, 岡部淳, 入江英嗣, 坂井修
一, 田中英彦. クリティカルパス情報を用いた分散命令発行型マイクロプロセッサ向けステアリン
グ方式. 情報処理学会論文誌コンピューティング
システム (ACS-6), pp. 12–22, 2004.
16) 服部直也, 高田正法, 岡部淳, 入江英嗣, 坂井修
一, 田中英彦. 発行時間命令差に基づいた命令ス
テアリング方式. 先進的計算基盤システムシンポ
ジウム 2004(SACSIS2004), pp. 167–176, 2004.
(平成 ? 年 ? 月 ? 日受付)
(平成 ? 年 ? 月 ? 日採録)

高田 正法（学生会員）

1979 年生. 2003 年東京大学工学部電子情報工学科卒業. 現在, 同大学
院情報理工学系研究科電子情報学専
攻修士課程在学中. プロセッサアー
キテクチャなどの研究に従事.

坂井 修一（正会員）
昭和 56 年東京大学理学部情報科学科卒業. 昭和 61 年同大学院工学系研究科情報工学専門課程修了. 工学博士. 同年工業技術院電子技術総合研究所入所. 平成 3 〜4 年, 米国
マサチューセッツ工科大学招聘研究員, 平成 5 〜8 年

RWC 超並列アーキテクチャ研究室室長. 平成 8 年筑波大学電子・情報工学系助教授. 平成 10 年東京大学大学院工学系研究科助教授, 平成 13 年同大学院情報理工学系研究科教授. 計算機システム一般, 特にアーキ
テクチャ, 並列処理, スケジューリング問題, マルチメ
ディア応用などの研究に従事. 著書「論理回路入門」,「図説コンピュータアーキテクチャ」. 電子情報通信学会, 人工知能学会, IEEE , ACM 各会員.

田中 英彦（正会員）
昭和 40 年東京大学工学部電子工学科卒業. 昭和 45 年同大学院工学入江 英嗣（正会員）

1975 年生. 1999 年東京大学工学部電子情報工学科卒業. 2004 年同
大学院情報理工学系研究科電子情報学専攻博士課程修了. 博士（情報理工学）. プロセッサアーキテクチャなどの研究に従事.

系研究科博士課程修了. 工学博士.
同年同大学工学部講師. 昭和 46 年
同助教授. 昭和 62 年同教授. 平成

13 〜16 年東京大学大学院情報理工学系研究科教授・研究科長. この間昭和 53 〜54 年米国ニューヨーク市
立大学客員教授. 平成 16 年より情報セキュリティ大
学院大学情報セキュリティ研究科教授・研究科長. 計
算機アーキテクチャ, 並列処理, 自然言語処理, メディ
ア処理, 分散処理, CAD 等の研究に興味を持ってい服部 直也

る. 著書「非ノイマンコンピュータ」, 「情報通信シ

1976 年生. 1999 年東京大学工学部電子情報工学科卒業. 2004 年同
大学院情報理工学系研究科電子情報学専攻博士課程修了. 博士（情報理工学）. プロセッサアーキテクチャなどの研究に従事.

ステム」, 「Parallel Inference Engine -PIE-」, 共著
書「計算機アーキテクチャ」, 「VLSI コンピュータ

I,II 」, 「ソフトウェア指向アーキテクチャ」. 本会
フェロー. 電子情報通信学会, 人工知能学会, 日本ソフトウェア科学会, IEEE , ACM 各会員.