Vol. 45

No. SIG 6(ACS 6)

May 2004

情報処理学会論文誌：コンピューティングシステム

クリティカルパス情報を用いた分散命令発行型マイクロプロセッサ向けステアリング方式
服
入

部
江

直
英

也†,☆ 高嗣†,☆☆ 坂

田
井

正
修

法†
一†

岡
田

部
中

英

淳†
彦†,☆☆☆

マイクロプロセッサの高クロック動作と高 IPC を両立させるために，小規模な演算資源の塊を間接的に接続したクラスタアーキテクチャが提案されている．このアーキテクチャでは，個々のクラス
タは高速に動作する．しかしクラスタの命令発行幅が狭いため，命令を適度に分散しなければ高 IPCは得られない．その一方で，クラスタ間の信号転送遅延が小さくないため，データ依存のある命令を別クラスタに分散すれば IPC は低下してしまう．したがって，命令をクラスタに割り当てる，命令
ステアリングには，データ依存と負荷分散の適切なバランスをとることが求められている．これまでの研究では，クラスタの負荷情報を指標としてバランスをとる方式が提案されていた．しかしこの方
式は，データ依存に関係なく命令を分散させる点に非効率性が存在していた．そこで本論文では，ク
リティカルパスに属する重要な命令の分散を避け，重要でない命令を用いて予防的に負荷分散を行う方式を提案する．また，クリティカルパス情報だけでは判断が適切でない状況に着目し，これを回避するために，洗練された負荷指標を併用する方式を提案する．

Critical Path Based Steering Algorithms
for Clustered Microprocessor Architectures with Distributed Issue Logic
Naoya Hattori,†,☆ Masanori Takada,† Jun Okabe,†
Hidetsugu Irie,†,☆☆ Shuichi Sakai† and Hidehiko Tanaka†,☆☆☆
To achieve both high clock rate and high IPC of microprocessors, clustered architecture
has been proposed. In this architecture, small number of computation resources is clustered,and the clusters are interconnected each other. Each of them performs at high clock rate,
but has only narrow throughput. Therefore, instruction workload of each cluster should bebalanced for high IPC, On the other hand, dependent instructions should be steered into thesame cluster, to avoid inter-cluster communication delay. To achieve high IPC, data dependence ﬁrst strategy and load balance ﬁrst strategy should be selected properly. Therefore, thesteering algorithm to decide the strategy by workload information has been proposed. But
this method has ineﬃciency because data dependence is always ignored while workload is unbalanced. In this paper, Criticality Steering is proposed. This steering algorithm prevents toignore any critical data dependence, and uses all non-critical instructions for load balancing.
Then we propose another steering algorithm with critical path and workload information, forthe condition that critical path information alone does not work well.

1. は じ め にが，高性能化への要求はとどまるところを知らない．

近年プロセッサの性能は目覚ましく向上している

る Deeper Pipeline 技術と，半導体技術の微細化によ近年のプロセッサは主に，パイプラインを深く設計する高クロック化によって性能を向上させてきた．プロ† 東京大学大学院情報理工学系研究科
Graduate School of Information Science and Technology, The University of Tokyo
☆
現在，日立製作所中央研究所
Presently with Hitachi, Ltd., Central Research Laboratory☆☆
現在，科学技術振興機構
Presently with Japan Science and Technology Agency☆☆☆
現在，情報セキュリティ大学院大学
Presently with Institute of Information Security

セッサの性能は動作クロックと IPC（Instruction Per

Cycle）の積で求められるため，性能向上のためには両者のバランス良い改善が望ましい．しかし実際には，
動作クロックを向上させると IPC は低下する傾向にある．
パイプラインを深くすると各処理に必要なサイクル数が増加し，依存関係にある命令の発行間隔が大きく
12

Vol. 45

No. SIG 6(ACS 6)

分散命令発行型マイクロプロセッサ向けステアリング方式

13なるために，IPC が低下する5),14) ．また半導体技術のスタへ割り当てることで，クラスタ間通信に起因する微細化に関しては，今後ゲート遅延に対して配線遅延

Wakeup 遅延を回避することができる．

が支配的になることが知られている．アーキテクチャ

また，個々のクラスタのスループットが小さいため設計者は，処理遅延の増加を容認するか，演算資源をに，特定のクラスタに命令が集中すると命令が Wakeup

減らして遅延増加を抑えるかの選択を迫られるが，いしていても Select されない，Select 遅延が発生する．

ずれにしても IPC が低下すると考えられている1) ．

この遅延は，命令を IQ 内の命令が少ないクラスタへ

IPC の低下要因は，制御依存による発行間隔の拡割り当てることで回避することができる．

大，レジスタデータ依存による発行間隔の拡大，メモ

このように命令をクラスタに割り当てる，命令ステ

リデータ依存による発行間隔の拡大，の 3 種に大別さアリングは，Wakeup 遅延と Select 遅延のバランス

れるが，最も影響が大きいのはレジスタデータ依存でをとらなければならない，難しい問題である．

5),14)．そこでレジスタデータ依存に関係する機構

これまで，Wakeup 遅延回避/Select 遅延回避のいとして，演算器間のデータフォワーディング機構と命ずれかに特化した命令ステアリング方式と，クラスタ

令発行機構（IQ: Issue Queue）に関する配線遅延が間の負荷均衡状態を用いて両者を使い分ける折衷方式

