5E-3

複数パス実行プロセッサのためのキャッシュメモリの提案
高野 直樹 田中 英彦 坂井 修一
ftakano, tanaka, sakaig@mtl.t.u-tokyo.ac.jp

東京大学大学院 工学系研究科 3

1 はじめにTtI

±ûtI

プロセッサの処理性能向上に対し、主記憶に使われている DRAM の処理速度が追い付かなくなり、プロセッサにデータ供給が十分に行われなくなるようになった。
このプロセッサとメモリーとのパフォーマンスギャップを解決するために、プロセッサと主記憶の間にキャッシュメモリが用いられてきた。
今後プロセッサの 1cycle に実行された命令数 (IPC1 )が向上するに従って、今まで以上に十分なデータを供給できるキャッシュの研究が不可欠である。本稿では次世代プロセッサとして現在研究が進められている複数パス実行プロセッサのためのキャッシュメモリについてポート数に着目し提案を行う。

½Mù,1 ¦^·Start
BranchStart
BranchBranchBranchTtION1*½Mù,1 ¦^·-Goal

Goal

図 1: 単一パス実行と複数パス実行の違い

2 複数パス実行プロセッサ多くなる。当然 1cycle あたりの Load/Store の数もマルチパス実行によって増えることが考えられる。
現在使われている Super Scalar プロセッサでは、分岐キャッシュへのアクセスを考えると Store は実行のパ予測を行い単一パスの投機的実行を行っているが、3〜4スが確定しない限り、すなわち Store 命令が In order 状
IPC が性能の限界と言われている。更に IPC の向上を態にならない限りキャッシュへの書き込みは起らない。
計るには、分岐予測ミス時のペナルティーを削減を行う
Store がキャッシュへ書き込みを行うタイミングはキャッために、分岐成立と不成立の投機的な両パスの実行を行シュの上流に存在する Load/Store キューで吸収するのう必要がある。これが複数パス実行プロセッサである。
で、キャッシュでそれを考える必要はない。プログラム
図 1に単一パス実行と複数パス実行の違いを示す。図はそれぞれ一定の割合で In Order になる Store が含ま中の単一パス実行では分岐予測失敗時にペナルティーがれているので、同じプログラムを実行すれば、実効 IPC発生しているが、複数パス実行では分岐成立と不成立のに比例したキャッシュへの Store による書き込みが起る
両パスを実行するのでペナルティーは存在しない。またと考えられる。
各パスは投機的に実行されるので IPC は単一パス実行
一方 Load は投機的に実行されたパスからも要求されよりも向上することがわかる。
るので、Load/Store キュー内にそのデータが存在すれば良いが、見つからないとキャッシュへ読み込みの要求複数パス実行プロセッサにおけるキ が送られる。Load/Store キューの大きさや複数パス実行のアルゴリズムによるが、実行 IPC に比例した数以ャッシュのポート 数の考察
上にキャッシュへの読み込みの要求が増える可能性があキャッシュが 1cycle で同時にデータの読み書きが行え る。つまり従来の Super Scalar プロセッサよりも 1cycleる数をポート数と呼ぶ。ここでは複数パス実行プロセッサ で同時にキャッシュへの読み込み要求が増えることが考におけるキャッシュメモリをポート数の観点から考える。 えられる。
以 上の よ うに 複数 パス 実 行プ ロセッサにお いて はLoad/Store ともに従来の Super Scalar で用いられてきた
3.1
ポート 数増加の必要性
キャッシュよりもポート数を増やす必要性が考えられる。

3

複数パス実行は単一パス実行と比較して、無駄なパスの命令も投機的に実行されるので、実行される命令数は
3

Naoki Takano, Hidehiko Tnaka and Shuichi Sakai

University of Tokyo, Graduate School of Engineering,
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan

1

Instrucion Per Cycle の略

3.2

従来のポート 数の増加手法

SRAM を理想的に多ポート化するとポート数の自乗分の実装コストがかかる。そのため従来のキャッシュの多ポート化には 3 つの手法が取られてきた。1 つは時分割法、1 つは複製法、そして Bank 分割法である。

