命令ウィンド ウの動的最適化
吉瀬 謙二, 中村 友洋, 辻 秀典, 安島 雄一郎, 高峰信, 坂井修一, 田中 英彦
東京大学大学院工学系研究科
1 はじめにがある。この利点より、本モデルでは集中ウィンド ウをプロセッサが抽出できる並列性は、データ依存関係が解消され機能ユニットに発行できる命令を解析する能力採用する。
幾つかのモデルにおいては命令ウィンドウにイン・オー(先見能力) に依存する。さらにプロセッサの先見能力を ダの情報も格納する場合がある。これらのモデルは、ハー決めるパラメタは命令ウィンド ウとリオーダ・バッファのエントリ数である。

ド ウェア量の節約という点から重要であるが、ここでは、命令を発行するためのバッファとしての命令ウィンド ウ(

本稿では、フェッチ機構、オペランド 供給、結果バスとイン・オーダの情報を保つためのバッファ リオーダ・といったハード ウェア資源を理想化したプロセッサ・モ

バッファ を分けて議論を進める。これより集中ウィン)デルを定義する。その上で先見能力の制約を変化させ、 ド ウに格納されていた命令が発行された時点で当該エン得られる並列性について検討する。

トリを開放し、それらのエントリには任意の命令を格納

2 命令ウィンド ウすることができるようになる。

命令をアウト・オブ・オーダに発行するためには、デコード・ステージと実行ステージを分離し、両者の間で実行可能な命令を動的に抽出し、実行待ちの命令をバッファする機構が必要である。この目的で設けられるバッファを命令ウィンド ウと呼ぶ。フェッチ、デ ィスパッチ、発プロセッサの正確な割込みを実現するために用いるリオーダ・バッファにはディスパッチされてからリタイアされるまでの全命令に対して、イン・オーダにエントリが割り付けられる。これよりイン・オーダなレジスタ・(1行、実行という処理の流れを図 に示した。命令ウィンyª°æÆºè ØªÆÄ

ド ウから機能ユニットに命令を発行するためには当該命令で必要となるオペランド が利用可能かつ、必要なハーäåí!Ê
G0Ðó¯

ド ウェア資源が利用可能となっている必要がある。

図ï»¼Â
Ø¤§î§ö­VÃÂ éÎÆË1: アウト・オブ・オーダ発行のためのウィンド ウ

図í­VÃU õUÓÆØ¤Ê¶VÃ Ê¦¼ÔÆÄè©¦öÌ©

¥©Ë­Ù Â éÎÆË­ VÃÂ éÎÆËyªyª°æÆºèÊ¶VÃ©¦öÌ©
yªØªÆÄ Ê¦¼ÔÆÄÈ Â éÎÆË§ö­VÃ)

ファイルへの書き込み リタイア を実現できる。

ÈÂ éÎÆË È ... Â éÎÆË2: 評価に用いたプロセッサ・モデル

正確な割込みをサポートする場合、命令ウィンド ウの3 命令ウィンド ウとプロセッサ・モデルエントリ数だけでなく、リオーダ・バッファのエントリ数が先見能力に影響を与える。図 3 はこの様子を説明す2 に示し るものである。アウト・オブ・オーダに発行された命令命令ウィンド ウを含むプロセッサ・モデルについてはさまざまな方式が提案されているが、本稿では図たモデルを検討する。

は、命令ウィンド ウのエントリから削除されるため、命多くのスーパースカラ・プロセッサではそれぞれの機

令ウィンド ウのエントリには連続した命令が格納されて能ユニット毎に分割されたウィンド ウ（リザベーション・ いるとは限らない。また、命令ウィンド ウのエントリにステーション）を用いている。別の選択は集中ウィンド 空きがあったとしても、リオーダ・バッファのエントリウを用いる方法で、ロジックが複雑になるという欠点がに空きがなければデ ィスパッチがストールしてしまう。

あるものの、エントリ数を有効に利用できるという利点

図 から明らかなように、リオーダ・バッファのエント3リ数以上の命令ウィンド ウのエントリ数は必要ない。
Dynamic Optimization of Instruction Window
Kenji KISE, Tomohiro NAKAMURA, Hidenori TSUJI,
ロード 命令に関しては、リオーダ・バッファ内のスト
Yuichiro AJIMA, Makoto TAKAMINE, Shuichi SAKAI,
ア命令との依存関係を検出できると想定する。これより、
Hidehiko TANAKA
Graduate school of Engineering, The University of Tokyo ロード 命令は依存関係のないストア命令を追い越して発で増加することに意味がある。ただし、リオーダ・バッ行できるようになる。

yª©¦öÌ©Í«öËíÐ¤íyªÌÊ¦¼ÔÆÄ·îÈ È¦Ì¦yªÌ

Ðyªí­VÃUÓÆØ¤Ð«öËíN§öU­VÃ