重要視されており，これまでに様々な研究がなされてが提案されている．それらの中では折衷方式が IPC 的いる3),5),8)∼10),13),15) ．本研究ではその中の，クラスに最も優れているが，負荷集中が発生している場合にタアーキテクチャに着目する．

いっさいのデータ依存関係を無視する点に，非効率性ある

Alpha 21264 6),7) に代表されるクラスタアーキテクが存在していた．

チャでは，演算資源をクラスタリングすることで IPC

そこで本研究では，高負荷クラスタへのデータ依存低下問題を改善している．IPC に大きな影響を与える，だけを無視するための負荷指標を検討する．また別の演算器間のデータフォワーディング遅延に関しては，

アプローチとして，クリティカルパス4),16) に属する

少数の演算器の塊（クラスタ）を形成することで対処重要なデータ依存は負荷にかかわらずつねに最優先し，する．クラスタ内の演算器は少数であるため，フォワー

重要でない命令だけを用いて予防的に負荷分散を行う

ディングの距離を短くすることが可能であり，遅延を方式を提案する．最後に，クリティカルパス情報だけ抑えられる．しかし，個々のクラスタのスループット

では判断が適切でない状況に着目し，これを回避するは小さい．そこで複数のクラスタを用意して，それらために負荷指標を併用する方式を提案する．

を間接的に接続することで，プロセッサ全体のスルー
プットを確保する．

本論文は以下のように構成される．2 章では命令ス
テアリングに関する関連研究を紹介し，3 章では本論

命令発行時には，後続命令のオペランドが揃ったこ

文で想定するアーキテクチャと評価環境について説明と（Wakeup）の判断のために，全 IQ エントリに発する．4 章で関連ステアリングの性能を解析し，それ行された命令のタグを送信するが，この命令タグ転送を受けて 5 章ではより優れた負荷指標と，クリティカ

遅延も IPC に与える影響が大きい．そこで，命令発行

ルパス情報を用いた方式を提案，評価する．最後に 6機構に対してもデータフォワーディングと同様に，ク章で全体をまとめる．

ラスタ化することが有用である．本研究ではそのよう

2. 関 連 研 究

な分散発行方式3),8) を仮定する．分散発行方式では，発行待ち命令を保持する IQ エントリをクラスタリン
グして，小規模な IQ を構成する．そしてその小規模

IQ を演算器クラスタと 1 対 1 に対応させる．この方本章ではこれまで研究されてきた，命令ステアリン
グ方式を紹介する．
命令ステアリングには Wakeup 遅延回避と Select式では IQ に対応する演算器数が減少するために，演遅延回避の 2 つの側面がある．クラスタアーキテク

算器に合わせて発行命令を選択する Select 処理も高チャではクラスタ間に信号転送の遅延（通信遅延）が速化される．

存在するため，データ依存関係のある命令を別のク

クラスタアーキテクチャでは命令をクラスタに割り

ラスタにステアリングすると Wakeup が遅れてしま

当てる，命令ステアリングの質がその性能を左右する．

う．このような Wakeup 遅延を避けるためには，デー

クラスタアーキテクチャでは，クラスタ内の信号転タ使用命令を，データ生成命令と同じクラスタ（オペ

送は短い配線で高速に行われるのに対し，クラスタ

ランドクラスタ）にステアリングすればよい．このよ

間の信号転送は配線長が長く，遅延が大きい．そのたうなステアリング戦略を本論文では，OP-戦略（OP

め命令を，データ依存関係にある先行命令と同じクラは Operand Producer の略）と呼ぶ．また，クラスタ

14

情報処理学会論文誌：コンピューティングシステム

アーキテクチャでは，各クラスタの命令発行幅が狭くなるため，同一クラスタに命令が集中すると Select がMay 2004

Focused Steering
Dependence Based Steering の改良方式として，ク

遅れてしまう．このような Select 遅延を避けるために

リティカルパス情報を用いた Focused Steering が提は，命令を最も命令数の少ないクラスタにステアリン

案されている4),16) ．クリティカルパスとは，プロググすればよい．このようなステアリング戦略を本論文

ラムの実行時間を規定する，最も長いデータ依存のフでは LW-戦略（LW は Low Workload の略）と呼ぶ．

ローである．両文献では，プログラム中のクリティカ

Modulo-N Steering

ルパスをヒューリスティックを用いて発見する方式がSelect 遅延の回避に特化した命令ステアリングとし提案されているが，Focused Steering ではこの情報にて，Modulo Steering が考案されている2) ．Modulo

基づいて，クリティカルパスの延長を避けるステアリ

Steering では，命令を Round-Robin に各クラスタにングを行う．

割り当てることで，命令集中を回避する．この方式でFocused Steering のアルゴリズムを図 2 に示す．こはクラスタ数を C とすると，X 番目にフェッチされたの方式は基本的に Dependence Based Steering と同じ命令は，[X mod C] 番のクラスタへステアリングさ動作をするが，クリティカルパス上の命令の未解決オれる．

ペランドが複数存在する場合には，クリティカルパスただし，これだけでは Wakeup 遅延が大きくなりやに属する重要なデータ依存を優先し，重要な Operand

