VLDP3 アーキテクチャにおけるレジスタ値の高速 Forwarding 手法の提案

田中 裕治 †

入江 英嗣 †

服部 直也 †

坂井 修一 †

田中 英彦 †概要
次世代アーキテクチャ VLDP3 は、多数の ALU を規則的に配置し 、ALU 間でデータフローを直接実行する。ALU 間は低レ イテンシでデータ転送できる仕組みを取り入れる。しかしレジスタを介したデータ転送はスイッチング・ロジックの複雑さなどの影響によりレ イテンシの増大を引き起こす。本稿
では、ALU とレジスタ間でのアクセス・レ イテンシの増加を抑えるため、多数 ALU 間で Forwardingを行い、レジスタを介さないレジスタ値転送機構を提案する。多数 ALU で構成された実行機構において効率的な Forwarding 機構を提案し 、シミュレータによる評価を行った。

Register Forwarding Mechanisms
on VLDP3 Architecture

Yuji Tanaka§
Hidetsugu Irie§
Naoya Hattori§
Shuichi Sakai§
Hidehiko Tanaka§

AbstractThe next-generation architecture VLDP3 has many ALUs in order, and directly executes dataﬂow
with ALUs. VLDP3 transfers data among ALUs with low latency, but data communication withregister unit increases latency because of the complexity of switching logic, and so on. In this paper,in order to decrease register access latency among ALUs and register unit, we proposed register
forwarding mechanisms among many ALUs which don’t access register unit, and evaluated themby simulation results.

1

はじめに半導体技術の進歩によって半導体プロセスが微細化し 、チップ上に多数の資源を使用することができるようになった。しかしプロセスの微細化に伴って配線遅延の影響を無視できなくなるなど 、性能低下を招く新たな要因を考慮する必要が出てきた。そのため近年では 、性能のト
レード オフを考えた新しいプロセッサ・アーキテ
クチャとして、多数の ALU で構成された実行機構を持つ VLDP3 などが研究されている [6]。
多数 ALU を規則的に配置した ALU-Net 構造
では、ALU-Net にデータフローを割り当てて直接実行する [6]。この方式を使うと ALU 間のデータ転送が低レ イテンシで行えるが 、レジスタからデータを読み書きするためのレ イテンシが相対的に増大してしまう。従来手法を使ってレジスタを介さない Forwarding を ALU 間で行えば 、レ イテンシの増加が抑えられる。しかし 任意のALU 間で Forwarding を行おうとするとロジックが複雑化してし まい、レ イテンシ削減は難しくなってしまう。そこで、多数 ALU で構成され† 東京大学

§ Graduate School of Information Science and Technology, University of Tokyo

た実行機構に適した Forwarding 機構を考える必要が出てくる。
本稿では、VLDP3 の実行機構とレジスタ機構の概略を述べ、レジスタ依存によって生じ るレイテンシを抑えるメカニズムを考えていく。従
来手法の問題点をまとめ、VLDP3 のような多数演算器構成の実行機構において 、多数の演算器間でレジスタ値を Forwarding するための手法を提案し 、その機構をシミュレータに実装して評価する。

2

VLDP3 の概要

本章では VLDP3 アーキテクチャの概要について実行機構を中心に述べる。

2.1

ALU-Net の構成とネット ワーク

VLDP3 の実行機構は、複数の Node を規則的に並べ、各 Node 間を短い配線 (Local Wire) で結合した ALU-Net である。Node は演算処理を行う最小単位で、ALU(演算ユニット ) と制御ロジックから成る。各 Node のロジックは小規模かつ単純であるため、ALU-Net を大規模化しても複雑化が抑えられる利点がある。

ALU-Net のモデルを図 1 に示す。各 Node は、ALU と Operand Buﬀer 、そし て 小規模な Issue Logic から成る。IB は多重実行されるため、Operand Buﬀer は小規模なリザベーション・ステーションの役割を果たす。Issue Logic は命令の発火を制御する。発火された命令から順に演算を行い、演算結果を Router を通して次の Nodeへと転送する。各 Node 間を結ぶ Local Wire は短い配線で 、配線遅延の影響を受けにくい。な
おかつ単純なロジックで制御されるので 、低レイテンシのデータ転送を可能にする。次の Nodeを繋ぐ 配線は図のように 3 本に限定したものを想定する。
NodeALU-Net
Node Node Node Node
Node Node Node Node