図õU¹Áyªí1»íõU¹ÁyªÌµµàÉÐ·è®§ö­VÃU¼ÉVËôoW

3: あるプロセッサ状態における先見能力

256 を想定した場合には、命令ウィン
64 を越えたところで IPC が飽和すファのエントリ数ド ウのエントリ数がる。以上の検討より、命令ウィンド ウとリオーダ・バッ

32, 128 または 64, 256 とした場合IPC を飽和させないためバッファ構成であり、命令ウィンド ウのエントリ数の 4 倍がリオーダ・バッファのファのエントリ数をが4 評価環境エントリ数の目安となることがわかった。

ド ウとリオーダ・バッファのエントリ数を変化させた場

きなかっが、現在いくつかのプログラムを解析中である。

3章で定義したプロセッサ・モデルに従い、命令ウィン合のcc1 の解析結果しか検討することがで時間の都合上、IPC (1 サイクルにリタイアした平均命令数) を測 6 関連研究定する。ディスパッチ、発行、リタイアの幅はそれぞれ命令ウィンド ウのエントリ数を変化させた時の性能は文10 命令とする。ロード・ユニット 2 つ、ストア・ユニッ 献 [1] に詳しいが、(1) 分岐ユニットとロード /ストア・
ト 2 つ、分岐ユニット 2 つ、それ以外の命令を処理するユニットがそれぞれ一つしか存在しない。(2) 分岐命令、ALU を 6 つという構成 (IPC10 を可能とする構成) とす ロード /ストア命令はインオーダで発行する。という制る。フォワーディング・パスと結果バスの数は制限して約により速度向上比はそれほど得られていない。より多いない。理想的な命令フェッチ機構を仮定した。2 ポー
くの IPC をターゲットとした場合には、先の制約は厳トのミスをおこさないデータ・キャッシュを仮定する。
アーキテクチャはしすぎる。汎用アプ リケーションにおける分岐命令の実

SPARC architecture version 8 を 行頻度は 20% 以上となることが多く、1 サイクルに 1 つ用いる。リオーダ・バッファ、命令ウィンド ウのエント以上の分岐命令を処理する必要がある。また、ロード ・32 から 256 まで変化させる。解析時間の都 ストア命令をインオーダに処理するという制約が並列性合上、SPEC95 から cc1 に関する 4700 万命令の実行ト抽出のネックとなる可能性がある。
リ数ともにレースを解析する。

7

5 評価結果と検討

命令ウィンド ウ、リオーダ・バッファと先見能力の関係³²±° ÆÍÀ
¯

¯²³
®¯µ

Ïâìïáâï ³±¿òããâï Ðæ÷â °¯¯²³

まとめと今後の課題®¯µ³±°¯をまとめ、それらのエントリ数を変化させた場合の並列性(IPC) を検討した。

評価において、データ・フォワーデ ィングのパスや、結果バス、レジスタ・ファイル等のポート数は制限していない。本稿で示した

IPC を達成するプロセッサを設計[3] で指摘されているようしようとした場合には、文献®にデータ・フォワーデ ィングのパスが複雑になるなど、­多くの問題点が発生する。本稿で示したÔæëáìô Ðæ÷âIPC を実現するためのアーキテクチャの提案は今後の課題である。

本稿では考慮しなかったが、文献 [2] で提案されてい4: エントリ数を変化させた場合の IPC (cc1)
るように参照データの値予測をおこなえば真のデータ依
cc1 の評価結果を図 4 に示した。右下の共に 32 の設 存関係さえ解消できる場合がある。本評価で得た並列性
図定が標準的なプロセッサの先見能力を想定しており、こには、まだ改善できる余地が残っている。

IPC は 2.6 である。一方、先見能力を最も高く設 参考文献定した (図の左上で、エントリ数を共に 256 とした) 場[1] マイク・ジョンソン. スーパースカラ・プロセッサ. 日経
合の IPC は 5.7 という結果を得た。先見能力の向上に
BP センター.
より 2.2 倍の IPC が利用可能となることがわかる。
[2] Mikko H. Lipasti, Christopher B. Wilkerson, and John
Paul Shen. Value Locality and Load Value Prediction.
次に、図 4からエントリ数と IPC の関係を検討する。
ASPLOS VII, pages 138{147, 1996.
ウィンド ウのエントリ数 32 の時には、リオーダ・バッ[3] Subbarao Palacharla, Norman P. Jouppi, and J. E.
ファのエントリ数が 128 を越えた所で IPC が飽和してSmith. Complexity-E ective Superscalar Processors.
24th Annual Int. Symp. on Computer Architecture,いることがわかる。一方、ウィンド ウのエントリ数 64
pages 206{218, 1997.
以上の時にはリオーダ・バッファのエントリ数を 256 まの時の