すいため，クラスタ間の通信遅延が大きい場合には不Producer と同じクラスタに割り当てる．この動作に向きである．そこで，データ依存のある命令はフェッチ

より，クリティカルパス中に通信遅延が追加されるこ順的に比較的密集していることを利用して，連続したとを回避できる．

N 命令の塊を Round-Robin で割り当てる，ModuloN Steering も考案されている．この方式では X 番目

Parcerisa らの Steering
Wakeup 遅延と Select 遅延の双方の影響を避けるにフェッチされた命令は，[X/N mod C] 番のクラス

ために，Parcerisa らはクラスタ間の負荷バランスに

タへステアリングされる．N の値はクラスタアーキテ着目した折衷方式を提案している11),12) ．そのアルゴ

クチャの構成に応じて，発見的に選ばれる．

リズムを図 3 に示す．この方式では，負荷が均衡してDependence Based Steering
Wakeup 遅延の回避に特化した命令ステアリングいる場合はどのクラスタにも Select 遅延に差がない

として，データ依存を重視した Dependence Based

る場合は Select 遅延を重視して LW-戦略を採用する．

2)と判断して OP-戦略を採用し，負荷集中が発生していSteering が考案されている ．そのアルゴリズムを

彼らは負荷を把握するために，まず IQ 内の Wakeup

図 1 に示す．このステアリング方式では，対象命令に済み命令数である NREADY という指標を検討した．

未解決のオペランドが存在する場合はつねに OP-戦略

しかし，命令ステアリングの結果が NREADY に反映を適用する．この際，未解決オペランドが複数存在す

されるには時間を要するため，その間に NREADY がる場合には，その中から任意のオペランドを選択する．

最小だったクラスタに命令が集中する可能性がある．

また，未解決オペランドが存在しない場合は，Select

これを避けるために，彼らは DCOUNT という近似

遅延を回避するために LW-戦略を適用し，最も命令数が少ないクラスタを選択する．このステアリングは

OP-戦略を基本としているため，特定のクラスタに命令が集中しやすい．そのため，クラスタの発行幅が狭い場合には不向きである．

図 1 Dependence Based Steering のアルゴリズム
Fig. 1 Algorithm of Dependence Based Steering.

図 2 Focused Steering のアルゴリズム
Fig. 2 Algorithm of Focused Steering.

Vol. 45

No. SIG 6(ACS 6)

15

分散命令発行型マイクロプロセッサ向けステアリング方式

図 4 想定するアーキテクチャの構成
Fig. 4 Target architecture.
図 3 負荷情報を用いる命令ステアリングのアルゴリズム
Fig. 3 Steering algorithm using workload information.

指標を採用した．彼らが用いた指標 DCOUNT は各
クラスタの状態を示す符号付整数値で，命令がそのクラスタにステアリングされた場合に [クラスタ数 − 1]だけ増加し，他のクラスタにステアリングされた場合に 1 だけ減少する．負荷状態を判断する際には，最大の DCOUNT 値が閾値よりも大きければ負荷集中と見なし，小さければ負荷は均衡していると見なす．また，DCOUNT が最少のクラスタを最低負荷クラスタと見なす．
またこの方式では，複数オペランド命令に対するオ
ペランドクラスタを選択する際にも，DCOUNT が最も小さいクラスタを選択する．

3. 本研究で想定するプロセッサ構成と評価
環境
3.1 本研究で想定するプロセッサ構成
本研究で想定するアーキテクチャの構成を図 4 に示す．想定するアーキテクチャは Frontend，分散クラスタ，Backend，クリティカルパス予測器から構成される．Frontend では命令のフェッチ，デコード，レジスタリネーミングを行い，分散した IQ への命令ステアリングを行う．IQ からキャッシュまではクラスタに

表 1 シミュレータの設定
Table 1 Simulator conﬁguration.

Total Pipeline Depth
Issue-to-Wakeup
D1 Access
クラスタ間通信遅延
整数演算遅延
整数乗算遅延
浮動小数点演算遅延
分岐予測
メモリ依存予測キャッシュ
クラスタ数
各 IQ の発行幅
各 IQ entry
フェッチ幅
リタイア幅
演算器の機能命令セット
測定命令数

20 stages
1 cycle2 cycles2 cycles1 cycle15 cycles
4 cyclesGshare（64 k エントリ）
理想化
100% hit
8
1 issue/cluster
32
88
全種類の命令を処理可能
Alpha 21264
最大 16 M 命令

表 2 クリティカルパス予測器の設定
Table 2 Conﬁguration of Critical Path Predictor.
推定法
indexing
エントリ数
各エントリの内容
Critical と判定された場合
Non-Critical と判定された場合
Critical と予測する閾値

Qold
PC base direct map
32 k エントリ
6 bit 飽和カウンタ
カウンタを MAX にするカウンタを −1 する
1 以上

含まれており，レジスタとキャッシュはそれぞれが完全な複製を保持する．Backend は主にリタイア処理をし，それぞれ Alpha 21264 のすべての種類の演算を行い，リタイア命令の情報をクリティカルパス予測器

実行できると仮定した．分岐ミスペナルティとなる総に通知する．クリティカルパス予測器は Frontend に

パイプライン段数は，全部で 20 段とし，データ依存

対して予測情報を与える．このほかにも Frontend へのある命令の発行間隔（Issue-to-Wakeup 遅延）は最は，ステアリングの選択や IQ が不足した場合の stall