渡しされるデータの 2 つのデータ転送に分類できる。できるだけ多くのデータ転送を IB 内だけに閉じ 込められれば 、IB 内と外とで別々のデータ転送手法を取り入れることで 、局所性を利用した高速な転送が可能になる。
IB にはコンパイラによって IB 内データフロー
グラフ (DFG) の情報が 付加され る。この情報
は 、ALU-Net 内のど の Node へ命令を割り当てる (Assign) かという配置情報になっており、命令を割り当てられた Node ではこのデータフロー
グラフの情報にもとづいた演算を行う。また、処理を IB 単位にすることで、数十命令の単位でレジスタ・リネーミング処理を行うため、レジスタでの処理を単純化できる利点がある。

0 Operand
1 Buffer
23IssueALU

Node Node Node NodeLocal
Wire

Router2.3

レジスタ管理ユニット

ALU-Net にレジスタ値を供給し 、書き込み処理を管理するユニットをレジスタ管理ユニット(RWU: ReadWriteUnit) と呼ぶ。RWU では IBを単位として命令間の依存関係を解析し 、レジスタ・リネーミング処理を行う。

図 1: ALU-Net と Node の構成

ALU-Net 上にデータフローを形成する様子を
図 2 に示す。命令 I1 と I2 はレジスタ R0〜R2 を読み込み、R6 へ書き出す。各 I1〜I4 の演算結
果はそれぞれ Local Wire を使って受け渡しされるので、低レ イテンシな転送が可能となる。一方の ALU-Net とレジスタ・ユニットを繋ぐネッ
トワークの配線を Global Wire と呼ぶ (図 2(右)太線)。

Register Files

R2

R1

R0
I1

I1
I2
I2

I3

I3

R6I4I4

図 2: DFG(左) とアサイン後の ALU-Net(右)2.2IB 単位の処理方式

複数の命令列を静的に切り分け、IB (Instruction Block) という塊を構成する。命令を IB 単位にクラスタリングすることで、IB の中だけで受け渡しされるデータと、別の IB との間で受けIB Fetch
IB Decode
IB AssignRead

Read要求の場合
Renaming/依存解析

レジスタ・アクセス

Write

RWU

Write要求の場合
Renaming/依存解析

レジスタ・アクセス

図 3: RWU へのアクセス要求

RWU での動作を図 3 に示す。レジスタ読み込
み命令の場合は RWU 内でリネーミングと依存を解析して該当する Node へレジスタ値を転送する。レジスタ書き込み命令の場合にも同様に
RWU 内でリネーミング処理と依存解析を行い、ALU-Net からレジスタ値を受け取る。RWU はレジスタアクセス要求と共に命令の座標情報をIB Decode ステージから受け取っているので、レジスタ値を必要な Node へ直接転送できる。

2.4

実行モデル

IB 実行のモデルを図 4 を用いて説明する。実行前処理は IB 単位で Fetch 、Decode 、Assign の順に実行される。レジスタ・アクセスはリネー
ム処理が 終わると Global Network を経由してALU-Net へ転送され 、オペランドが揃った命令から順に発火する。演算結果は RWU へ出力される。IB 内の演算がすべて終わると ALU-Net 上から IB が ﬂush される。命令が例外を起こさず、かつ直前の IB の Retire を確認すると IB Retire

を開始する。

InstRWUIBIBIBIBFetch Decode Assign Execute 演算
RWU
GlobalReadReq NetworkIB
RetireRWU
GlobalNetwork WriteReq

Write
Backtime

図 4: IB の実行モデル

データ依存の分類

3

