ストアキューの拡張によるロードトラフィックの削減方式
吉瀬謙二y , 斎藤英一z , 入江英嗣y , 坂井修一y , 田中英彦y
東京大学大学院工学系研究科y株式会社日立製作所 日立工業専門学院z
1 はじめに2 データキャッシュのポート 数ªËÆÉ¼ ËÆ £Æ¸» ¸Ë¸ ÆÉÎ¸É»ÀÅ¾ |

アウトオブオーダ実行をおこなうプロセッサは、ストア 本評価で採用した Alpha AXP アーキテクチャの 1 ワー
命令をインオーダに処理するためにストアキューを利用 ド は 8byte であり、256 個のストア・データを保存するする。このストアキューのエントリを数百という規模に ためには容量 2KB の連想記憶が必要となる。
拡大するとともに、命令がリタイアされた後もエントリ
に余裕がある限りデータを保持することで、多くのローªËÆÉ¼ ¨Ì¼Ì¼ ÅËÉÐ

ド命令の要求をストアキューで処理することを検討する。

この拡張により、今後予測されるデータ供給機構のポート数増加の問題緩和を目指す。


データキャッシュのマルチ・ポート化には幾つかの戦略
がある [1] 。IBM Power2, DEC Alpha21264 ではキャッ
シュをプロセッサの倍速で動作させることで 2 ポートを実現する。MIPS R10000 ではキャッシュを 2 バンクに分割することで、異なったバンクへのアクセスを同時に可¾ÆÄÂÊÀÄ
¾ºººÆÄÇÉ¼ÊÊ
ÃÀÀÁÇ¼¾Ç¼ÉÃ
ÍÆÉË¼Ï
¤
能としている。DEC Alpha21164 ではキャッシュを 2 つに複製し、一貫性を維持することで 2 ポートを実現して
図 1: ストアキューのエントリ数と供給できるデータいる。このような中、更なる命令レベル並列性の利用を目指した研究が進められており [3] 、それに見合うポー 4 ストアキューの拡張によるロードトラフィックの削減
ト数の確保が課題となっている。
図 1の予備評価結果より、ストアキューのエントリ数を3 スト アキューとデータ参照の時間的局所性大きくすることで、約半分のデータをストアキューからアウトオブオーダ実行をおこなうプロセッサは、キャッ 供給できる可能性があることがわかった。しかし、ストシュの更新をインオーダに処理するためにストアキュー アキューとキャッシュの両方にロード の要求を出していを利用する。このような目的でストアキューを実装した ては、ロードユニットとキャッシュとのトラフィックを削場合には、キャッシュに値を書きこんだエントリはスト 減することはできない。このため、図 2に示す様に、ローアキューから開放してかまわない。一方、キャッシュに ド 命令をストアキューからデータを得るものと、キャッデータを書きこんだ後にもエントリを開放せず、データ シュからデータを得るものに分類し、それぞれのバッファをストアキューから供給するように設計することもでき にのみロード の要求を出す方式を検討する。
る。この場合、新しくエントリが必要となった時点で、6WRUH 8QLW
/RDG 8QLW/RDG 8QLW
最も古く割り当てられたエントリを開放する。エントリ$GGUHVVが開放されるまで、ストアキューは各エントリのデータ'DWD'DWDを供給できるバッファとなる。本研究ではストアキュー
6WRUH$GGUHVVを両方の目的で利用する。
4XHXH
ストアキューのエントリ数を 16〜512 に変化させて、$GGUHVV'DWD$GGUHVV'DWDストアキューから供給できるデータの割合を測定した。
'DWD &DFKH
スカラプロセッサ環境を用いて測定したため、n エント
図 2: ストアキューの拡張とトラフィックの分散リのストアキューからデータを供給できる割合は、ロード するデータが、先行する n 個のストア命令において生利用するバッファの選択方法として、動的予測や静的情成された値である割合となる。測定結果を図 1に示す。
報の利用が考えられる。図 2の機構により、ロード ・ト
この結果から、先行する 256 個のストアからロードできラフィックを 2 つのバッファに分散させ、ポート数増加る確率は平均で 51%となることがわかる。の効果を得るには、適切なバッファにロード要求を出す、それぞれのバッファに均等にロード要求を出す、という2 つの条件を満たす必要がある。最初の条件を満たせなyい場合には、ストアキューにデータを要求したが、そのzデータをストアキューからは供給できないといった状況

Load Trac Decrease with Extended Store Queue
Kenji KISE, Eiichi SAITO, Hidetsugu IRIE,
Shuichi SAKAI, and Hidehiko TANAKA
Graduate school of Engineering, The University of Tokyo
Hitachi, Ltd.

5 スト アキュー利用の動的予測利用するバッファを分類するために動的予測の利用を検討する。コンパイラ等を用いた静的な情報付加は今後の課題である。動的な予測機構として 2 ビット・カウンタ方式（ 4096 エントリのダイレクトマップ ）, JRS 予測器[2]（ 4096 エント リの予測テーブル、閾値 8 ） を評価した。ストアキューのエントリは 256 エントリを想定した。