時分割法はキャッシュに使われている SRAM のクロッ
クをプロセッサの複数倍率で駆動することによりポートè)N
Lazy Store·.
Load/Store
Buffer.;=数を増やす手法である。しかしこの方法で増やせるのはLazy.Store¡~L
せいぜい 2〜3 ポートが限界であり、スケーラビリティStoreLazyLoadLoadStoreに欠けるので、多ポート化には向かない。
StoreStore
Bit
複製法は同じ内容のキャッシュをポート数だけ用意し、読み込みのポート数を増やす手法である。これは実装コストがポート数倍かかるのと、書き込みの際一貫性を保つため書き込みのポート数は 1 のままであるのが欠点である。
Addr Data
Bank 分割法は SRAM を複数 Bank に分割し、アドレ
4-port Replicated Cacheスによって分散配置を行うことでポート数を増やす方法
K)1Cache.Store"LBufferL`ðである。しかしこの方法は Bank 化されたキャッシュとLoad/Store ユニットを接続するため Crossbar 等の相互結合網が必要であり、同じ Bank への衝突が起る可能性 図 2: 複製法をベースにした新しい多ポートキャッシュがある。
現在の半導体の集積度の問題から考えると、複製法よ 存する。Stored Bit 全てがセットされたらそのエントリりも Bank 分割法の方がトランジスタを有効に利用でき は Lazy Store Bu er から消去する。Load/Store キュー
るため、利点が大きいように思われる。しかし今後 10 から Store データのエントリが削除される時にまだ Lazy年間の半導体テクノロジー予測 [2] を参照すると、将来 Store Bu er に残っている時は、強制的にキャッシュにキャッシュに使えるトランジスタ数は数億個オーダーにな 対して書き込みを行うことで一貫性を保つ。
本手法は Load/Store キューからデータが追い出されり、Bank 分割が必ずしも有利な手法とは言えなくなる。
るまでの時間を使うので、Load/Store キューのエントリ3.3
複製法のキャッシュを使った Lazy Store 数が小さい時には Lazy に Store を行う時間が少なくなってしまい効果は低下する。このため Load/Store キュー
ここで、複製法のキャッシュに対して新しく Store 専 のエントリ数を考えた上での定量的評価が重要である。
用の Bu er を設けることで、遅延書き込みを行えるようにしたキャッシュを新たに提案する。このキャッシュをまとめ
図 2に示す。
次世代プロセッサとして研究されている複数パス実行Bank 分割法より複製法を選んだのは Bank 衝突を起こさず効率良く Load 要求に答えるためである。過去の研 プロセッサの概要を述べ、キャッシュシステムの多ポー
究 [1] においては Bank 分割法をベースにした手法が提案 ト化の重要性を述べた。その後、複製法を用いたキャッされていたが、この手法では Load/Store ともに Latency シュに対する Lazy Store の提案を行った。今後は Superが増加する可能性があり、異なったラインの Bank 衝突 Scalar プロセッサと複数パス実行プロセッサのシミュレーが起るのは回避できない。また複数パス実行プロセッサ タを用いて本手法の定量的な評価を行う予定である。
本研究の一部は、文部省科学研究費補助金 (基盤研究においては、Super Scalar プロセッサと比較して Store
より Load の方が数が増えることを想定して、Load と親 (B) 課題番号 11480066) および、(株) 半導体理工学研究センターとの共同研究によるものである。
和性が高い複製法を選択する。

4

本手法は複製法におけるキャッシュへの書き込みは 1ポートしか行えない欠点を補うため、Store の際起る書 参考文献
き込みを Lazy に行うことで、Store の書き込みのポート[1] Jude A. Rivers, Gary S. Tyson, Edward S. David数を仮想的に増やす。
son and Todd M. Austin, \On high-bandwidth data
Store データはキャッシュに書き込みの要求を行った
cache design for multi-issue processors, \ Inter後でもしばらくの間 Load/Store キューに留まっており、
national Symposium on Microarchitecture, Pages
その間はキャッシュにアクセスする必要はない。そこで
46-56, December 1-3, 1997, Research Triangle Pk
ポートが塞がっている時は、Store 要求が出されても一United States.
度にキャッシュに書き込みを行わずに、一時的に LazyStore Bu er に保存する。キャッシュは常に全てのポー [2] Semiconductor Industry Association, International
トを占有されている訳ではなく、一時的に Load/StoreTechnology Roadmap for Semiconductors 1999 Ediユニットからの要求が来ない時があるので、空いた時間
tion. http://www.itrs.net/ntrs/publntrs.nsf
を使って Lazy Store Bu er にある古いデータから Storeを行う。Store の実行後そのキャッシュの Stored Bit をセットし、どのキャッシュにすでに書き込まれたかを保