ALU-Net 方式では、IB を境界としてデータの依存関係が 2 つ存在する。ただし本稿でデータと言った場合にはレジスタ値のことを指し 、メモリについては関連研究 [8] で述べられている。
ここで 2 つの依存関係をまとめる。
1. IB 内データ依存
IB 内の命令間に真の依存関係がある場合で、これを IB 内データ依存と呼ぶ。IB 内デー
タ依存の関係にある演算結果は Local Wire
によって転送経路が静的に決まっておりレジスタを介さないため、次の Node へ高速に転送できる。
2. IB 間レジスタ依存
IB を跨いだ命令間に真の依存関係がある場合を IB 間レジスタ依存と呼ぶ。この関係にある命令の間ではレジスタを介したデータ転送が必要なため 、Global Wire を経由する。そのため、転送距離のアクセス・レ イテンシが増大し 、さらに IB を跨ぐレジスタ転送経路を RWU で動的に決定するためレ イテンシが増大してしまう。
このことから 、IB 間レジスタ依存にあるレジスタ値の転送がボトルネックになりやすく、高速化する必要がある。次章以降において 、高速化のためにレジスタ値 Fowarding 機構の導入を考える。

4

VLDP3 での Forwarding

本章では従来の Forwarding 機構を VLDP3 に採用したときの問題点をまとめ、新たな機構の必要性を述べる。

4.1

従来手法の問題点

従来の Forwarding 手法では、演算結果を他の全ての ALU へ無条件にブ ロード キャストする必要があるため、ALU 数の増加とともに ResultBus からの入力数も増加し 、Issue Logic が複雑化する問題を抱えていた。4way から 8way 程度のスーパースカラであれば 、このような全 ALUへのブロード キャスト方式による Forwarding でも実現可能である。しかし 、本研究で想定するVLDP3 アーキテクチャは 、ALU-Net に多数のALU を持っている。現時点で実行機構には 64 個の ALU を持った ALU-Net を想定しているため、
もし仮に従来の Forwarding をそのまま適用したとすると、Result Bus からの入力数が 1Node あたり 128 入力 (=2 オペランド ×64ALU) になってしまう。しかも各 Node には Local Wire からの 6 入力 (=2 オペランド ×3 方向からの入力) とレジスタ・ユニットからの 2 入力があるため、実際の入力数はこれ以上となる。入力数が増えると、リザベーション・ステーションでの処理が複雑化する。そして Issue 処理のレ イテンシが増大してしまう。さらに、大規模化による配線遅延の影響が無視できなくなることも予想される。
次章では、VLDP3 で Forwarding を実現するために、Issue Logic の複雑化を抑え、多数演算器で構成された実行機構の下での Forwarding 手法の確立を目指す。

Forwarding 対象依存距離4.2

本稿では依存距離という言葉をレジスタ依存のある IB 同士が時間的にどれだけ離れているかを示す値と定義し 、IB のフェッチ順の差で表されるものとする。IB 間レジスタ依存の 50 ％以上は、依存距離 1 の IB 間 (=隣接 IB 間) であることがわかっている [4]。よって本研究ではこの局所性を生かし 、隣接 IB のみを対象とした Forwarding機構を提案する。

5

提案機構

5.1

提案機構の概要

Local Wire

Forwarding
Wire

Register
Read/Write Unit
Global Wire

ALU-Net
図 5: Wire の種類

提案機構の特徴は、IB 間のレジスタ依存解析をIB Assign 完了前に行い、依存関係の情報を ALUNet 内の Node に持たせることにある。VLDP3のベースラインモデル [6] ではレジスタ・アクセスの情報をすべて RWU 内で処理していたため 、通信レ イテンシが大きいという欠点を抱えていた。本方式では 、IB 間のレジスタ依存関係を前倒しで行い、その結果情報を ALU-Net 内にも持たせる。ALU-Net 内で依存情報を分散管理することで RWU との通信レ イテンシが小さくなる利点がある。またその情報を使うことで、ALUNet の Node 間でレジスタ値を Forwarding できるようになる。転送経路には Forwarding Wireを図 5 のように設ける。ここでは隣接 IB 間のレジスタ依存を対象とする 2 方式 (broadcast 方式と producer driven 方式) 提案する。

producer(Register WriteIB
Decode FAnalyze
Table
Recordconsumer

IB Assignを行う命令

Global Wire)

演算

ExecIB Retire
GNetwork

を行う命令(Register ReadWBRWU Access

Forwarding Wire

FNetwork)(1) Fwd

あり IB
Decode FAnalyze IB Assign