Programgom88ksim
gcc
compressliijpeg
perlvortex

2BC
37.54%, 2.84%
63.84%, 0.43%
41.39%, 1.77%
53.06%, 0.79%
55.16%, 1.40%
33.64%, 2.32%
50.83%, 1.77%
51.25%, 2.65%

JRS
6.25%, 0.88%
59.24%, 0.31%
20.52%, 1.04%
47.73%, 0.28%
48.33%, 0.45%
18.08%, 0.89%
43.79%, 0.35%
35.82%, 0.95%

表 1: ストアキュー利用の動的予測結果

アキューを用いている。ストアキューの利用については5章で検討した 2BC を用いた。設定 c から f は、両方のバッファにリクエストを送る通常のプロセッサ・モデルであり、比較のために用意したモデルである。
©¼ËÀÉ¼» ÅÊËÉÌºËÀÆÅÊ §¼É ÐºÃ¼ ªÌÊË¸ÀÅ¼»

が発生する。この場合には、次のサイクルにキャッシュへのアクセスが必要となり、ロード 命令の実行レイテンシを 1 サイクル増加させることになる。2 番目の条件を満たせない場合には、キャッシュにアクセスするロード命令が集中して実行されるといった状況が発生し、バッファの利用率が低下する。

 ¸º¿¼   ª¨  ¸º¿¼   ª¨  ©¼¸» ÇÆÉË  ©¼¸» ÇÆÉË  ©¼¸» ÇÆÉË  ©¼¸» ÇÆÉË Å½ÀÅÀËÐ










¾Æ

ÄÂÊÀÄ ¾ºº ºÆÄÇÉ¼ÊÊ

ÃÀ

ÀÁÇ¼¾

Ç¼ÉÃ

ÍÆÉË¼Ï¤

図 3: 拡張したストアキューによる性能向上
評価結果を図 3に示す。キャッシュのポート数 1 を想定した場合の評価は、設定 a と c の結果を比較すればよい。
この時、拡張されたストアキューを用いることで IPC1.7の向上を確認できた。同様に、キャッシュのポート数 2を想定した場合、設定 b と d の結果を比較すればよい。
この時、拡張されたストアキューを用いることで IPC0.5の向上を確認できた。

表 1に結果を示す。2 ビット・カウンタ方式 (2BC), JRS
予測器 (JRS) それぞれについて、ストアキューからデータを供給できると正しく予測した割合と、ストアキュー 7 まとめからデータを供給できると予測してミスした割合を示し ストアキューをデータ参照の時間的局所性を利用する
た。割合は、実行した全ロード命令に対するものである。 バッファとして利用するために、ストアキューのエント
この結果から、分岐履歴を用いて予測する JRS の利点 リを 256 という大きな値に設定するとともに、ロード要はそれほど大きくないことがわかる。特に go, ijpeg に 求をキャッシュとストアキューに分散させ、キャッシュついては、JRS で予測できる割合が大きく低下する。 とロード ユニットのトラフィックを削減する方式を検討

6 スト アキューの拡張と性能評価

スーパースカラのシミュレータを用いて、拡張したス
トアキューを評価する。本評価では、ミスを起こさないデータキャッシュを仮定した。また、メモリシステムに厳しい負荷を与えるために、分岐ミスをおこさない理想的な分岐予測機構を仮定した。シミュレータの主な実行パラメタを表 2にまとめる。

Parameter
Bandwidth of fetch and retire
Instruction window
Memory latency
The number of functional unit

Value
16 instr. per cycle
128 entries
2 cycle / 3 cycle
No limitation

表 2: 評価に用いたプロセッサ・モデルのパラメタ
キャッシュのポート数 1 とストアキューのポート数 2(設定 a) 、キャッシュのポート数 2 とストアキューのポート数 2(設定 b) 、ポートの数を 1(設定 c), 2(設定 d), 4(設定 e), 無限大 (設定 f) 、という 6 つの設定においてプロセッサ性能を測定した。設定 a, b では、拡張されたストした。
ストアキュー利用の動的予測に関して、2 ビット・カウンタ方式と JRS 予測器を評価し、前者が適していることを示した。スーパースカラのシミュレータを用いて本方式を評価し、特にキャッシュのポート数が少ない場合に、本方式が有効であることを確認した。
参考文献[1] Jude A. Rivers, Gary S. Tyson, Edward S. Davidson, and Todd M. Austin. On High-Bandwidth
Data Cache Design for Multi-Issue Processors. In
Proc. of MICRO-30, pages 46-56, 1997.
[2] Erik Jacobsen, Eric Rotenberg, and J. E. Smith.
Assigning con dence to conditional branch predictions. In Proc. of MICRO-29, pages 142-152, 1996.
[3] 中村友洋, 吉瀬謙二, 辻秀典, 安島雄一郎, 田中英彦.
大規模データパスプロセッサの構想. 情報処理学会
計算機アーキテクチャ研究会, Arch 124, pp.13-18,
Jun.1997.