短で 1 サイクルとした．

管理のために各 IQ の負荷情報として IQ 内の命令数が通知される．

同様にクリティカルパス予測器の設定を表 2 に示す．各命令がクリティカルであるか推定する方法とし

3.2 評 価 環 境て，文献 16) で提案されている Qold を用いた．これ

以下で評価に用いるシミュレータの設定を表 1 に示

は，IQ 内の最古の命令がオペランド待ち状態である

す．1 並列のクラスタ 8 つからなる構成とし，キャッ

場合に，クリティカルな命令であると推定するヒュー

シュやメモリ依存予測は理想化した．また，各クラス

リスティックである．想定アーキテクチャでは IQ はタの演算器は完全にパイプライン化されていると仮定

分散しているが，すべての IQ の中で最も古い命令の16

情報処理学会論文誌：コンピューティングシステム

May 2004

表 3 使用ベンチマーク
Table 3 Benchmark set.

MediaBench（計 16 種）SPECint2000
test（計 11 種）SPECint95
train（計 10 種）

adpcm（rawcadio, rawdaudio），
epic（epic, unepic），
g721（encode, decode），
gsm（toast, untoastv），
jpeg（cjpeg, djpeg），
mesa（mipmap, osdemo, texgen），
mpeg2（encode, decode），
rasta
bzip2, crafty, gap, gcc, gzip, mcf,
parser, twolf, vortex,
vpr（place, route）
compress, gcc, go,
ijpeg, li, m88ksim,perl（jumble, primes, scrrable），
vortex

図 5 従来ステアリング方式の CPI
Fig. 5 CPI for each Prior Steering algorithm.

みを Qold の対象とした．
使用するアプリケーション全 37 種を表 3 に示す．
これらのアプリケーションを最大 16 M 命令動作させ，平均 CPI を求めた．

4. 従来命令ステアリングの性能解析
本章では既存の命令ステアリング方式の性能を確認し，さらなる性能向上への余地を検討する．

図 6 Global Balance Steering の CPI と閾値の関係
Fig. 6 CPI of Global Balance Steering for each threshold.

想定アーキテクチャに対して，2 章で述べた各種ステ
アリングの性能を評価した．ただし Parcerisa 方式に

CPI であり，Wakeup 遅延の影響を受ける．最上端が関しては，NREADY の近似として DCOUNT ではな

各ステアリングを適用した場合の実際の性能を示して

く，クラスタ内の未発行命令数（NINST）を用いるこいる．なお，評価には括弧内に示した最適な閾値を用とも有効だと考え，合わせて評価した．その場合負荷いた．

均衡の判断としては，クラスタの未発行命令数の最大

Focused は Dependence Based よりも通信遅延の値と最小値の差を閾値と比較した．本論文ではこの判影響を軽減できているが，すべてのデータ依存を重視

断指標を Global Balance と呼び，Global Balance をするこれらの方式は Select 遅延の影響を強く受けて用いた命令ステアリングを Global Balance Steering

おり，他の方式よりも CPI 値が大きい．これはデーと呼ぶ．この方式のアルゴリズムは図 3 と同様であタ依存関係にある命令が特定のクラスタに集中するこり，負荷集中の判断に Global Balance を，最低負荷とが原因であり，未解決オペランドが存在する場合でクラスタの判断に NINST を用いる．

も，必要に応じてデータ依存を無視し LW-戦略を採

また，命令ステアリングによる CPI の下限を把握用することの必要性を示唆している．

するために，通信遅延が 0 で発行幅が 8 である 1 ク

また，命令分散機能に優れた残りの 3 方式に関して

ラスタ構成の理想プロセッサ（Ideal）の CPI も測定

は，Modulo，Parcerisa 方式，Global Balance の順にした．理想プロセッサに関しては，動作クロックの低

CPI が低い．Modulo と Parcerisa 方式の比較からは，下等は考慮せず，IQ エントリが 8 倍の 1 クラスタ構

命令ステアリングの判断にデータ依存を用いることの成としてシミュレーションした．

有用性がうかがえる．Parcerisa 方式，Global Balance

性能評価の結果を図 5 に示す．棒グラフの下端は想の比較からは，DCOUNT よりも Global Balance の定アーキテクチャの CPI の下限値となる，理想プロ方が命令ステアリングの判断指標としてより適していセッサの CPI を表している．中央の灰色部までの高ることが確認できた．

さは各クラスタの発行幅を 1 に制限した場合の CPI

次に，最も CPI の低かった Global Balance Steer-であり，Select 遅延の影響を受ける．最上端はさらにing に対して，戦略判断に用いる閾値を変化させながら CPI の調査を行った．その結果を図 6 に示す．

クラスタ間通信遅延を 2 サイクルに設定した場合のVol. 45

No. SIG 6(ACS 6)

分散命令発行型マイクロプロセッサ向けステアリング方式

17

閾値を上げると LW-戦略の頻度が下がるために発行

アリング方式を Local Balance Steering と呼ぶ．そ幅の影響が大きくなって Select 遅延が増加し，OP-戦のアルゴリズムを図 8 に示す．図 3 との違いは，戦略の頻度が上がるために通信遅延の影響が小さくなっ

略判断にオペランドクラスタに関する負荷情報を使用て Wakeup 遅延が減少する．閾値を下げると逆の変する点にある．