Exec(2) Fwd

なし IB
Decode FAnalyze IB Assign

Exec

GNetwork演算演算

図 7: broadcast 方式のタイミングチャート

broadcast 方式

5.2

この方式は IB 間レジ スタ依存の解析結果をconsumer の Node に与え、受信側で入力値を Select する方式である。consumer だけがレジスタ依存に関する情報を持っているので 、本方式は従来型の Fowarding と類似した機構であると言える。

Forwarding 情報の生成

5.2.1

本稿ではレジスタ値を出力する側の情報を producer 情報、入力する側の情報を consumer 情報と呼ぶ。それぞれ図 6 のように、レジスタ出力のあるレジスタ番号に対応するフィールド に 1bitの w-ﬂag を持つマップを producer 側に、レジスタ入力のあるレジスタ番号に対応するフィールドに 1bit の r-ﬂag を持つマップを consumer 側に、それぞれ静的に付加しておく。r-ﬂag を持つマッ
プには、レジスタ読み込みを行う命令の配置情報を座標として一緒に付加しておく。各論理レジスタ番号に対応したエント リのビットフラグの積が 1 であると、その 2 つの命令間に隣接 IB 間レジスタ依存が存在する。図の例ではレジスタ R2を Forwarding の対象とみなし 、Forwarding 情報として consumer の Node(1,1) に Assign する。
producer情報
w-flagconsumer情報

012

36300

10

1

r-flag0126300

10
(5,2)

座標 (1,3) (4,6) (1,1)

R2生成したForwarding情報 Forwarding flag=1
consumerの Node(1,1)×
RegID2 = 1へAssignする

図 6: Forwarding 情報の生成

5.2.2

タイミングチャート の解説

タイミングの様子を図 7 に示す。各ブロックは処理ステージのタイミングを表し 、ブロックの長さとパイプ ライン段数とは無関係である。
Forwarding ありの場合 (1) となしの場合 (2) を併記する。

producer は IB Decode 終了後にレジスタ出力情報を Fwd Table に記録する (Table Record)。
consumer は新たに FAnalyze(Forwarding Analyze) ステージへ進み、このステージで producerと consumer のレジスタ入出力情報をマージして Forwarding 情報を生成する。ここで得られた
Forwarding 情報とそれ以外の Decode 情報を一緒に consumer の命令に付加し 、次のステージ(IB Assign) へと実行を進める。
(2) の場合、producer の演算が終了すると、通常のレジスタ書き込み処理が始まる。通常処理
ではレジ スタ値を Global Network を経由してRWU へと送信する (GNetwork)。そして RWU内でレジ スタ依存関係を解析する (RWU Access)。解析の結果、後続 IB と IB 間データ依存の関係にあると判断された場合は 、再び Global
Wire を経由して目的の Node へデータを送信する (GNetowork)。
(1)Fwd ありの broadcast 方式では、producerの演算が終了した時点でレジスタ出力値を Forwarding ネットワークに送信する。転送経路にはForwarding ネットワークを用いる (FNetwork)。
転送されたレジスタ値を consumer 側で受信すると、Forwarding 情報を使って自分に送られてきた値かど うかを Select する。ネットワークは RWUを 経由し ない Fowarding Wire を使う (FNetwork)。
また本方式では 、producer からレジスタ値がbroadcast された時点で、consumer の Assign がまだ完了していない場合も存在する。Assign 完
了前の consumer には何を入力とすべきかの情報が存在しないため 、送られてきたレジスタ値をSelect することができない。そのため 、受信したレジスタ値をそのまま破棄するか 、もし くはAssign 完了まで Node 内に保持しておくかの 2方式がある。レジスタ値を破棄する場合は単純で、レジスタ値を受信した時点で Assign が間に合った consumer のみ、レジスタ値を Select してForwarding を行う。間に合わなかったものは通常の RWU 経由でレジスタ値を受信する。一方
Node 内に保持しておく場合には Node に Buﬀerを設け、宛先不明のレジスタ値はこの Buﬀer 内で Assign 完了まで待たせるようにする。いずれ

の方式が良いかを判断するため 、両方式で測定を行ってみる。

5.3.3

