物理HDD ホストOS ホストOSホストOS ホストOS ホストOSキャッシュ ゲストOSキャッシュ ゲストOS アクセス要求 アプリケーション H i t H i t
二重キャッシュ環境における負の参照の時間的局所性を
考慮したキャッシュ管理手法
杉本洋輝
†1山口実靖
†1 近年，クラウドコンピューティングの普及に伴い仮想化環境の重要性が高まっている． 仮想化環境下において，ホスト OS キャッシュ(下位キャッシュ)へのアクセスはゲスト OS キャッシュ(上位キャッシ ュ)を介して行われる．このような二重キャッシュ環境下において上位キャッシュの置換アルゴリズムに LRU が使用 されている場合，下位キャッシュにおいては一度アクセスされたデータが近い将来に再度アクセスされる可能性が低 くなり，通常とは逆向きの負の参照の時間的局所性が存在することが実 OS で確認されている． また，二重キャッシュ環境ではゲスト OS キャッシュとホスト OS キャッシュに同一のデータを重複して格納してい る可能性が高い． このように，ホスト OS キャッシュは負の参照の時間的局所性やゲスト OS キャッシュとのデータの重複により有効 に機能しない．本研究では，仮想化環境に適したキャッシュ置換手法を提案し，評価によりその有効性を示す．A Cache Replacement Algorithm in Virtualized Environment
with Two Caches
HIROKI SUGIMOTO
†1SANEYASU YAMAGUCHI
†11．はじめに
近年，クラウドコンピューティングの普及に伴い仮想化 環境の重要性が高まっている．仮想化環境下において，ホ スト OS キャッシュ(下位キャッシュ)へのアクセスはゲス ト OS キャッシュ(上位キャッシュ)を介して行われる．こ のような二重キャッシュ環境下において，上位キャッシュ の置換アルゴリズムに LRU が使用されている場合，下位 キャッシュにおいては一度アクセスされたデータが近い 将来に再度アクセスされる可能性が低くなり，通常とは逆 向きの負の参照の時間的局所性が存在することが実 OS で 確認されている[1]．また，二重キャッシュ環境ではゲス ト OS キャッシュとホスト OS キャッシュに同一のデータ を重複して格納している可能性が高い． ホスト OS キャッシュは負の参照の時間的局所性やゲス ト OS キャッシュとのデータの重複により有効に機能しな い．そのため，負の参照の時間的局所性とデータの重複を 考慮した置換手法が必要である． また，近年普及が進んでいるクラウドコンピューティン グ環境では，物理マシン上に複数の仮想マシンを稼働させ， 契約者に提供する．このような例では，資源提供者側が自 由に仮想マシンの資源を増減させることができず，仮想マ シンの数が少なく資源に余裕のある物理マシンではメモ リ資源をホスト OS が管理した状態のまま性能向上を図る ことが重要となる． 本稿では，二重のキャッシュで構成される仮想化環境に 適したキャッシュ置換手法を提案し，評価によりその有効 性を示す．2 ．負の参照の時間的局所性
アプリケーションが発行するデータアクセス要求には 多くの場合偏りがあり，LRU などのメモリ管理技法の多 くはこの参照の局所性の概念に基づいている．多くの場合， 参照の時間的局所性を考慮したメモリ置換手法を用いる ことにより下層の低速記憶装置の記憶容量よりも小さい キャッシュでも十分な性能を発揮することができる． しかし，仮想化環境のような二重キャッシュ環境では通 常とは逆向きの負の参照の時間的局所性が存在する．ホス ト OS キャッシュへのアクセスは，図 1 のようにゲスト OS キャッシュを介して行われる． 図 1 二重キャッシュ構造 †1 工学院大学大学院†1Department of information and Communications Engineering, Kogakuin University
「マルチメディア，分散，協調とモバイル (DICOMO2014)シンポジウム」 平成26年7月
アプリケーションから発行された要求がゲスト OS キャ ッシュ，ホスト OS キャッシュの両キャッシュでミスヒッ トした場合，両キャッシュには同一のデータが格納される． しかし，最近アクセスされたデータへのアクセス要求はゲ スト OS キャッシュ上で処理され，ホスト OS キャッシュ に届くことはない．従ってホスト OS キャッシュでは“最 近アクセスされたデータは近い将来再度アクセスされる 可能性が低い”という通常とは逆向きの負の参照の時間的 局所性が存在する． また，負の参照の時間的局所性はベンチマークのデータ サイズが十分に大きい時，上位キャッシュのサイズが大き いほど影響が大きくなることが確認されている[1]．
3 ．関連研究
二重キャッシュ環境を考慮したキャッシュ置換手法や 二重キャッシュ環境に適したキャッシュ置換手法として， 以下の手法がある． 3.1 2Q(two Queue) 2Q は Johnson らによって提案された 2 つのリストを用 いるキャッシュ置換手法である[2]． FIFO 列 A1in と LRU 列 Am を用いてデータを保管し，初めてアクセスしたデー タは A1in に格納し，2 回目以降は Am に格納する．置換 が必要になった際，A1in のサイズが拡張可能閾値よりも 小さく拡張可能である場合は Am の中で最も長い時間使 われていないデータを置換対象に選択する．A1in が拡張 可能でないときは A1in の中で最も古いデータを破棄し， その識別子を A1out に保管する．本手法は多重キャッシュ 構造を考慮した手法ではないが，後述の MQ などの多重キ ャッシュ用置換アルゴリズムの研究にて参照されている． 3.2 MQ(Multi Queue) MQ はネットワークストレージのキャッシュのような 2 次キャッシュのために提案されたアルゴリズムである[3]． 一度アクセスされたデータは近い将来に再度アクセスさ れることはなく，ある程度長い時間がたってからのみ再度 アクセスされることを考慮し，データを履歴に長期間保管 することでキャッシュヒット率向上を目指したアルゴリ ズムである．MQ は 2Q を参考にしており，複数の LRU 列 を維持してデータを管理する．各データをどの列に格納す るかはアクセス頻度によって決定され，最下位の列で最も 長い時間参照されていないデータを破棄対象とする．破棄 したデータの ID とアクセス頻度が Qout 列に保管される． データが再びアクセスされときは，Qout に保管してあっ た情報にもとづき格納する LRU 列を決定する．LRU 列のデータには expire Time が設定されており，参照 がないままこの時間に達すると，1 つ下位の LRU 列に移 動される．LRU 列内のデータが参照されると，参照回数 が更新され，新しい参照回数にもとづき格納 LRU が再計 算される
4 ．二重キャッシュ環境における参照の時間的
局所性の解析
4.1 二重キャッシュ環境における参照の局所性の解析 仮想化環境おいて下位キャッシュ（ホスト OS キャッシ ュ）に対する参照の局所性の調査を行う．図 2 の様な実験 環境を構築し，図 2 内の“Monitoring”の箇所を流れるア クセス要求を調査した．図 2 内の“Monitoring”の箇所を 流れるアクセス要求はゲスト OS のキャッシュを経由し た(キャッシュミスした) 後のものであり，ホスト OS キャ ッシュへの参照の局所性を調査することができる． 図 2 の実験環境にてベンチマークソフトである FFSB (Flexible File System Benchmark) を実行した．仮想化環 境において，実験に使用した計算機の仕様は表 1，表 2 の 通り，FFSB の設定は表 3 の通りである．なおモニタリン グはゲスト OS の仮想ブロックデバイス層(xvd 層)にて行 った． 図 2 参照の局所性解析環境 表 1 実計算機の仕様 OS CentOS6.3(64bit) Kernel Linux 2.6.32.57CPU Intel(R) Celeron(R)
HDD 3TB Memory 16GB Cache 15.45GB 仮想化システム Xen 4.1.1.8 使用ファイルシステム ext2 表 2 仮想計算機の仕様 OS CentOS6.3(64bit) Kernel Linux 2.6.32.57
CPU Intel(R) Celeron(R)
HDD 50GB Memory 1GB,2GB Cache 0.87GB, GB 使用ファイルシステム ext2 表 3 FFSB の設定 Data Size 8GB File Size 1MB Num File 8192 OP Size 1MB 4.2 解析結果 アクセス間隔とアクセス発生確率(確率密度関数)の関 係を図 5，図 6 に示す．再アクセス間隔とは，一度データ へのアクセスがされてから，もう一度同じデータへのアク セスが来るまでに他のデータへ何 GB アクセスしたかを 表している． 上位キャッシュサイズを変えた 2 つの測定結果両方で 負の参照の時間的局所性が確認できた．図 3 には再アクセ
ス間隔 0.4GB 以下，図 4 には再アクセス間隔 0.6GB 以下 の再アクセスがほとんど発生していない．また，上位キャ ッシュとなるゲスト OS のメモリサイズを増やすことで 再アクセスが発生しない間隔が長くなり，負の参照の局所 性が強くなることがわかる．
5 ．二重キャッシュ環境におけるキャッシュヒ
ット率の測定
5.1 測定方法 本章において，実 OS のキャッシュのヒット率の測定を 行う．上位キャッシュ（ゲスト OS キャッシュ)，下位キ ャッシュ(キャシュホスト OS キャッシュ)の各キャッシュ ヒット率を求めるため，図 5 の様な実験環境を構築した， 図 5 内は仮想化環境を示す．また，キャッシュヒット率を 求めるため，図 5 の“Monitoring”の箇所を流れるアクセ ス要求を調査した． 図 5 内の“Monitoring”(A)から(D)の箇所を流れるアク セス要求は順に，アプリケーションから発行され上位キャ ッシュに入ってくるアクセス要求，上位キャッシュでキャ ッシュミスしホスト OS に送られるアクセス要求，上位キ ャッシュでキャッシュミスし下位キャッシュに送られて くるアクセス要求，下位キャッシュでキャッシュミスし物 理 HDD に送られるアクセス要求である．また，各キャッ シュミス率は，各キャッシュに入る前のアクセス要求量 (図 5 の A や C)をキャッシュを経由した後のアクセス要求 量(図 5 の B や D)で割ることにより近似的に求めることが できる．なお上位キャッシュのモニタリングはブロック層， 下位キャッシュのモニタリングは SCSI 層にて行なった． 図 7 の実験環境で FFSB を実行した．実計算機および仮想 計算機の仕様は表 4，表 5 にしめす． 図 5 キャッシュヒット率測定環境 表 4 実計算機の仕様 OS CentOS6.3(64bit) Kernel Linu2.6.32.57CPU Intel(R) Celeron(R)
HDD 3TB Memory 16GB 仮想化システム Xen 4.1.1.8 使用ファイルシステム ext2 表 5 仮想計算機の仕様 OS CentOS6.3(64bit) Kernel Linux 2.6.32.57
CPU Intel(R) Celeron(R) 仮想HDD 50GB
Memory 2GB～12GB 使用ファイルシステム ext2
図 3 上位キャッシュ 1GB 時の参照の局所性
5.2 測定結果 上位（ゲスト OS）キャッシュ，下位（ホスト OS）キ ャッシュのキャッシュヒット率を図 8～図 11 に示す．ゲ スト OS メモリサイズとは，VM に与えたメモリのサイズ であり，ゲストが使用できるメモリのサイズである．ゲス ト OS は，このうちの一部をカーネルやユーザプロセスに 割り当て，残りの全てをページキャッシュ（ゲスト OS キ ャッシュ）に割り当てる．図の横軸は FFSB のデータサイ ズを示し，図の左軸はキャッシュヒット率を示し，また図 の右軸は FFSB によって得られたスループットを示して いる．また，両キャッシュヒット率とはゲスト OS キャッ シュまたはホスト OS キャッシュでヒットした確率を近 似的に求めたものである．これは，上位キャッシュに入っ てくるアクセス要求量を，物理 HDD に対して発行される アクセス量を割ったものである． すべての図において，ゲスト OS キャッシュヒット率が 100%のときにホスト OS キャッシュヒットが存在しない のは，すべてのアクセス要求がゲスト OS キャッシュで処 理されるためホスト OS キャッシュに要求がこないため である． まず，ホスト OS キャッシュヒット率について考察する． ゲスト OS に 12GB と 14GB 割り当てた実験に着目すると ホスト OS キャッシュヒット率はほぼ 0%となっており， ホスト OS に割り当てたメモリが有効に機能していない ことがわかる．また，ゲスト OS キャッシュが大きいとき （図 9 から図 11 など）は，データサイズの増加に対する ホスト OS キャッシュヒット率の低下の速度が高いこと がわかる．仮にホスト OS キャッシュへの参照に局所性が なく，全てのブロックに対して均等の確率で要求がくると するとホスト OS キャッシュヒット率は「ホスト OS キャ ッシュをデータサイズで割ったもの」となるはずである． データサイズの増加とともにホストヒット率はこの速度 を超えて低下しており，負の参照の時間的局所性により， ホスト OS に割り当てたメモリが有効に機能しなかった ため性能が劣化してしまったと考えられる． 次にスループットに着目して考察する．スループットは ゲスト OS キャッシュヒット率が 100%であるときが最も 良く，次にホスト OS キャッシュヒット率が 100%である ときが良い．ホスト OS キャッシュヒット率が 100%のと きが，ゲスト OS キャッシュヒット率が 100%の時に比べ てスループットが低い理由として，ゲスト OS キャッシュ でヒットした場合よりホスト OS キャッシュでヒットし た場合のほうが，アクセス要求に対する応答速度が遅い ことが挙げられる．二重キャッシュ環境では，アクセス要 求のあったデータをまず上位キャッシュ（ゲスト OS キャ ッシュ） に存在するか確認し，存在しない場合下位キャ ッシュ（ホスト OS キャッシュ）に該当データが存在する か確認する．そのため，ゲスト OS キャッシュに該当デー タが存在せず，ホスト OS で該当データが存在した場合で もゲスト OS キャッシュに該当データが存在するか確認 するため，ゲスト OS キャッシュでヒットした場合に比べ て CPU 処理が多くかかってしまい，アクセス要求に対す る応答速度が遅くなり，スループットの低下の原因となっ ていると考えられる． 0 500 1,000 1,500 2,000 2,500 3,000 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Thr oug hput[MB /s] キ ャッ シ ュ ヒッ ト 率 [%] DataSize[GB] ゲストOSキャッシュヒット率 ホストOSキャッシュヒット率 ホストOSキャッシュ/データサイズ比 両キャッシュヒット率 Throughput 0 500 1,000 1,500 2,000 2,500 3,000 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Thr oug hput[MB /s] キ ャッ シ ュ ヒッ ト 率 [%] DataSize[GB] ゲストOSキャッシュヒット率 ホストOSキャッシュヒット率 ホストOSキャッシュ/データサイズ比 両キャッシュヒット率 Throughput 0 500 1,000 1,500 2,000 2,500 3,000 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Thr oug hput[MB /s] キ ャッ シュ ヒッ ト 率 [%] DataSize[GB] ゲストOSキャッシュヒット率 ホストOSキャッシュヒット率 ホストOSキャッシュ/データサイズ比 両キャッシュヒット率 Throughput
図 6 ゲスト OS メモリ 2GB
キャッシュヒット率
図 7 ゲスト OS メモリ 4GB
キャッシュヒット率
図 8 ゲスト OS メモリ 6GB
キャッシュヒット率
6 ．負の参照の時間的局所性を考慮したキャッ
シュ置換
6.1 負の参照の時間的局所性を考慮したキャッシュ置換 上位キャッシュ，下位キャッシュ両キャッシュでミスヒ ットした場合，両キャッシュには HDD から読み込まれた 同じデータが格納される．しかし，最近参照されたデータ への要求は上位キャッシュで処理され下位キャッシュに は届かない．これを考慮し，ホスト OS キャッシュでは最 後に参照されてからの時間が最も短いデータを破棄対象 とする（MRU）手法を提案する．また，上位キャッシュ から破棄されるデータを監視し，破棄データを下位キャッ シュに最後に参照されてからの時間を最長（最も破棄され にくい状態）として格納する．上位キャッシュから破棄さ れたデータを格納する理由は，上位キャッシュから破棄さ れたデータは上位キャッシュに存在しないため，両キャッ シュでのデータの重複が起きないためである． アクセス要求がゲスト OS キャッシュでヒットした場合 の動作（図 12）を説明する．アプリケーションからペー ジ D へのアクセス要求が来たとする．ページ D はゲスト O S に存在するため，ゲスト OS は下位層に要求を転送せ することなくアプリケーションにデータを返す．また，ゲ スト OS キャッシュは置換アルゴリズムに LRU を用いて いるためヒットしたページ（ページ D）をゲスト OS キャ ッシュにおいて最も破棄されづらい状態（LRU の先頭） とする． 次に，アクセス要求がホスト OS キャッシュでヒットし た場合の動作（図 13）を説明する．アプリケーションか らページ G へのアクセス要求が来たとする．提案手法で は，ホスト OS キャッシュは置換アルゴリズムを MRU と しているため，ヒットしたページ（ページ G）をホスト OS キャッシュにおいて最も破棄されやすい状態とする． 次に，ゲスト OS はゲスト OS キャッシュにページ G のコ ピーを格納する．ゲスト OS キャッシュの最後尾データは ゲスト OS から破棄され，ホスト OS キャッシュに最も破 棄されづらい状態（最後に参照されてからの時間が最長） で格納される．これに伴い，ホスト OS キャッシュでは， 最後に参照されてからの時間が最短のページ G が破棄さ れる．また，ホスト OS キャッシュで破棄対象のページ G を破棄する． 次に，アクセス要求が両キャッシュでミスヒットした場 合の動作（図 14）を説明する．アプリケーションからペ ージ K へのアクセス要求が来たとする．ページ K はゲス ト OS キャッシュ，ホスト OS キャッシュの両キャッシュ に存在しないため，物理 HDD からデータの読み込みが行 われる．その時，提案手法ではゲスト OS キャッシュでの みページ K を格納し，ホスト OS キャッシュにはページ K を格納しない．この時，ゲスト OS キャッシュで破棄対象 のページ E をホスト OS キャッシュに最も破棄されにくい 状態で格納する．また，ホスト OS キャッシュで破棄対象 のページ J を破棄する．提案手法は以上の動作により両キ ャッシュのデータの重複を抑える事ができる． 6.3 負の参照の時間的局所性を考慮したキャッシュ置換 の評価 シミュレーションによりキャッシュヒット率を評価し た．シミュレーションではキャッシュおよびディスクは 4KB ブロックに管理されているものとした．上位キャッシ ュの置換アルゴリズムには LRU を用い，下位キャッシュ の置換アルゴリズムを変えてシミュレーションを行った． データサイズは 10GB とし，アクセス分布は一様分布とし た．図 15～図 17 にシミュレーション結果を示す． まず，各手法のヒット率を比較すると，すべての例にお いて提案手法のヒット率が高く，提案手法が有効であるこ とがわかる． 次に， LRU のヒット率について述べる．シミュレーシ ョンの結果より LRU は今回使用したアルゴリズムの中で 最もヒット率が低いことがわかる．また，下位キャッシュ のサイズが同じ場合でも上位キャッシュのサイズを増や すと下位キャッシュヒット率が低下する事がわかる．この 理由は２つ考えられる．一つは上位キャッシュのサイズを 大きくしたことにより負の参照の時間的局所性の影響がpageA pageB pageC pageD pageE
ゲストOSキャッシュ (LRU) 破棄優先度低→ ホストOSキャッシュ (MRU) 破棄優先度低→ ゲストOSキャッシュ ホストOSキャッシュ 破棄優先度低→ 破棄優先度低→
pageF pageG pageH pageI pageJ
pageF pageH pageI pageJpageG pageA pageB pageCpageDpageE
pageDへのアクセス要求
破棄対象
ゲストOSキャッシュ ホストOSキャッシュ
pageF pageH pageI pageJ pageA pageB pageC pageE pageF
pageD
破棄対象
pageA pageB pageC pageD pageE
ゲストOSキャッシュ (LRU) 破棄優先度低→ ホストOSキャッシュ (MRU) 破棄優先度低→ ゲストOSキャッシュ ホストOSキャッシュ 破棄優先度低→ 破棄優先度低→
pageF pageGpageH pageI pageJ
pageF pageH pageI pageJpageG
pageA pageB pageC pageDpageE
pageGへのアクセス要求
pageG
ゲストOSキャッシュ ホストOSキャッシュ
pageF
pageG
pageH pageI pageJ pageA pageB pageC pageD pageE
pageG
破棄対象 破棄対象
①
②
③
pageA pageB pageC pageDpageE 破棄優先度低→
破棄優先度低→
pageK pageA pageB pageC pageD
ゲストOSキャッシュ ホストOSキャッシュ 破棄優先度低→
破棄優先度低→
pageE
pageF pageG pageH pageI pageJ
pageF pageG pageH pageI pageJ
破棄対象 破棄対象
pageA pageB pageC pageD pageE
ゲストOSキャッシュ (LRU) 破棄優先度低→ ホストOSキャッシュ (MRU) 破棄優先度低→
pageF pageG pageH pageI pageJ
pageKへのアクセス要求 pageK ① ② ③
図 12 ゲスト OS キャッシュヒット時の動作
図 13 ホスト OS キャッシュヒット時の動作
図 14 両キャッシュミス時の動作
大きくなり，参照の時間的局所性を期待している LRU が 効果的に機能しなかったためである．もう一つの理由は， 上位キャッシュのサイズが大きくなったことにより，両キ ャッシュのデータの重複が増えたため，上位キャッシュで ミスヒットしたデータは下位キャッシュでもミスヒット する可能性が高くなり，ホスト OS キャッシュヒット率の 低下に繋がったと考えられる． 次に，下位キャッシュの置換アルゴリズムに提案手法を 選択した場合のヒット率に着目して考察する．LRU のヒ ット率が上位キャッシュの増加とともに低下するのに対 し，提案手法のヒット率は上位キャッシュの増加ともに向 上していることがわかる．上位キャッシュの増加ともにヒ ット率が向上した理由として，提案手法では負の参照の時 間的局所性を考慮し，最近参照のあったデータを破棄対象 とするためと考えられる．また，提案手法では，データの 重複が発生しないため，下位キャッシュが効果を持たない データを格納することがない．これもキャッシュヒット率 が向上した理由考えられる． 次に，下位キャッシュの置換アルゴリズムに MQ を選択 した場合のヒット率に着目して考察する．下位キャッシュ の置換アルゴリズムに MQ を選択した場合は LRU と変わ らない性能となり，有効に機能していないことがわかった． MQ は参照回数に基づき格納する LRU 列を決定するが， 今回の測定ではすべてのデータが１つの LRU 列に入って しまい実質的に LRU と同じ動作となり，同等の性能とな った．今回の測定では，MQ の文献[3]で推奨する （f は参照回数）に基づき格納 LRU 列を決定したが，これ では適切に動作しないことがわかり，MQ ではこの決定方 法を調整しないと高い性能を示せないことがわかった．
7．おわりに
本稿では，仮想化環境下における負の参照の時間的局所 性の紹介と負の参照の時間的局所性を考慮した置換手法 の提案をし，評価した．その結果，提案手法は 多くの OS で採用されている置換アルゴリズムである LRU よりも高 い性能を示すことがわかった． 今後は，代表的なホスト OS である Linux への実装を行 っていく予定である． 謝辞 本研究は JSPS 科研費 24300034, 25280022, 26730040 の助 成を受けたものである参考文献
[1] 竹内洸祐，山口実靖, “複数サーバ接続ネットワーク ストレージ環境での参照の局所性の解析“第 24 回 コンピ ュータシステム・シンポジウム (ComSys 2012)[2]Theodore Johnson, Dennis Shasha, “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm,” Proceedings of the 20th International Conference on Very Large Data Bases (1994)
[3]Yuanyuan Zhou and James F. Philbin, Kai Li “Second-Level Buffer Cache Management,” IEEE Transactions on parallel and distributed systems, vol. 15, no. 7, JULY 2004
0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 2 3 4 5 キ ャ ッ シュ ヒ ット 率 [% ] 下位キャッシュサイズ[GB] LRU MQ FIFO RAND LFU MRU FIX 提案手法 図 15 シミュレーション結果，上位キャッシュ 2GB 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 2 3 4 5 キ ャ ッ シュ ヒ ット 率 [% ] 下位キャッシュサイズ[GB] LRU MQ FIFO RAND LFU MRU FIX 提案手法 図 16 シミュレーション結果，上位キャッシュ 3GB 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 2 3 4 5 キ ャ ッ シュ ヒ ット 率 [% ] 下位キャッシュサイズ[GB] LRU MQ FIFO RAND LFU MRU FIX 提案手法 図 17 シミュレーション結果，上位キャッシュ 4GB