化が起こり，Wakeup 遅延と Select 遅延のバランスがLocal Balance Steering を用いた場合の各閾値にお最もよくとれている，閾値 6 の場合に最低の CPI でける CPI の内訳を，図 9 に示す．判断に用いる指標はある 0.494 を示している．閾値調整ですでに安定して変わっているが，Global Balance Steering の同じ閾

いるこの状態から，さらに CPI を削減するためには，値と比べて CPI 中の発行幅に起因する部分に大きな以下の 2 つのいずれかを実現する必要がある．

変化は見られない．一方，通信遅延に起因する部分は，(1)

Select 遅延の増加を抑えつつ Wakeup 遅延を

特に閾値が小さい場合に顕著に減少している．このこ

削減する．

とから，Local Balance を指標とすることで，SelectWakeup 遅延の増加を抑えつつ Select 遅延を

遅延を増やさずに Wakeup 遅延を削減できることが削減する．

確認できた．また最適な閾値 4 の場合の CPI は 0.482(2)

5. さらに高性能な命令ステアリング方式の検討とその評価であった．

5.1 より適切な負荷指標の検討

適な閾値 4 を，強調してある．右端の average37 が

まず我々は，Select 遅延の増加を抑えつつ Wakeup
略の適用に着目した．たとえば図 7 は，横軸にクラ37 アプリケーションの平均値であるが，多くのアプリ
ケーションでは平均と同様に，閾値に対する CPI の変動は小さかった．しかしながら，adpcm では顕著な

スタを，縦軸にクラスタ内の命令数を示しており，こ右下がり傾向が見られ，gap と mcf では顕著な右上がの状況は特定のクラスタに命令が集中している状態をりの傾向が見られた．これは各アプリケーションの並表している．このような状況下では，Global Balance

列度に依存すると考えられる．CPI の大きい，並列度が閾値を超えているため，次の命令には必ず LW-戦の低いアプリケーションでは命令を分散して発行幅を遅延を削減するアプローチとして，無意味な LW-戦

次に，閾値 CPI の関係に関して特徴的なアプリケー
ションのデータを図 10 に掲載する．このグラフは最略が適用され，命令数が最少であるクラスタ c へ割り当てられる．しかし，未解決オペランドが比較的負荷の低いクラスタ b で生成される場合には，クラス
タ c と b の Select 遅延の差は小さいと考えられるため，Wakeup 遅延を軽減する OP-戦略の方が適切と考えられる．このように適切な判断が行えない原因は，

Global Balance が個々のクラスタの負荷を反映していないことにある．
そこで我々は，個々のクラスタの負荷状態を反映させた指標として，OP-クラスタの IQ 内命令数と，IQ
内命令数の最小値の差の命令数を検討した．この指標

図 8 Local Balance Steering のアルゴリズム
Fig. 8 Algorithm of Local Balance Steering.

を Local Balance と呼び，この指標を用いる命令ステ

図 7 Global Balance によるステアリングが適切でない例
Fig. 7 An example of case where Global Balance ismisleading.

図 9 Local Balance Steering の CPI と閾値の関係
Fig. 9 CPI of Local Balance Steering for each threshold.

18

情報処理学会論文誌：コンピューティングシステム

図 10 特徴的なアプリケーションに対する Local Balance
Steering の CPI
Fig. 10 CPI of Local Balance Steering for some
remarkable applications.

May 2004

図 11 Criticality Steering のアルゴリズム
Fig. 11 Algorithm of Criticality Steering.

活用する意味が薄いため，閾値を大きくしてデータ依存を重視すべきである．それに対して CPI の小さい，並列度の高いアプリケーションでは，閾値を小さくして命令を分散させなければ，並列性を利用できない．
以上より，Local Balance Steering の性能は閾値設
定に大きく依存することはないが，アプリケーションの並列性が極端な場合には閾値依存性が観測されることが分かった．

5.2 クリティカルパス情報を用いた戦略判断の提案
次に我々は，Wakeup 遅延の増加を抑えつつ Select
遅延を削減するアプローチとしてクリティカルパスに着目した．

4 章でも述べたように，データ依存に従ってステア
リングを続けると，特定のクラスタに命令が集中して

図 12 クリティカルパス予測テーブルエントリのビット数とCriticality Steering の CPI の関係
Fig. 12 CPI for Criticality Steering with diﬀerent numberof bits per Critical Path prediction table entry.

Select 遅延が発生する．そして，この遅延を避けるた

ため，OP-戦略を適用して Wakeup 遅延を軽減するべ

めには，データ依存を無視して LW-戦略を適用するこきだと考えられる．

とが有効であった．これまでの方式では，負荷集中がそこで我々は，クリティカルパス情報を用いて OP-

発生してから LW-戦略を適用していたが，予防的に戦略/LW-戦略を判断する，Criticality Steering を提LW-戦略を用いておけば，すべてのクラスタを Select

案する．負荷情報に基づいて戦略を判断するステアリ

遅延の少ない状態に保つことが可能であると考えられングでは，複数オペランド命令に対するオペランド選る．そこで我々は，重要でない命令に対して，予防的択にも負荷情報を用いていたが，Criticality Steeringに LW-戦略を適用することで，重要な命令を速やか