本方式の特徴は、後続 IB へ高速に転送すべきレジスタ値とそうでないレジスタ値を producer側が知っていることにある。高速に転送すべきレジスタ値は IB 間の依存距離が 1 のレジスタ依存であり、この依存関係にあるレジスタ値のみを隣接 IB へ Forwarding Wire を使って高速に転送することで、Forwarding ネットワークへの負荷を抑えられるようになっている。この「 高速に転送すべきレジスタ値を選択」することが本方式の利点であると言える。

producer driven 方式

5.3

producer driven 方式の特徴

2 つめの提案方式では 、IB 間レジスタ依存関係を解析し 、その結果をレジスタ値の送信元となる IB 側の命令に与える。Forwarding すべきレジスタ値を送信元で選択することで、Forwardingネットワークの負荷を軽減できる利点がある。
Forwarding 情報の生成

5.3.1

producer情報01
座標 (2,7)

w-flag

本章ではそれぞれの方式をシミュレータに実装して性能の変化を調べ、考察する。

6.1

2630(3,3)1(5,1)

0(8,0)00
座標 (1,3)r-flagFrame=21

2

630(4,6)

1(1,1)

1(5,2)

Frame=4

生成したForwarding情報

×Frame=4

Node(1,1)

RegID=2

producerの Frame=2Node(5,1)

へAssignする

図 8: Forwarding 情報の生成

5.3.2

タイミングチャート の解説

本方式のタイミングチャートを図 9 に示す。
broadcast 方式と異なる点は 、FAnalyze ステー
ジが IB Assign と同じタイミングで始まり、生成した Fowarding 情報を FAssign ステージで producer へ付加する点である。

Global Wireproducer (Register Writeを行う命令)
IB Decode

評価環境

VLDP3compiler でコンパイルした SPECint
95 に train 入 力 を 使 い 、ト レ ー ス ベー ス のVLDP3simulator で評価を行った。IB は最大 64命令を含むように作った。ここではモデルの基本的傾向を知ることを目的とするため 、ALU-Netのトポロジは完全結合網を仮定した。完全結合網とは、ALU-Net 内の全ての Node が他の任意のNode と Local Wire で接続されたネットワーク・モデルである。VLDP3compiler の作成と ALUNet トポロジによる IB の品質については関連研
究で述べられている [7]。シミュレーションモデル
は第 2.4 節の実行モデルを用い、分岐予測は 100％ヒットとした。その他のパラメタは表 1 の通りである。前処理は Fetch 、Decode 、Assign でそれぞれ 2 サイクルと設定した。ROB はリオーダバッファサイズである。

consumer情報

1

性能評価と考察6

broadcast 方式と同様に 、図 8 の w-ﬂag のマップ を producerIB に 、r-ﬂag のマップ を consumerIB にそれぞれ静的に付加しておく。各論
理レジスタに対応するビット列とその命令の配置情報を保持するマップを保持する。解析ステー
ジでは各エントリの比較を行い、IB 間レジスタ依存を判断する。図の例では R2 が IB 間レジス
タ依存にあるので 、consumer の座標情報 (1,1)
を producer に送信 (Assign) する。

IB Assign

Execreceive

演算

IB RetireWB

表 1: 測定環境に用いたパラメタ
パラメタ
IB 多重度ROB size
前処理 latency cycle
追加 FAnalyze latency cycle
追加 FAssign latency cycle
実行 latency(per Node) cycle
Local network latency cycle
Register access latency cycle
Register network latency cycle
Forwarding network latency cycle
Cache access latency cycle
Cache network latency cycle
Cache size

No-fwd8166001022+2(往復)010∞

B
8166101000110∞

P8166121000110∞

各方式の性能比較を行うため 、方式ごとに値が異なる要素のあるパラメタについて注目する。
Forwarding Wireconsumer (Register Readを行う命令)
Forwarding ネットワークは現時点で理想的なの
FNetwork
GNetwork で、方式ごとに変わることはなく、両方式とも 1FAnalyze
FAssignに設定する。そのかわりレジスタ・レ イテンシ
Fwdあり
演算
IB Decode
IB Assign Execが 0 になる。レジスタ依存の処理もマップのエント リ比較なので 、処理量は同じ である。よっ図 9: producer driven 方式のタイミングチャートて FAnalyze レ イテンシも同じに設定する (=レTable Record

GNetworkRWU Accessイテンシ 1)。FAssign レ イテンシは ALU-Net への命令 Assign と同じ 処理なので 2 に設定する。

