Vol. 45No. SIG 11(ACS 7)情報処理学会論文誌：コンピューティングシステムOct. 2004
発行時間差に基づいた命令ステアリング方式
服部直也†,☆高田正法†岡部淳†
入江英嗣†,☆☆ 坂井修一†田中英彦†,☆☆☆
マイクロプロセッサの高クロック動作と高 IPC を両立させるために，小規模な演算資源の塊を間接的に接続したクラスタアーキテクチャが提案されている．このアーキテクチャでは，命令発行に関する遅延を軽減するために，『最も発行遅延が少ないクラスタ』を特定し，そこへ命令をステアリングすることが望ましい．しかし，そのようなクラスタを厳密に求めるには複雑な計算を要するため，これまでに提案された命令ステアリング方式は，種々の近似を用いてクラスタを選択していた．本論文では，従来方式が用いている近似の精度を解析し，命令の集中/分散の判断に改善の余地があることを明らかにする．そしてこの判断を改善するために，データ生成命令と消費命令の命令間距離を用いる方式を提案する．シミュレータを用いた評価の結果，提案方式は従来方式に比べて，OOO 発行構成に対しては 9.2%，FIFO 発行構成に対しては 5.0% 性能が向上することを確認した．
Instruction Steering Algorithms Based on Issue Delay
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 architecturehas been proposed. In this architecture, instruction should be steered into “the cluster withminimum Issue Delay”. But to detect such a cluster causes too complex calculation. There-fore, prior instruction steering algorithms use some approximations.This paper analyzesthe precision of such approximations, and ﬁnds the room for improvement at concentra-tion/distribution heuristics. To improve it, Local Distance Steering—a more precise approx-imation algorithm using Instruction Distance—is proposed.The evaluation by simulationshows that Local Distance Steering improves on performance 9.2% with Out-of-Order Issuearchitectures, 5.0% with FIFO Issue architectures.
1.は じ め に
近年プロセッサの性能は目覚ましく向上している
が，高性能化への要求はとどまるところを知らない．
近年のプロセッサは主に，パイプラインを深く設計す
る Deeper Pipeline 技術と，半導体技術の微細化に
よる高クロック化によって性能を向上させてきた．プ
ロセッサの性能は動作クロックと IPC（InstructionsPer Cycle）の積で求められるため，性能向上のため
† 東京大学大学院情報理工学系研究科Graduate School of Information Science and Technol-ogy, The University of Tokyo☆ 現在，日立製作所中央研究所Presently with Hitachi, Ltd., Central Research Labora-tory☆☆ 現在，科学技術振興機構Presently with Japan Science and Technology Agency☆☆☆ 現在，情報セキュリティ大学院大学Presently with Institute of Information Security
には両者のバランス良い改善が望ましい．しかし実際
には，動作クロックを向上させると IPC は低下する
傾向にある．
パイプラインを深くすると各処理に必要なサイクル
数が増加し，依存関係にある命令の発行間隔が大きく
なるために，IPC が低下する5),14)．また半導体技術の
微細化に関しては，今後ゲート遅延に対して配線遅延
が支配的になることが知られている．アーキテクチャ
設計者は，処理遅延の増加を容認するか，演算資源を
減らして遅延増加を抑えるかの選択を迫られるが，い
ずれにしても IPC が低下すると考えられている1)．
IPC の低下要因は，制御依存による発行間隔の拡
大，レジスタデータ依存による発行間隔の拡大，メモ
リデータ依存による発行間隔の拡大，の 3 種に大別さ
れるが，最も影響が大きいのはレジスタデータ依存で
ある5),14)．そこでレジスタデータ依存に関係する機構
として，演算器間のデータフォワーディング機構と命
令発行機構（IQ : Issue Queue）に関する配線遅延が
Vol. 45No. SIG 11(ACS 7)発行時間差に基づいた命令ステアリング方式81
図 1Execution-Driven アーキテクチャFig. 1Execution-Driven Steering Architecture.
図 2Dispatch-Driven アーキテクチャFig. 2Dispatch-Driven Steering Architecture.
重要視されており，これまでに様々な研究がなされて
いる4),5),8)～10),13),15)．本研究ではその中の，クラス
タアーキテクチャに着目する．
Alpha 21264 6),7) に代表されるクラスタアーキテク
チャでは，演算資源をクラスタリングすることで IPC
低下問題を改善している．IPC に大きな影響を与える，
演算器間のデータフォワーディング遅延に関しては，
少数の演算器の塊（クラスタ）を形成することで対処
する．クラスタ内の演算器は少数であるため，フォワー
ディングの距離を短くすることが可能であり，遅延を
抑えられる．しかし，個々のクラスタのスループット
は小さい．そこで複数のクラスタを用意して，それら
を間接的に接続することで，プロセッサ全体のスルー
プットを確保する．
命令発行時には，後続命令のオペランドが揃ったこ
と（Wakeup）の判断のために，全 IQ エントリに発
行された命令のタグを送信するが，この命令タグ転送
遅延も IPC に与える影響が大きい．そこで，IQ に対
してもデータフォワーディングと同様に，クラスタ化
することが有用である．図 1 のように演算器のみを
クラスタ化したアーキテクチャは Execution-DrivenSteering Microarchitecture 10)，図 2 のように命令発
行機構までクラスタ化したアーキテクチャは Dispatch-
Driven Steering Microarchitecture 10) と呼ばれてい
る．なお，図中の縦線はクラスタ間を結ぶネットワー
本研究では，文献 4)，8) 等，多くの文献で支持さ
れている，Dispatch-Driven アーキテクチャに着目す
る．以下では特に断らない限り，Dispatch-Driven を
前提とする．また，クラスタ間ネットワークに関して
は最も理解しやすいクロスバトポロジを前提とする．Dispatch-Driven では命令をクラスタに割り当てる，
命令ステアリングの質がその性能を左右する．クラス
タ内の高速な信号転送を利用するためには，データ依
存関係にある命令を同じクラスタへ集中して割り当て
ることが必要である．しかしプロセッサのスループッ
トを利用するためには，命令を適度に分散させる必要
がある．したがって命令を滞りなく処理し続けるため
には命令ステアリングの際に，何らかの方法で集中と
分散のバランスをとらなければならない．
命令ステアリングの理想は，データ生成命令と消費
命令の『発行時間差』を短縮するために，『最も早く発
行可能なクラスタ』を選択することである．これまで
に提案されたステアリング方式は，発行時間差を近似
的に求めてクラスタを選択していたが，その近似精度
に問題があった．
本論文では『発行時間差』を明確に意識した高精度
な近似方式として，『命令間距離』に着目した LocalDistance Steering と Global Distance Steering を提
案，評価する．
本論文は以下のように構成される．2 章では命令ス
テアリングとクラスタアーキテクチャの性能に関して
検討し，命令の発行時刻情報を利用した，理想的な命
令ステアリング方式を提示する．3 章では命令ステア
リングに関する先行研究を紹介し，理想命令ステアリ
ングを近似する方法とその不備を検討する．4 章では
本論文で想定するアーキテクチャと評価環境について
述べる．5 章で先行ステアリング方式の性能と近似の
妥当性を解析し，それを受けて 6 章ではより優れた近
似方式を提案，評価する．7 章では提案手法に対して
閾値，クラスタ構成を変えた場合の評価を行い，8 章
では異なるクラスタアーキテクチャとの比較を行う．
最後に 9 章で全体をまとめる．
2.命令ステアリング
命令ステアリングは，処理レイテンシとスループッ
トという 2 つの観点から，クラスタアーキテクチャのIPC に影響を与える．命令発行には Wakeup と Select
の 2 段階のプロセスが存在するが，両者はこのプロセ
スそれぞれに対応している．
クラスタ間通信による Wakeup 遅延
本論文では，データを生成する命令（Producer）が
発行されてからデータを消費する命令（Consumer）
が Wakeup するまでの時間差を Wakeup 遅延（また
はΔ Wakeup）と呼ぶ．Producer と Consumer を異
なるクラスタにステアリングする場合は，クラスタ間
の命令タグフォワーディングが通信遅延の分だけ遅れ
ることになる．その様子を 図 3 に示す．図中の W
82情報処理学会論文誌：コンピューティングシステムOct. 2004
図 3命令ステアリングと Wakeup 遅延の関係Fig. 3Relationship between Instruction Steering andWakeup Delay.
図 4命令ステアリングと Select 遅延の関係Fig. 4Relationship between Instruction Steering andSelect Delay.
は Wakeup，S は Select の略で，縦線はクロックを意
味する．また，矢印はデータ依存関係を示している．
Producer と Consumer を同じクラスタに割り当てる
（上段）場合は，Consumer は次のサイクルで Wakeup
するが，異なるクラスタに割り当てる（下段）とクラ
スタ間通信遅延と等しい Wakeup 遅延が発生する．
命令集中による Select 遅延
命令が Wakeup してから Select されるまでの時間
差を，本論文では Select 遅延（またはΔ Select）と呼
ぶ．クラスタアーキテクチャは一般に，個々のクラス
タの命令発行幅が狭い．そのため，同時に Wakeup す
る複数の命令を同クラスタにステアリングする場合，
発行幅を超える後続命令には Select 遅延が発生する．
この様子を 図 4 に示す．依存関係のない命令 a，命令
b を同じクラスタに割り当てる（上段）と，発行資源
が利用可能になるまで命令 b は Stall する．これに対
して，命令 b を異なるクラスタに割り当てる（下段）
場合は命令 a と同時に発行可能である．Wakeup 遅延と Select 遅延のバランス
命令を速やかに発行するためには，Producer とConsumer の『発行時間差』（またはΔ Issue）を短
縮することが必要である．『発行時間差』は前述の定
義より，Wakeup 遅延と Select 遅延の総和で求めら
れる．Wakeup 遅延に関してはデータ依存命令を特定
クラスタへ集中させることで，Select 遅延に関しては
命令を多数のクラスタへ分散させることで軽減でき
る．しかし，一般に実プログラム中の命令列には複雑
なデータ依存関係があるため，Wakeup 遅延の改善は
Select 遅延を招き，Select 遅延の改善は Wakeup 遅
延を招く．したがって命令発行の遅延を改善するため
には，両遅延のバランスをとることが必要である．つ
まり，Wakeup 遅延や Select 遅延といった個々の要素
だけにとらわれず，『最も早く発行可能なクラスタ』を
選ぶことが命令ステアリングの本質である．
究極的には，正確な命令発行時刻を計算してクラス
タを選択することができれば，理想的な性能が得られ
ると考えられる．すべてのクラスタの中から『最も早
く発行可能な』クラスタを選択することから，本論文
ではそのような方式を min(ALL) と呼ぶ．
しかし命令発行時刻の計算，特に Select 遅延の計
算には，命令発行を行うのと同程度以上の複雑性と遅
延を要するため，現実的ではない．そのため，これま
でに近似的な手法が提案されてきた．
3.関 連 研 究
Wakeup 遅延に関しては，オペランド数が多いほど
計算が複雑になる．しかし大多数の命令は，実行時に
未解決であるオペランドは 1 つ以下であることが知
られている2),9) ため，本論文では特に断らない限り複
数オペランドに関する説明は省略する．通信遅延が固
定時間となるクロスバトポロジの採用を仮定すると，Consumer が Producer と同じクラスタにある場合は
Wakeup 遅延が 0 になり，それ以外のクラスタにあ
る場合は固定サイクル（C）の通信遅延が発生する．Wakeup 遅延は最大でも 2 値しかとりえないので，発
行時間差（= Wakeup 遅延 + Select 遅延）が最も小
さいクラスタは，以下のいずれかの条件を満たす．
• 0 入力命令の場合：Select 遅延が最小のクラスタ• 1 入力命令の場合：
Wakeup 遅延が 0 である唯一のクラスタ，または，Select 遅延が最小のクラスタ
Wakeup 遅延が 0 であるクラスタは比較的容易に特
定可能であるが，Select 遅延が最小となるクラスタを
求めることは一般に難しい．そのため多くの命令ステ
アリング方式では，Wakeup 遅延が 0 であるクラスタ
と，近似的に求めた Select 遅延が最小とおぼしきク
ラスタの中から，ヒューリスティックに従って一方を
選択している．
Vol. 45No. SIG 11(ACS 7)発行時間差に基づいた命令ステアリング方式83
図 5Dependence Based Steering のアルゴリズムFig. 5Dependence Based Steering algorithm.
3.1Wakeup 遅延重視の Dependence BasedSteering
Wakeup 遅延の回避に特化した単純な命令ステアリ
ングとして，図 5 に示す Dependence Based Steer-
ing が考案されている3)．この方式では Select 遅延が
十分に小さいと仮定し，対象命令に未解決のオペラン
ドが存在する場合はつねに未解決オペランドと同じク
ラスタ（以下 OP-クラスタと略記：OP は OperandProducer の略）へのステアリングを行う．未解決オ
ペランドが存在しない場合は，最低負荷クラスタ（以
下 LW-クラスタと略記：LW は Lowest Workload の
略）の Select 遅延が最小であるという近似に基づい
てステアリングを行う．この方式は Select 遅延が小さ
いことを仮定しているため，クラスタの発行幅が狭い
場合のように Select 遅延の影響が大きい構成には不
向きである．3.2Select 遅延重視の Modulo Steering
Select 遅延の回避に特化した単純な命令ステアリン
グとして，Modulo Steering が考案されている3)．こ
の方式では Wakeup 遅延が十分小さいという仮定と，
累計ステアリング命令数が少ないクラスタは Select 遅
延が小さいという仮定の下に，命令を Round-Robin
にステアリングする．
この方式は Wakeup 遅延が無視できないアーキテク
チャには不向きであるが，その点を改良した Modulo-N Steering も提案されている．Modulo-N Steering で
は連続する命令には依存関係があると仮定し，連続す
る N 命令ずつの塊を Round-Robin にステアリングす
ることで，Wakeup 遅延の影響を軽減する（図 6）．な
お，Modulo Steering は N = 1 の場合の Modulo-NSteering と等価であるため，以下では両者を区別なく，
Modulo Steering と呼ぶ．
この方式は発行時間差の計算に多数の近似を用いて
いるため，近似精度が低下しやすいことが問題である．
3.3Out-of-Order 発行向けの Parcerisa 方式Wakeup 遅延と Select 遅延の双方の影響を避けるた
めに，Parcerisa らはクラスタ間の負荷バランスに着
目した方式を提案している11),12)（以後，本論文中で
図 6Modulo Steering のアルゴリズムFig. 6Modulo Steering algorithm.
図 7Parcerisa らのアルゴリズムFig. 7Parcerisa’s algorithm.
は Parcerisa 方式と呼ぶ）．そのアルゴリズムを 図 7
に示す．この方式では，負荷が均衡している場合はど
のクラスタも Select 遅延が同程度であると判断してOP-クラスタへステアリングする．逆に負荷集中が発
生している場合は Select 遅延が最も小さいと予想さ
れる LW-クラスタへステアリングする．
彼らは負荷の均衡状態を把握するために，DCOUNT
という指標を採用している．DCOUNT は各クラスタ
の状態を示す符号付整数値で，命令がそのクラスタに
ステアリングされた場合に [クラスタ数–1] だけ増加し，
他のクラスタにステアリングされた場合に 1 だけ減少
する．負荷状態を判断する際には，最大の DCOUNT
値が閾値よりも大きければ負荷集中と見なし，小さけ
れば負荷は均衡していると見なす．
この方式では Select 遅延の推定に，Consumer をWakeup する時点での負荷ではなく，Consumer をス
テアリングする時点での負荷を用いている．したがっ
てステアリングと Wakeup に時間差が大きい場合等，Wakeup 時の負荷状態とステアリング時の負荷状態が
異なる命令に対しては，この方式では適切な判断がで
3.4FIFO 発行向けの Palacharla 方式Palacharla らは文献 10) で，マイクロプロセッサを
高速化するうえで，命令発行の遅延が問題になってい
ることを指摘し，この遅延を短縮するために FIFO 発
行方式に着目している．この方式では，FIFO 先頭の
命令のみを発行可能とすることで，命令タグフォワー
ディング配線を短縮し，高速化することができる．し
84情報処理学会論文誌：コンピューティングシステムOct. 2004
図 8Palacharla らの FIFO 発行クラスタアーキテクチャFig. 8Palacharla’s FIFO issue clustered architecture.
かし，命令発行に制限が課せられているため，各命令
に対して FIFO を選択する，命令ステアリングが重要
になる．彼らは独自の命令ステアリングを提案してい
る（以後，本論文中では Palacharla 方式と呼ぶ）．文
献 10) で提案されているアーキテクチャは，図 8 に
示すように，4 つの FIFO を搭載した 2-cluster から
構成される．また，図中の縦線で示すように命令タグ
やデータをフォワーディングする，クラスタ間ネット
ワークが存在する．Palacharla 方式は単一クラスタ内
の FIFO 選択方法を拡張された形で考案されている．
単一クラスタ内の FIFO に対しては通信遅延が存在
しないため，Wakeup 遅延はつねに一定である．その
ため命令ステアリングには，Select 遅延を可能な限り
避けることが要求される．一般にはそのようなクラス
タを特定することは難しいが，特定の条件下において
簡単に求めることができる．
( 1 )無負荷 FIFO（以下 NW-FIFO と略記：NW はNo Workload の略）が存在する場合：
NW-FIFO へステアリングすれば，Consumer
はつねに FIFO の先頭に位置する．
( 2 )未解決オペランドの Producer が FIFO の末尾
にある場合：Producer と同じ FIFO（以下 OP-FIFO と略
記）にステアリングすれば，Producer の発行
直後に Consumer が OP-FIFO の先頭に位置
する．Palacharla 方式ではこれらの性質を受けて，条件( 2 ) を満たす FIFO があればその FIFO（OP-FIFO）
へ，なければ条件 ( 1 ) を満たす NW-FIFO へステア
リングする．NW-FIFO が不足した場合には，いずれ
かの FIFO が空になるまでステアリングステージ以前
のパイプラインを stall させる．逆に NW-FIFO が複
数存在する場合は，直前の命令と同じクラスタに属す
る FIFO を優先することで，クラスタ間通信の影響を
軽減する．この方式のアルゴリズムフローチャートを
図 9 に示す．
この方式では，Select 遅延の有無のみに着目してい
図 9Palacharla 方式のアルゴリズムFig. 9Palacharla’s algorithm.
図 10想定するアーキテクチャの構成Fig. 10Target architecture.
る．しかし，正確には Wakeup 遅延と Select 遅延の
和が最小になるクラスタを選択すべきであり，そのよ
うな選択のためには，Select 遅延を数値として算出す
る必要がある．
4.本研究で想定するプロセッサ構成と評価環境
4.1本研究で想定するプロセッサ構成
本研究で想定するアーキテクチャの構成を図 10 に
示す．想定するアーキテクチャは Frontend，クラスタ
部，Backend から構成される．Frontend では命令の
フェッチ，デコード，レジスタリネーミングを行い，分
散した IQ への命令ステアリングを行う．IQ からキャッ
シュまではクラスタに含まれており，レジスタとキャッ
シュはそれぞれが完全な複製を保持する．Backend は
主にリタイア処理を行う．なお，本論文では IQ の発
行方式として，Out-of-Order（OOO）発行と FIFO
発行の 2 方式を評価の対象とする．4.2基本評価環境
以下で評価に用いるシミュレータの基本設定を表 1
に示す．1 並列のクラスタ 8 つからなる構成とし，キャッ
シュやメモリ依存予測は理想化した．また，各クラス
タの演算器は完全にパイプライン化されていると仮定
Vol. 45No. SIG 11(ACS 7)発行時間差に基づいた命令ステアリング方式85
表 1シミュレータの基本設定Table 1Baseline simulator conﬁguration.
Total Pipeline Depth20 stagesIssue-to-Wakeup1 cycleD1 Access2 cyclesL2 Access12 cyclesクラスタ間通信遅延2 cycles
整数演算遅延1 cycle整数乗算遅延15 cycles浮動小数点演算遅延4 cycles
分岐予測Gshare（64 k エントリ）メモリ依存予測理想化命令キャッシュ100% hitデータキャッシュ100% hit各クラスタの発行幅と総数1-issue × 8-clusterクラスタ間ネットワークトポロジクロスバ各 IQ のエントリ数32Active List の大きさ256命令発行方式OOO or FIFOフェッチ幅8リタイア幅8演算器の機能全種類の命令を処理可能命令セットAlpha 21264測定命令数256 M 命令
し，それぞれ Alpha 21264 のすべての種類の演算を
実行できると仮定した．分岐ミスペナルティとなる総
パイプライン段数は，全部で 20 段とし，データ依存
のある命令の発行間隔（Issue-to-Wakeup 遅延）は最
短で 1 サイクルとした．クラスタ間の通信遅延に関し
ては 2 サイクルと仮定して評価を行った．
なお Sensitivity の評価のために，クラスタ間通信
遅延，クラスタの並列度，キャッシュに関しては，そ
れぞれ変化させたデータも測定する．
性能評価には SPECint95 の train 10 種をすべて使
用し，これらのアプリケーションを 256 M 命令動作
させ，平均 CPI（Clocks Per Instruction：IPC の逆
数）を求めた．バイナリは OSF1 上で gcc 2.95.2 を
用いて作成した．また測定にはトレースシミュレータ
5.先行命令ステアリング方式の性能
Wakeup 遅延が最小となるクラスタは OP-クラスタ
であるが，Select 遅延が最小となるクラスタを正確に
特定することは難しい．そこで，Select 遅延最小クラ
スタの近似として，従来方式が用いている LW-クラ
スタや NW-クラスタを用いる近似の精度を調べるた
めに，min(OP, LW)，min(OP, NW) という項目も
用意した．これらは min(ALL) がすべてのクラスタ
からΔ Delay が最小であるクラスタを選択するのに対
し，OP-クラスタと LW-クラスタまたは NW-クラス
タの中だけからΔ Issue が最小であるクラスタを選択
図 11従来方式の CPI 比較（OOO 発行）Fig. 11Performance analysis of prior steering algorithms(OOO issue).
する．5.1OOO 発行に対する先行方式の性能解析OOO 発行の想定アーキテクチャに対して，各種ス
テアリング方式を用いた場合の CPI を図 11 に示す．
まず理想的な方式に着目すると，min(OP, LW) は
min(OP, NW) よりも CPI が小さく，min(ALL) と
の差がほとんど見受けられない．これは，Select 遅延
が最小となるクラスタとして LW-クラスタを選択す
る近似の妥当性を示唆している．
また従来方式に関しては，Parcerisa 方式の CPI が
最も小さい．これは Parcerisa 方式で用いている近似
が，他方式の近似よりも精度が高いことを示している．
ここで，min(OP, LW) と Parcerisa 方式に着目す
ると，両者は Select 遅延が最小となるクラスタとしてLW-クラスタを選択している点で共通しており，OP-
クラスタと LW-クラスタの一方を選択する判断基準の
みが異なる．したがって両者の CPI の差は，Parcerisa
方式のクラスタ選択の判断基準が不正確であることに
起因する．つまり，Parcerisa 方式はクラスタの判断
基準に改善の余地が残っていることが確認された．
5.2FIFO 発行に対する先行方式の性能解析
同様に，FIFO 発行の想定アーキテクチャに対して，
各種ステアリング方式を用いた場合の CPI を図 12 に
示す．FIFO 発行の場合は，min(OP, NW) の方が min(OP,
LW) よりも CPI が小さく，min(ALL) との差がほと
んど見受けられない．これは，Select 遅延が最小とな
るクラスタとして NW-クラスタを選択する近似の妥
当性を示唆している．
従来方式に関しては，Palacharla 方式の CPI が最
も小さい．これは Palacharla 方式で用いている近似
が，他方式の近似よりも精度が高いことを示している．
OOO 発行の場合と同様に，min(OP, NW) とPalacharla 方式の CPI の差は，Placharla 方式のクラ
86情報処理学会論文誌：コンピューティングシステムOct. 2004
図 12従来方式の CPI 比較（FIFO 発行）Fig. 12Performance analysis of prior steering algorithms(FIFO issue).
図 13発行時間差の近似計算Fig. 13Issue delay approximation.
スタ選択の判断基準が不正確であることに起因する．
つまり，Palacharla 方式はクラスタの判断基準に改善
の余地が残っていることが確認された．
6.依存命令の発行時間差に基づいた命令ステアリング方式の提案と評価
関連研究におけるクラスタ選択の不正確性を改善す
るために，本研究では，『最も早く発行可能なクラスタ』
の高精度な推定に着目した．以下で説明する推定方式
の概要を図 13 に示す．この図は OP-クラスタ，*W-
クラスタ（LW-クラスタと NW-クラスタの総称）にConsumer 命令をステアリングする場合の，Producer
の発行時刻，Consumer の Wakeup 時刻および発行
時刻を順に示している．Producer が発行してから Consumer が発行するま
での時間差（IssueDelay）は，次の式で求められる．IssueDelay = WakeupDelay + SelectDelay
ここで OP-クラスタ内の実際の命令発行スループッ
トを T，OP-クラスタにおける Producer と Consumer
の間の命令数を ∆ とすると，OP-クラスタにおける
Select 遅延は ∆ / T である．また，*W-クラスタに
おける Select 遅延は小さいと考えられるため，0 に近
似する．よって，通信遅延を C とすると以下の近似式
が成り立つ．
図 14Out-of-Order 発行向け提案手法のアルゴリズムFig. 14Proposal algorithm for OOO issue.
WakeupDelay(OP) = 0WakeupDelay(∗W) = C
SelectDelay(OP) = ∆/TSelectDelay(∗W) = 0
したがって，両クラスタの発行時間差は以下の式で
求められる．IssueDelay(OP) = ∆/T
IssueDelay(∗W) = C
すると『最も早く発行可能なクラスタ』は ∆/T とC の大小比較，つまり ∆ と C×T の大小比較で決定
できる．∆ を正確に算出する方法としては，ステアリングさ
れた命令に対して，クラスタごとに通し番号を付けるこ
とが考えられる．この通し番号の差を Local Distance
しかしクラスタごとに命令の通し番号を付けるに
は，番号の生成や記憶等の管理ハードウェアが必要に
なるため，複雑性が増加する可能性がある．このよう
な複雑性の増加を避けたい場合には，クラスタごとの
通し番号を，アクティブリスト中の間の命令数で代用
することが考えられる．この命令タグの差を GlobalDistance と呼び，その値はΔ Select に比例すると見
なす．C×T に関しては，実効スループットを求めること
も考えられるが，本研究では簡単のために適当な定数
を設定することにした．
したがって，先の比較計算は，Local（Global）Dis-
tance と閾値（定数）の比較に帰着された．Local Distance や Global Distance を判断基準とす
る命令ステアリングは，OOO 発行向け，FIFO 発行向
け命令ステアリングそれぞれの枠組みである，min(OP,LW)，min(OP, NW) に従って図 14，図 15 の形に
なる．6.1評価
表 1 で示した基本構成における各種方式の CPI を，
図 16，図 17 に示す．それぞれ OOO 発行，FIFO 発
Vol. 45No. SIG 11(ACS 7)発行時間差に基づいた命令ステアリング方式87
図 15FIFO 発行向け提案手法のアルゴリズムFig. 15Proposal algorithm for FIFO issue.
図 16従来方式と提案方式の CPI 比較（OOO 発行）Fig. 16Performance comparison of prior and proposedsteering algorithms (OOO issue).
図 17従来方式と提案方式の CPI 比較（FIFO 発行）Fig. 17Performance comparison of prior and proposedsteering algorithms (FIFO issue).
行の場合の CPI を示している．
提案方式 Local Distance Steering は OOO 発行で
は 9.2%，FIFO 発行では 5.0%，従来方式よりも CPI
が改善されている．これは Local Distance Steering
が Select 遅延の推定に用いている近似の精度が，各従
来方式が用いている近似の精度よりも高いためである．
特に OOO 発行の場合は，Local Distance Steering と
理想方式 min(ALL) との性能差が 3.3%ときわめて小
さく，優れた近似精度であることがうかがえる．Global Distance Steering に関しては，OOO 発行
の場合は Parcerisa 方式よりも CPI が 5.7%改善され
ているが，FIFO 発行の場合は Palacharla 方式と比
べて 0.6%とわずかながら CPI が劣化している．こ
れは Global Distance Steering が用いている，Δ Se-
lect(OP) が Global Distance に比例するという近似
の精度が，Parcerisa 方式が用いている近似の精度よ
り高く，Palacharla 方式が用いている近似の精度より
低いことを示している．
7.Sensitivity Analysis
7.1提案手法の閾値依存性
次に，基本設定における，各アプリケーション・閾
値ごとの CPI を測定した．その結果を図 18，図 19
に示す．左側の 5 つの棒は Local Distance（LD）の
閾値 0～4 に対応しており，右側の 5 つの棒は GlobalDistance（GD）の閾値 2～6 に対応している．OOO 発行の場合は各アプリケーションとも，平均と
同様緩やかな CPI 推移を示しており，閾値を LD02，GD04 前後に設定しておけばおおむね最適な設定に
なっている．しかし FIFO 発行の場合には，急激なCPI 変化を示すアプリケーションが存在する．Local/Global Distance は閾値が無限であれば De-
pendence Based と同じ動作をする．その場合は，図 20
のように，出力が複数回使用される命令を含むデータ
フローが特定のクラスタに集中し，Select 遅延のため
に性能が低下する．閾値を下げれば，そのようなデー
タフローが分割されやすくなり，Wakeup 遅延が増加
する代わりに Select 遅延が軽減される．m88ksim やperl-p のように，閾値による急激な CPI 変化を示すア
プリケーションは，図 20 のようなデータフローの実
行回数が多いためであると考えられる．実際 m88ksim
に関しては，『出力が複数回使用される命令』（図 20 のA）の実行頻度が，他のアプリケーションに比べて顕
著に多いことを確認している．
7.2通信遅延を変化させた場合の評価
基本設定から，通信遅延を 1～4 の間で変化させな
がら測定した CPI を，図 21，図 22 に示す．なお，
各方式に関して，それぞれ最適な閾値を用いた場合のCPI を掲載した．
通信遅延が大きいほどΔ Wakeup が増加するため，CPI が増加している．ただし，OOO 発行の場合の
min(ALL) と min(OP, LW) の差や，FIFO 発行の場
合の min(ALL) と min(OP, NW) の差のように，純
粋にΔ Select の推定誤差に起因する性能差は，通信
遅延によらず一定である．つまり，Δ Wakeup に起
因する推定誤差の分だけ CPI が劣化し，各方式の性
能差が広がっている．また，提案方式 Local DistanceSteering は通信遅延の大小にかかわらず，CPI を削減
88情報処理学会論文誌：コンピューティングシステムOct. 2004
図 18提案方式の閾値とアプリケーションごとの CPI（OOO 発行）Fig. 18Performance of individual applications with diﬀerent threshold values (OOO issue).
図 19提案手法の閾値とアプリケーションごとの CPI（FIFO 発行）Fig. 19Performance of individual applications with diﬀerent threshold values (FIFO issue).
図 20閾値が問題になりやすいデータフローグラフの例Fig. 20Example of threshold sensitive Data Flow Graph.
できている．
基本的に，通信遅延が変化しても各方式間の優劣は
変化しないが，FIFO 発行の場合の Palacharla 方式
だけは，通信遅延が増加した場合に CPI が大きく劣
化し，Global Distance Steering との優劣が逆転して
いる．これは，Palacharla 方式はΔ Wakeup =0 を前
図 21通信遅延を変化させた場合（OOO 発行）Fig. 21Impact of inter-cluster communication latency onCPI (OOO issue).
提に設計されているため，通信遅延が増加した場合に
他方式よりも大きな近似誤差が発生することが原因で
Vol. 45No. SIG 11(ACS 7)発行時間差に基づいた命令ステアリング方式89
図 22通信遅延を変化させた場合（FIFO 発行）Fig. 22Impact of inter-cluster communication latency onCPI (FIFO issue).
図 23発行幅を変化させた場合（OOO 発行）Fig. 23Impact of issue width per cluster on CPI (OOOissue).
図 24発行幅を変化させた場合（FIFO 発行）Fig. 24Impact of issue width per cluster on CPI (FIFOissue).
7.3発行幅を変化させた場合の評価
同様に，発行幅を変化させた場合の CPI を図 23，
図 24 に示す．なお，クラスタ全体の発行幅を 8 に固
定するために，発行幅を増やした分だけクラスタ数を
減少させている．
OOO 発行の場合は，クラスタの並列度が上がると
ステアリング方式による CPI 差が小さくなっている
が，FIFO 発行の場合は，並列度が上がっても CPI 差
があまり小さくならない．これは，OOO 発行の場合
図 25Dispatch-Driven OOO 発行アーキテクチャ（2 × 2）Fig. 25Dispatch-Driven OOO Issue Architecture.
図 26Dispatch-Driven 複数 FIFO アーキテクチャ（2 × 2）Fig. 26Dispatch-Driven FIFO Issue Architecture.
は並列度が上がると図 25 のように，ステアリングの
選択肢が減少するのに対し，FIFO 発行の場合は図 26
のように並列度にかかわらず，ステアリングの選択肢
が一定であることに起因する．つまり，OOO 発行の
場合はステアリングの選択肢数が減少するため，運良
く最適なクラスタを選択できる可能性が増加している
と考えられる．7.4現実的なデータキャッシュを用いた場合
基本構成ではデータキャッシュを 100%ヒットとして
理想化していたが，Local Distance Steering や Global
Distance Steering は OP-クラスタのスループットを
固定値で近似しているため，キャッシュミスの影響を
受けやすい可能性がある．そこで本節では，現実的な
キャッシュパラメータに対する性能を測定した．4 章で述べたように，本研究では全クラスタに複製
されたキャッシュが搭載されていることを仮定してい
る．また，クラスタアーキテクチャの意義から考えて，
個々のクラスタに 8 k bytes という小さめのキャッシュ
容量を想定した．なお，内容を全クラスタに複製す
るため，正味のキャッシュ容量はプロセッサ全体でも
8 k bytes となる．その他のパラメータは表 2 に示す．
また，そのパラメータで測定した，各方式の CPI を
図 27，図 28 に示す．
理想的な性能を意味する min(ALL)，min(OP,LW)，min(OP, NW) は正確な処理レイテンシを元
に算出する必要があるため，キャッシュを理想化しな
ければ測定できない．そのため，これらの項目は 図 27，
図 28 には掲載していない．それ以外の方式に関して
は，OOO 発行，FIFO 発行のいずれも 8 k-byte キャッ
90情報処理学会論文誌：コンピューティングシステムOct. 2004
表 2キャッシュパラメータTable 2Cache parameters.
Capacity8 k bytesL1 Data CacheAssociativity2-way
Line Size32 bytes/line
L1 Instruction Cache100%hit
L2 Uniﬁed Cache100%hit
図 278 k のデータキャッシュを用いた場合（OOO）Fig. 27CPI with 8 KB data cache (OOO issue).
図 288 k のデータキャッシュを用いた場合（FIFO）Fig. 28CPI with 8 KB data cache (FIFO issue).
シュを用いることにともなう性能劣化はほぼ同程度で
あり，提案方式 Local Distance Steering が最も高性能
であることが確認された．FIFO 発行であってもキャッ
シュミスの影響を大きく受けない理由としては，各方
式とも基本的にはデータ依存に基づいてステアリング
されていることが考えられる．つまり，キャッシュミ
スを起こしたロード命令とその後続命令が，同じクラ
スタに隣接してステアリングされることが多いために，
キャッシュミスの影響は軽減されていると考えられる．
8.異なるクラスタアーキテクチャとの比較
冒頭でも述べたように，クラスタアーキテクチャに
は Dispatch-Driven のほかに Execution-Driven とい
う構成が存在する．本章では，Execution-Driven 構
成と提案方式を用いた Dispatch-Driven 構成の比較を
図 29小林らのアーキテクチャFig. 29Kobayashi’s architecture.
Dispatch-Driven の特徴Dispatch-Driven では，IQ がクラスタ化されてい
るため，Wakeup 遅延と Select 遅延の総和を小さく
するステアリングが必要である．Execution-Driven の特徴
それに対して Execution-Driven では IQ がクラス
タ化されていないため，Δ Select =0 と見なしてよい．
そのため Wakeup 遅延だけを小さくするステアリン
グを行えばよく，Dispatch-Driven よりも発行遅延を
軽減することが可能である．つまり，高い IPC が期
待できる．したがって，OOO 発行 Execution-Driven
は，OOO 発行 Dispatch-Driven の IPC 上限と考え
ることができる．
しかしその反面，各クラスタに対して利用可能な
オペランドを把握する必要があるため，IQ が複雑に
小林らのアーキテクチャの特徴
小林らは文献 16) で，Execution-Driven の IPC を
さらに向上させるために，データフローグラフの最長
パスの命令に着目して，発行待ち命令に優先順位を設
けることを提案している．小林らは複数 FIFO からな
る IQ と PIT（Path Information Table）を用いて，
データフローの最長パスを計算し，優先すべき重要な
命令を認識している．したがって，小林らのアーキテク
チャは図 29 のように FIFO 発行の Execution-Driven
という構成になる．IQ が複数の FIFO から構成され
ているため，FIFO に対するステアリングも必要であ
るが，これには DFG 解析に応用可能な Palacharla 方
式を用いている．このアーキテクチャでは，1 度目のス
テアリングで Select 遅延が決定し，2 度目のステアリ
ングで Wakeup 遅延が決定する．Execution-Driven
のステアリングを行う点，優先順位を設ける点，の 2
点のために複雑性が増加するが，Wakeup，Select 遅
延を個別に決定できるために発行遅延を軽減しやすく，IPC 向上が期待できる．
したがって，小林らのアーキテクチャは，FIFO 発
行 Dispatch-Driven の IPC 上限であると考えられる．
各アーキテクチャの CPI 測定に関して表 3 に示す
Vol. 45No. SIG 11(ACS 7)発行時間差に基づいた命令ステアリング方式91
表 3各種アーキテクチャ構成Table 3Architecture conﬁgurations.
IQ エントリ数256Execution-Driven発行幅8 命令/cycle（OOO）クラスタ数8
クラスタの演算能力1 命令/cycle
IQ エントリ数32/FIFO小林らの構成発行幅8 命令/cycle（FIFO）クラスタ数8
FIFO 数16
クラスタの演算能力1 命令/cycle
IQ エントリ数32/clusterDispatch-Drivenクラスタの発行幅1 命令/cycle（OOO/FIFO 共通）クラスタ数8
クラスタの演算能力1 命令/cycle
図 30異なるアーキテクチャとの比較（OOO 発行）Fig. 30CPI comparison of various architectures (OOOissue).
図 31異なるアーキテクチャとの比較（FIFO 発行）Fig. 31CPI comparison of various architectures (FIFOissue).
パラメータを用いた．表中に記載のないパラメータは
表 1 の値を用いている．なお，小林らの方式は FIFO
数が少ない構成では本来の性能を発揮できないため，
評価には 16 FIFO 構成を用いた．また，小林らの提
案方式に加えて，優先順位を設けない方式（FIFO 発
行 Execution-Driven）も比較対象とした．各種アー
キテクチャに対する CPI を図 30，図 31 に示す．
OOO 発行に関しては，理想方式 min(ALL) を用
いることで性能上限である Execution-Driven と遜色
のない CPI が得られている．同様に，提案方式 Lo-cal Distance Steering も良好な CPI が得られており，
Execution-Driven との差は 3.3%である．このことか
ら OOO 発行の場合は，Dispatch-Driven 構成に提案
方式を導入することで，複雑な Execution-Driven に
近い性能が得られることが確認された．FIFO 発行に関しては，Execution-Driven に対し
て小林らの方式を用いることで 4.5% CPI を改善でき
ている．これに対し，Dispatch-Driven の CPI 下限
である min(ALL) は 4.4% CPI が増加しており，提
案方式 Local Distance Steering は 12% CPI が増加
している．このように FIFO 発行の場合は，各方式の
性能は複雑性とのトレードオフなっている．したがっ
て提案方式は，小林らのような複雑な方式にはかなわ
ないが，比較的単純な構成を仮定する場合には有効な
方式であると位置付けられる．
本論文では，命令の発行時刻情報を用いた理想的な
命令ステアリング方式に対する，有効な近似方式を検
討した．先行研究における近似方式では，選択するク
ラスタを（1）Wakeup 遅延に着目して，未解決オペ
ランド生成クラスタ，（2）Select 遅延に着目して，命
令数が少ないクラスタに限定する近似は妥当であった
が，両者から 1 つを選択する部分に近似の劣化が確認
そこで我々は，命令の発行時刻の定義から導出した
近似式を用いて，データ生成命令と消費命令の命令間
距離を用いることで，先行方式よりも高精度な Select
遅延推定を行う Local Distance Steering を提案した．
この方式は OOO 発行のクラスタアーキテクチャに対
して，先行研究 Parcerisa 方式から 9.2%の CPI 改善
を確認し，残る性能向上の余地は 3.3%しか存在しな
いことを確認した．また FIFO 発行のクラスタアーキ
テクチャに対しては，先行研究 Palacharla 方式から5.0%の CPI 改善が確認された．
さらに我々は，Local Distance をより簡単な方法で
近似する Global Distance Steering を提案した．こ
の方式は OOO 発行のクラスタアーキテクチャに対し
て，Parcerisa 方式から 5.7%の CPI 改善が確認され
た．しかし FIFO 発行のクラスタアーキテクチャに
対しては，Palacharla 方式からの改善は確認されな
また，通信遅延やクラスタの発行幅を変えた場合，
あるいはデータキャッシュを理想化しない場合でも，提
案手法 Local Distance Steering が有効であることを
92情報処理学会論文誌：コンピューティングシステムOct. 2004
確認した．さらに，OOO 発行の場合は提案方式を用
いた Dispatch-Driven なクラスタアーキテクチャが，
Execution-Driven に迫る性能を発揮することを確認
今後の課題としては，以下の 2 点を考えている．今
回の提案は，全クラスタにレジスタファイルやキャッ
シュの内容が複製されることを前提としていた．しか
し資源の利用効率を考えると，そのような複製には
無駄が多い．そこで，複製を制限するアーキテクチャ
に対しても提案方式を適用させたいと考えている．ま
た，今回はクロスバ型のネットワークトポロジを前提
にしていたが，リング等の他のトポロジに対しても提
案方式の評価，あるいは改良を行う必要があると考え
謝辞本論文の研究は，一部 21 世紀 COE「情報技
術戦略コア」による．
1) Agarwal, V., Hrishikesh, M.S., Keckler, S.W.and Burger, D.: Clock Rate versus IPC: TheEnd of the Road for Conventional Microarchi-tectures, ISCA 2000, pp.248–259 (2000).2) Seznec, A. and Toullec, E. and Rochecouste,O.:RegisterWriteSpecializationRegisterRead Specialization: A Path to Complexity-Eﬀective Wide-Issue Superscalar Processors,MICRO 2002, pp.383–394 (2002).3) Baniasadi, A. and Moshovos, A.: Instruc-tion Distribution Heuristics for Quad-ClusterDynamically-Scheduled,SuperscalarProces-sors, MICRO 2000, pp.337–347 (2000).4) Canal, R., Parcerisa, J.-M. and Gonz´alez,A.: A Cost-Eﬀective Clustered Architecture,PACT 1999, pp.160–168 (1999).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 is6 to 8 FO4 Inverter Delays, ISCA 2002, pp.14–24 (2002).6) Farkas, K.I., Chow, P., Jouppi, N.P. andVranesic, Z.: The Multicluster Architecture:Reducing Cycle Time Through Partitioning,MICRO 1997, pp.149–159 (1997).7) Kessler, R.E.: The Alpha 21264 Microproces-sor, IEEE Micro, pp.25–36 (1999).8) Kim, H.-S. and Smith, J.E.: An InstrucitonSet and Microarchitecture for Instruction LevelDistributed Processing, ISCA 2002, pp.71–86(2002).9) Kim, I. and Lipasti, M.H.: Half-Price Archi-tecture, 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 Gonz´alez, A.: ReducingWire Delay Penalty through Value Prediction,MICRO 2000, pp.317–326 (2000).12) Parcerisa, J.-M., Sahuquillo, J., Gonz´alez, A.and Duato, J.: Eﬃcient Interconnects for Clus-tered Microarchitectures, PACT 2002, pp.291–300 (2002).13) Raasch, S.E., Binkert, N.L. and Reinhardt,S.K.: A Scalable Instruction Queue Design Us-ing Dependence Chains, ISCA 2002, pp.318–329 (2002).14) Sprangle, E. and Carmean, D.: Increasing Pro-cessor Performance by Implementing DeeperPipelines, ISCA 2002, pp.25–34 (2002).15) Stark, J., Brown, M.D. and Patt, Y.N.:On Pipelining Dynamic Instruction SchedulingLogic, MICRO 2000, pp.57–66 (2000).16) 小林良太郎，安藤秀樹，島田俊夫：データフロー・グラフの最長パスに着目したクラスタ化スーパスカラ・プロセッサにおける命令発行機構，JSPP2001, pp.31–38 (2001).
(平成 16 年 1 月 31 日受付)
(平成 16 年 5 月 21 日採録)
服部直也1976 年生．1999 年東京大学工学
部電子情報工学科卒業．2004 年同
大学院情報理工学系研究科電子情報
学専攻博士課程修了．情報理工学博
士．プロセッサアーキテクチャ等の
研究に従事．
高田正法（学生会員）1979 年生．2003 年東京大学工学
部電子情報工学科卒業．現在，同大学
院情報理工学系研究科電子情報学専
攻修士課程在学中．プロセッサアー
キテクチャ等の研究に従事．
Vol. 45No. SIG 11(ACS 7)発行時間差に基づいた命令ステアリング方式93
1976 年生．1999 年早稲田大学理
工学部電子通信学科卒業．2001 年
東京大学大学院工学系研究科情報工
学専攻修了．現在，同大学院情報理
工学系研究科電子情報学専攻博士課
程在学中．プロセッサアーキテクチャ等の研究に従事．
入江英嗣（正会員）1975 年生．1999 年東京大学工学
部電子情報工学科卒業．2004 年同
大学院情報理工学系研究科電子情報
学専攻博士課程修了．情報理工学博
士．プロセッサアーキテクチャ等の
研究に従事．
坂井修一（正会員）1981 年東京大学理学部情報科学
科卒業．1986 年同大学院工学系研
究科情報工学専門課程修了．工学博
士．同年工業技術院電子技術総合研
究所入所．1991 年～1992 年，米国
マサチューセッツ工科大学招聘研究員，1993 年～1996
年 RWC 超並列アーキテクチャ研究室室長．1996 年
筑波大学電子・情報工学系助教授．1998 年東京大学
大学院工学系研究科助教授，2001 年同大学院情報理
工学系研究科教授．計算機システム一般，特にアーキ
テクチャ，並列処理，スケジューリング問題，マルチ
メディア応用等の研究に従事．著書『論理回路入門』，
『図説コンピュータアーキテクチャ』．電子情報通信学
会，人工知能学会，IEEE，ACM 各会員．
田中英彦（フェロー）
1965 年東京大学工学部電子工学
科卒業．1970 年同大学院工学系研
究科博士課程修了．工学博士．同年
同大学工学部講師．1971 年同助教
授．1987 年同教授．2001 年より同
大学院情報理工学系研究科教授・研究科長．この間1978 年～1979 年米国ニューヨーク市立大学客員教授．
計算機アーキテクチャ，並列処理，自然言語処理，メ
ディア処理，分散処理，CAD 等の研究に興味を持っ
ている．著書『非ノイマンコンピュータ』，『情報通信シ
ステム』，『Parallel Inference Engine—PIE』，共著書
『計算機アーキテクチャ』，『VLSI コンピュータ I，II』，
『ソフトウェア指向アーキテクチャ』．本会フェロー．
電子情報通信学会，人工知能学会，日本ソフトウェア
科学会，IEEE，ACM 各会員．