ではオペランド選択にもクリティカルパス情報を用いに発行できる可能性に着目した．

る．そのアルゴリズムは図 11 に示すように，分岐条

Focused Steering の項で述べたように，プログラム

件は Focused Steering と同じである．しかし，2 番目の実行時間を決めるのはクリティカルパスであり，その分岐によって OP-戦略と LW-戦略が分かれる点に，の中に含まれる重要な命令に対する Wakeup 遅延や発想の違いがある．

Select 遅延は，実行時間に大きく影響する．これとは対照的に，重要でない命令は多少処理が遅れても全体への影響は少ない．したがって，重要でない命令に対Criticality Steering を用いた場合の CPI を図 12に示す．Criticality Steering では，クリティカルパス
予測の結果が直接ステアリング戦略になるため，予測して予防的に LW-戦略を適用してもこれらの命令にされた重要な命令の割合が性能に影響すると考えられ対する Wakeup 遅延の影響は少ないと考えられる．一る．そこでクリティカルパス予測器は表 2 で述べた構方で，重要な命令に対しては，どのクラスタも Select

成のまま，予測テーブルエントリのビット数を 4〜9

遅延の小さい，良好な状態になっていると考えられるに変化させることで，重要な命令の割合を変化させた．

Vol. 45

No. SIG 6(ACS 6)

分散命令発行型マイクロプロセッサ向けステアリング方式

図 13 特徴的なアプリケーションごとの Criticality Steering のCPI
Fig. 13 CPI of Criticality Steering for some remarkableapplications.

19

図 14

Criticality + Local Balance Steering のアルゴリズム（step1）
Fig. 14 Algorithm of Criticality + Local Balance Steering(step1).

想定アーキテクチャに対しては，測定領域内で安定して低い CPI が得られている．また，6 ビットの場
合が最も CPI が低く，0.479 であった．この数値はGlobal Balance Steering や Local Balance Steeringよりも小さいことから，Criticality Steering の有効性を確認した．
次に図 10 で見た特徴的なアプリケーションの CPI
をクリティカルパス予測器のビット数ごとにまとめたグラフを図 13 に示す．このグラフも，最適なビット数である 6 を強調した．Criticality Steering では，グラフに示した 4 アプリケーションを含むすべてのアプ

図 15

Criticality + Local Balance Steering のアルゴリズム（step2）
Fig. 15 Algorithm of Criticality + Local Balance Steering(step2).

リケーションで，予測器エントリのビット数と CPI の関係がおおむね平坦になった．このことから，Criti-

cality Steering の CPI は予測器エントリのビット数に影響されにくいことが確認された．

5.3 クリティカルパス情報と負荷情報の併用
Criticality Steering では，重要な命令をステアリングする際にはつねに負荷バランスがとれていることを仮定して，つねに OP-戦略を適用していた．また，重要でない命令をステアリングする際にはつねに予防
的負荷分散が有効であると仮定して LW-戦略を適用していた．しかし，クリティカルパス情報とクラスタの負荷情報は独立した情報であるため，必ずしもこの仮定は成り立たない．そこで本研究では，Criticality

図 16 重要命令用閾値の変化と Criticality + Local Balance
Steering の CPI（非重要命令用の閾値は 0）
Fig. 16 CPI of Criticality + Local Balance Steering foreach critical threshold (NonCriticalThreshold =0).

Steering で決定したステアリング先を，負荷情報を用いて修正することで，さらなる性能向上が得られる余する 2 つの閾値をそれぞれ，重要命令用の閾値，非重地を検討した．その具体的な手順を図 14，図 15 に示要命令用の閾値と呼ぶ．

す．図 14 が処理の前半部であり，Criticality Steeringのアルゴリズムを用いて，オペランドクラスタと閾値

なお，Criticality Steering は重要命令用の閾値をIQ のエントリ数と同じ 32（すべて OP-戦略）に，非を選択する．続く後半部（図 15）では，決定した閾値

重要命令用の閾値を 0（すべて LW-戦略）に設定した，を用いて Local Balance Steering を行い，最終的なCriticality + Local Balance Steering と等価である．

ステアリング先を決定する．この方式を Criticality +非重要命令用の閾値を 0 に固定して，重要命令用のLocal Balance Steering と呼ぶ．また，前半部で決定

閾値を 32 から減少させた場合の CPI を図 16 に示す．

20

情報処理学会論文誌：コンピューティングシステム

図 17

非重要命令用閾値の変化と Criticality + Local Balance
Steering の CPI（重要命令用の閾値は 16）
Fig. 17 CPI of Criticality + Local Balance Steering foreach non-critical threshold (CriticalThreshold =16).

May 2004

図 18 特徴的なアプリケーションに対する各方式の CPI
Fig. 18 CPI for each steering algorithm for some
remarkable applications.

重要命令に対する最適な閾値 32 ではなく 16 であった．このことから，重要な命令であっても負荷集中時には LW-戦略を適用して Select 遅延を回避すべきであることが確認できた．
次に，重要命令用の閾値を 16 に固定し，非重要命
令用の閾値を 0 から増加させた場合の CPI を図 17 に示す．非重要命令に対する最適な閾値は 0 ではなく 3であった．このことから，Criticality Steering では重要でない命令を負荷分散しすぎており，重要でない命令であっても負荷が十分に均衡している場合には OP戦略を適用して Wakeup 遅延を回避すべきであるこ