6.2

各方式の性能比較

方式別に性能を測定した結果を図 10 に示す。
No-forward は Forwarding を行わなかった場合、Broadcast-nobuﬀer と Broadcast-idealbuﬀer はそれぞ れ Buﬀer なし と 理想的 Buﬀer ありの
broadcast 方式、Producer は producer driven 方式、Perfect-forward は理想的な Forwarding を行ったときの IPC である。また producer driven方式で Forwarding 対象命令数を測定した結果を
図 11 に示す。all depreg は 、consumer から見たときに IB 間レジスタ依存がある命令数の IBあたりの平均値を表しており、fwd depreg は alldepreg の中で Forwarding した命令数の平均を表している。D1 は隣接 IB の Forwarding だけをサポートした場合、D16 は ROB と同じだけの依存距離を Forwarding した場合の値である。

7No-forward

Broadcast-nobuffer

Broadcast-idealbuffer

Producer

Perfect-forward

6考察

6.3

図 10 に よると 、ベー スラ イン と な る Noforwad の IPC と比較して、理想的な Forwardingを行った場合 (Perfect-forward) には約 2 割の性能向上が見込める。これを性能の上限値とすると 、提案した producer driven 方式において理想的な値に近い性能が 得られることがわかる。
broadcast 方式との比較で見てみると、いずれもproducer driven 方式の性能が上回っている。これは broadcast 方式で IB の実行ステージ 中にFAnalyze ステージが追加され 、パイプライン段数増えたことによると考えられる。
次に図 11 によると、IB あたり D16 の場合で約 3 割、隣接 IB 間にすれば約 4 割の Forwardingの対象命令数が削減できた。producer driven 方式は producer がレジスタ値を Forwarding Wireに流すべきかそうでないかを知っているので、この性質を使うことで Forwarding 対象命令数が削減でき、ネットワーク負荷を抑えられることが言える。
以上より、producer driven 方式で理想値に近い値が得られ、かつ、Forwarding 対象命令数を抑えてネットワーク負荷を軽くできるという点から考えて 、提案方式の有効性が示されたと言えよう。

574CPI

32

10compressgo

ijpeg

li

m88ksimperl-jperl-pperl-svortexmean

図 10: 各方式の IPC

おわりに

本稿では多数 ALU を規則的に配置した実行機構を持つ VLDP3 アーキテクチャについて述べた。IB 間レジスタ依存の関係にある命令間でレジスタを介さない Forwarding 機構を提案し 、その評価を行った。特に隣接 IB 間のレジスタ依存にのみ着目し 、提案手法を用いることで、Forwarding
対象命令数を約 4 割削減することができた。性能向上率も理想値に近い値が得られることがわかった。今後は 、より具体的な Forwarding ネッ
トワークのトポロジを考える必要がある。

謝辞

16
fwd depreg (D1)

fwd depreg (D16)

all depreg

14

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

12

参考文献

10

BI/ 8

[1] 田中裕治, “VLDP3 アーキテクチャの構想 (3)〜レジスタフォワーディング機構の初期検討〜”, 情報科学
技術フォーラム 2002 講演論文集 C-17, Sep. 2002.

6

4

20

compressgo

ijpeg

lim88ksim

perl-jperl-pperl-svortexaverage

図 11: IB あたりに Forwarding した命令数[2] 入江英嗣, “VLDP3: データフローを高速実行する大規模アーキテクチャ”, 情報処理学会研究会報告 ARC
2003-ARC-151, Vol.2003, No.10, pp.49-54, Jan.
2003.
[3] 服部直也, “VLDP3 アーキテクチャに対するコード生成の検討”, 情報処理学会研究会報告 ARC 2003ARC-151, Vol.2003, No.10, pp.55-60, Jan. 2003.
[4] 山口健輔, “VLDP3 アーキテクチャにおけるメモリリネーミング手法の検討”, HOKKE2003, 2003.