図 19 クラスタ数，通信遅延を変化させた場合の各方式の CPI
Fig. 19 CPI for each steering algorithm with diﬀerent
communication latency and number of clusters.

とが確認できた．
以上から，Criticality Steering にクラスタの負荷情

また，特殊なアプリケーションとしては，gap ですべ

報を取り入れることで，さらに CPI を削減できることての方式で同等の CPI が得られており，mcf で Localを確認した．また，重要命令用の閾値を 16，非重要命Balance 方式の CPI が他を上回っている．これらに令用の閾値を 3 に設定するのが最適であり，その場合関しては図 10 で述べたように，gap と mcf は並列度の CPI は Criticality Steering よりも 3%低い 0.465の高いアプリケーションであり，負荷分散がなされてであった．

いれば理想に近い CPI が得られること，および Local

5.4 各手法の性能比較
これまでに検討した方式と，提案方式の平均 CPI といくつかのアプリケーションにおける CPI を図 18 にまとめる．adpcm 等，多くのアプリケーションでは平均と同様の傾向が見られたが，jpeg-cjpeg，parser，Balance Steering の閾値依存性が高いことが原因である．
また，クラスタ数や通信遅延を変化させた場合のCPI を測定した結果を図 19 に示す．全般的に，通信遅延が大きい場合やクラスタの発行幅が狭い場合と

perl-primes 等のように Local Balance Steering とCriticality Steering の CPI が逆転するアプリケーショ

いった，CPI 的に厳しい条件下では命令ステアリン

ンも少なからず存在した．これは，クリティカルパス

るが，CPI 的な制限が緩い発行幅が 2 や 4 の場合に情報がクラスタの負荷情報とは独立した指標であるは，各方式の性能差が小さく，場合によってはわずかため，それらを用いる命令ステアリングの優劣がアプに CPI が逆転している．また，最も厳しい条件であリケーションに依存することを示唆している．しかしる発行幅 1，通信遅延 4 という構成では，クリティカ

グの性能差が大きい．グラフは基本的に右下がりであながら，両情報を組み合わせた Criticality + Local

ルパス情報のみを用いる Criticality Steering は，他

Balance 方式では，どのアプリケーションでも安定して低い CPI が得られている．

の方式に比べて CPI の増加が著しい．これに関して
は，Criticality Steering には重要でない命令を負荷分

Vol. 45

No. SIG 6(ACS 6)

散しすぎる性質があるために，通信遅延増加の影響を受けやすいことが原因であると考えている．しかしな
がら，Criticality Steering に負荷情報を取り入れることで，クラスタ構成によらず最も低い CPI が得られることを確認した．

6. ま と め
本論文では，次世代高クロック指向マイクロプロセッ
サアーキテクチャとして，分散 IQ 構成のクラスタ型
アーキテクチャを想定し，クラスタの発行幅低下と通信遅延による CPI 増加を抑えるための，命令ステア
リング方式に関して議論した．
関連研究で最も CPI の低かった Parcerisa 方式は，
クラスタ負荷の近似指標として DCOUNT を用いていたが，未発行命令数を用いることでさらに性能が向上することを確認した．
次に，ステアリングの判断指標に，プロセッサ全体を代表する負荷情報ではなく，クラスタ個別の負荷均衡情報を用いる方式を検討した．この方式は Parcerisa
らの方式と比べて 3.7% CPI 改善が得られた．
さらに我々は，プログラム中の重要でない命令に着目する，Criticality Steering を提案した．この方式では重要でない命令を用いて予防的に負荷を均衡させておくことで，重要な命令の Wakeup，Select 遅延を改善できる．この方式は Parcerisa らの方式と比べて4.3% CPI 改善が得られた．
しかしながら Criticality Steering はクラスタの負荷情報に関して，重要な命令のステアリング時にはつねに負荷が均衡している，重要でない命令のステア
リング時にはつねに予防負荷分散が必要である，という極端な仮定を前提としていた．そこで，Criticality
Steering に負荷情報を取り入れる方式を検討したところ，CPI がさらに低下し，Parcerisa らの方式と比べて 7.1%の改善が得られた．
また，命令の重要性情報と負荷情報を単体で用いる
ステアリングの優劣は，アプリケーションやクラスタ
数，通信遅延の大きさに依存していたが，両者を合わせた方式は環境によらず低い CPI が得られることを確認した．
今後の課題としては，提案方式のハードウェア的な複雑性の検討を考えている．
謝辞 本論文の研究は，一部 21 世紀 COE「情報技術戦略コア」による．

21

分散命令発行型マイクロプロセッサ向けステアリング方式

参 考

文

献

1) Agarwal, V., Hrishikesh, M.S., Keckler, S.W.
and Burger, D.: Clock Rate versus IPC: The
End of the Road for Conventional Microarchitectures, ISCA 2000, pp.248–259 (2000).
2) Baniasadi, A. and Moshovos, A.: Instruction Distribution Heuristics for Quad-Cluster
Dynamically-Scheduled, Superscalar Processors, MICRO 2000, pp.337–347 (2000).
3) Canal, R., Parcerisa, J.-M. and González,
A.: A Cost-Eﬀective Clustered Architecture,
PACT 1999, pp.160–168 (1999).
4) Fields, B., Rubin, S. and Bodik, R.: Focusing
Processor Policies via Critical-Path Prediction,
ISCA 2001, pp.74–85 (2001).
5) Hrishikesh, M.S., Jouppi, N.P., Farkas, K.I.,
Burger, D., Keckler, S.W. and Shivakumar, P.:
The Optimal Logic Depth Per Pipeline Stage is
6 to 8 FO4 Inverter Delays, ISCA 2002, pp.14–
24 (2002).
6) Farkas, K.I., Chow, P., Jouppi, N.P. and
Vranesic, Z.: The Multicluster Architecture:
Reducing Cycle Time Through Partitioning,
MICRO 1997, pp.149–159 (1997).
7) Kessler, R.E.: The Alpha 21264 Microprocessor, IEEE Micro, pp.25–36 (1999).
8) Kim, H.-S. and Smith, J.E.: An Instruciton
Set and Microarchitecture for Instruction Level
Distributed Processing, ISCA 2002, pp.71–86(2002).
9) Kim, I. and Lipasti, M.H.: Half-Price Architecture, ISCA 2003, pp.28–38 (2003).
10) Palacharla, S., Jouppi, N.P. and Smith, J.E.:
Complexity-Eﬀective Superscalar Processors,
ISCA 1997, pp.206–218 (1997).
11) Parcerisa, J.-M. and González, A.: Reducing
Wire Delay Penalty through Value Prediction,
MICRO 2000, pp.317–326 (2000).
12) Parcerisa, J.-M., Sahuquillo, J., González, A.
and Duato, J.: Eﬃcient Interconnects for Clustered Microarchitectures, PACT 2002, pp.291–
300 (2002).
13) Raasch, S.E., Binkert, N.L. and Reinhardt,
S.K.: A Scalable Instruction Queue Design Using Dependence Chains, ISCA 2002, pp.318–
329 (2002).
14) Sprangle, E. and Carmean, D.: Increasing Processor Performance by Implementing Deeper
Pipelines, ISCA 2002, pp.25–34 (2002).
15) Stark, J., Brown, M.D. and Patt, Y.N.:
On Pipelining Dynamic Instruction Scheduling
Logic, MICRO 2000, pp.57–66 (2000).
16) Tune, E., Liang, D., Tullsen, D.M. and Calder,22

情報処理学会論文誌：コンピューティングシステム

B.: Dynamic Prediction of Critical Path Instructions, HPCA 2001, pp.185–196 (2001).
(平成 15 年 10 月 10 日受付)
(平成 16 年 2 月 28 日採録)

May 2004

坂井 修一（正会員）

1981 年東京大学理学部情報科学科卒業．1986 年同大学院工学系研
究科情報工学専門課程修了．工学博
士．同年工業技術院電子技術総合研

服部 直也

究所入所．1991 年〜1992 年，米国

1976 年生．1999 年東京大学工学部電子情報工学科卒業．2004 年同

マサチューセッツ工科大学招聘研究員，1993 年〜1996

大学院情報理工学系研究科電子情報

筑波大学電子・情報工学系助教授．1998 年東京大学

学専攻博士課程修了．情報理工学博

大学院工学系研究科助教授，2001 年同大学院情報理士．プロセッサアーキテクチャ等の工学系研究科教授．計算機システム一般，特にアーキ

年 RWC 超並列アーキテクチャ研究室室長．1996 年

テクチャ，並列処理，スケジューリング問題，マルチ研究に従事．

メディア応用等の研究に従事．著書『論理回路入門』，
高田 正法（学生会員）『図説コンピュータアーキテクチャ』．電子情報通信学

1979 年生．2003 年東京大学工学会，人工知能学会，IEEE，ACM 各会員．

部電子情報工学科卒業．現在，同大学
院情報理工学系研究科電子情報学専
攻修士課程在学中．プロセッサアー
キテクチャ等の研究に従事．

田中 英彦（フェロー）

1965 年東京大学工学部電子工学科卒業．1970 年同大学院工学系研
究科博士課程修了．工学博士．同年

岡部淳

1976 年生．1999 年早稲田大学理
工学部電子通信学科卒業．2001 年

同大学工学部講師．1971 年同助教授．1987 年同教授．2001 年より同大学院情報理工学系研究科教授・研究科長．この間

東京大学大学院工学系研究科情報工1978 年〜1979 年米国ニューヨーク市立大学客員教授．

学専攻修了．現在，同大学院情報理

計算機アーキテクチャ，並列処理，自然言語処理，メ

工学系研究科電子情報学専攻博士課

ディア処理，分散処理，CAD 等の研究に興味を持っ

程在学中．プロセッサアーキテクチャ等の研究に従事．

ている．著書『非ノイマンコンピュータ』，
『情報通信
，共著
システム』
，
『Parallel Inference Engine—PIE』

入江 英嗣（学生会員）

書『計算機アーキテクチャ』，『VLSI コンピュータ I，1975 年生．1999 年東京大学工学

II』，『ソフトウェア指向アーキテクチャ』．電子情報部電子情報工学科卒業．2004 年同

通信学会，人工知能学会，日本ソフトウェア科学会，

大学院情報理工学系研究科電子情報

IEEE，ACM 各会員．

学専攻博士課程修了．情報理工学博士．プロセッサアーキテクチャ等の研究に従事．