マルチコアCPU環境におけるL2キャッシュの影響を考慮したVMスケジューラ

全文

(1)Vol.2009-OS-112 No.1 2009/8/5. 情報処理学会研究報告

(2) .

(3)

(4)

(5)

(6) % +

(7) 2 ! 3 "

(8) #

(9)

(10) + .

(11) % - 1

(12) .

(13) "

(14) . . % -

(15) %"

(16) %%!. .

(17) 1 , %#

(18) "

(19) . -

(20) "

(21) .

(22) /% #"

(23) %

(24) "

(25) 1. マルチコア環境におけるキャッシュの影響を考慮したスケジューラ.

(26) % % +

(27)

(28)

(29) ,

(30) % ! 3 %% " 4 " + . !.

(31) % " $ "

(32) 2! 4 "

(33)

(34) . ""#$ % $ "

(35) 2 . +

(36) . #

(37) 5% $#

(38) $

(39) . ! $.

(40) $ + , 6 " -

(41) .

(42)

(43) ,

(44) % ! 7 1 , %

(45) "

(46) " 2 , ,2

(47) % . +. 本吉. 橋田. 哲. 剛Ý 也Ý. 山河. 田野. 浩健. 史Ý Ý 二Ý Ý.

(48)

(49) .

(50) " ! %1 , % % .

(51) 1

(52) 2 +

(53)

(54) -

(55) %

(56) !. はじめに. 仮想化技術を用いたサーバ統合化のためのマシンのとしてが広く普及している．は一つのチップに複数のコアを持ち，同一チップ上に載っているコア同士で共有のキャッシュを持つ．キャッシュミスはの性能を大きく低下させるため，のスケジューリングではコア同士によるキャッシュの競合に注意する必要がある．に対応したプロセススケジューラの研究がされているが，仮想化環境には対応していない．本研究では，仮想化環境においてのキャッシュミスが性能に与える影響を調査し，キャッシュを考慮した仮想マシンスケジューラの設計を行った． ! を用いて実験を行ったところ，上で "#$ % なワークロードを実行したとき，最大で約 &'()のスループットの差があることがわかった．実験結果より，キャッシュを考慮したスケジューリングを行うためにはつの要素が必要であることがわかった．第一に，上で実行するワークロードがキャッシュの影響を受けやすいかを判別することである．第二に，とキャッシュの状態を基に，キャッシュが有効に働くように仮想をスケジューリングすることである． . サーバマシンのとして

(57)

(58) が広く普及している．はつのチップに複数のコアを持ち，同一チップ上に載っているコア同士で共有キャッシュを持つ．共有キャッシュを持つことで，プロセッサ間通信の速度向上や，キャッシュミスの減. を採用したとしてのや，の

(59) などがある．サーバ用途ののトップシェアを持つは年までに数十から数百の物理コアを持つメニーコアの生産を目指している．よって，今後もの物理コア少が見込める．. 数の増加は続いていくと考えられる．. の性能が低下する主な要因の一つはキャッシュミスであることが知れらている．特に，キャッシュミスはメモリアクセスを伴うため，性能に大きな影響を与える．では，複数のコアがキャッシュを共有するので，共有キャッシュの競合が発生し，キャッシュミスの増加を招きやすい．.

(60) . キャッシュミスを減少させるアプローチの一つとして，の物理的なキャッシュサ. イズの増加が挙げられる．しかし，キャッシュサイズを増やすにはハードウェアの変更によ.

(61) Ý

(62) Ý Ý Ý Ý Ý . . . . る再設計のコストや，増加分のキャッシュメモリのコストなど，大きなコストがかかる．ま. . た，キャッシュサイズを増やすことによりキャッシュ面積が増加し，コア用のスペースが減っ. . てしまう．そのため，チップに載せるコア数を増やせなくなるという問題もある．こうした. * "

(63) $" + , % # % - .. Ý 慶應義塾大学. #" , - %

(64) "

(65) # . + #" .

(66) /

(67) !.

(68). 0

(69)

(70) 1

(71) " +

(72) +. Ý 科学技術振興機構.

(73)

(74) 1

(75) %

(76) " "

(77) %

(78) !

(79) " . # %+

(80) % -"

(81) 1 ,

(82) - #

(83) #. . . . ((8 -"

(84) + # -

(85)

(86).

(87) Vol.2009-OS-112 No.1 2009/8/5. 情報処理学会研究報告

(88) . ことから，ソフトウェアが. のキャッシュを効率的に用いることでキャッシュミ. めると共に，今後の課題について考察する．. スを抑えることが必要である．. 関連研究. に対応したプロセススケジューラを備えたの研究が行われている．一方，仮想化環境におけるの対応は遅れている．近年，仮想化技術を用いたサーバの統合化が行われている．サーバの統合化とは，複数台のサーバを台の物理マシン上の仮想マシンで稼働させる手法である．を管理する仮想マシンモニタの役割のつに，物理マシンのリソースの管理がある．上では複数のを稼働させるため，仮想マシンに効果的にリソースをスケジューリングしなければスループットが落ちてしまう．例えば，複数の上でそれぞれ異なるワークロードを動作させたとき，同一チップ上の物理コアで同時に稼働するの組み合わせによってはキャッシュミスが増加し，性能が低下する．という研究結果が報告されている．こうしたことから，仮想化の統合化環境においてのキャッシュを効率的に利用するスケジューラが求められている．本研究では，仮想化環境においてのキャッシュミスがスループットに与える影響を調査し，キャッシュを考慮したスケジューラの設計を行う．仮想化環境におけるキャッシュの影響を調べるために，を搭載する台の物理マシン上で仮想をつ持つを複数稼働させ，キャッシュを考慮したスケジューリングの場合と，考慮していないスケジューリングの場合のそれぞれで上で様々なワークロードを実行した．実験結果より，上で

(89) !" # なワークロードを実行したとき，キャッシュを考慮したスケジューリングと，そうでないスケジューリングとでは最大で約 $%のスループットの差があることがわかった．また，既存のであるのスケジューラがキャッシュを考慮したスケジューリングを行っているかについて分析した．その結果，のスケジューラはキャッシュを考慮に入れないスケジューリングを行うため，スループットが低下することがわかった．実験結果を基に，キャッシュの振る舞いを考慮したスケジューラを設計した．提案スケジューラでは，キャッシュミスの影響を大きく受けるを判別するために上で動作するワークロードを判別する．また，の状態とキャッシュの状態を基に，キャッシュが有効に働くように仮想をそこで現在，. プロセススケジューラ. のキャッシュの影響を考慮したプロセススケジューラが提案されている．らは，変数やロックを共有するスレッドを同時に実行することでキャッシュの再. 利用率を高めるコンストラクティブキャッシュシェアリングの評価を行っている．複数のコアがそれぞれ別のタスクを実行すると，共有キャッシュとメインメモリへの帯域の競合が発生する．コンストラクティブキャッシュシェアリングではワーキングセットがオーバーラップしてるスレッドを同時に実行して全体のワーキングサイズを節約する．従来の '

(90) ( ) * ' スケジューラとコンストラクティブキャッシュシェアリングを実装する )

(91) ). +

(92) + スケジューラを環境で比較した結果，+ が良い性能を発揮することを実証した．仮想化環境では同士が共有リソースを持たないため，+ を適用するの. は困難である．. ,

(93) )#

(94) * は環境下において，変数やロックを共有するスレッド同士を同じチップ上の物理にスケジューリングすることで，オーバーヘッドとなるチップ外. へのメモリアクセスを減らす手法である．マルチスレッドプログラミングでは共有変数やロックなどへのアクセスがボトルネックとなる．そこで，,

(95) )#.

(96) * では各スレッ. ドごとに一定期間中のメモリへのアクセスを記録する．そして，全てのスレッドのメモリアクセスを比較して類似しているアクセスパターンのスレッドをクラスタリングする．仮想化. による統合化環境で動くワークロードの場合，異なる同士で変数やロックを共有することは無いため，,

(97) )#. . スケジューラ.

(98) * を仮想化環境に適用することは困難である．. 前述したように，のプロセススケジューラに関しては，. が研究・提案されている．一方，スケジューラを. に対応するための手法. に対応させるための研究は行わ. れていない．. マルチプロセッサに対応したスケジューラ. はアーキテクチャの上で動作するである．では，以前に仮想を割り当てた物理に，再び仮想を割り当てる Æ スケジューリングを行う．こうすることで，キャッシュの再利用性を高めている． . )

(99) はを拡張したものである．物理ごとに仮想のキューを持つ．アイドル状態. スケジューリングする．. 本論文の構成は以下の通りである．章では関連研究について説明する．& 章ではス. ケジューリングについての実験を行い，その結果について分析する．$ 章ではキャッシュを考慮したスケジューラの設計について考察する．最後に章で本研究の内容をまと. . . ((8 -"

(100) + # -

(101)

(102).


(104) . が他の物理から仮想を奪うギャングスケジューリングを行うこと全体のグローバルな負荷分散を行っている．と . )

(105) 共に，

(106)

(107)

(108) での利用を前提としており，については考慮していない．

(109) は -./ アーキテクチャの上で動作するオープンソースので，商用のサーバでも利用されている．現在のバージョンのはクレジットスケジューラを採用している．クレジットスケジューラは物理間の負荷分散を行うことで，を効率よく利用する．物理間の負荷バランスが崩れた時に仮想が動作する物理を変更することにより，物理間の負荷バランスを取る．クレジットスケジューラは物理間の負荷分散を重視しており，の共有キャッシュの利用に関しては考慮しての物理. で負荷分散する．さらに，定期的に物理. いない．. , "). * は仮想に割り当てる物理のシェアを動的に変更する．ゲストにバルーンモジュールを疑似デバイスドライバとしてロードすることで．ゲストのスケジューリングコードに変更を加えることなくがゲスト内の負荷分散を行うことを可能にする．バルーンモジュールは仮想の速度の偏りを検出したとき，仮想的なワークロードを作り出してゲストのスケジューリングを調整する．, "). * は物理の使用率を上げることを目的としており，本研究の目的とは異なる． . 上で実行するワークロードを考慮したスケジューラ. スケジューリングを効果的に行うために，上で実行するワークロードを考慮してスケジューリングする研究が行われている．. *)

(110) らはによる 0 スケジューリングについての分析を行い，仮想環境での 0 性能を向上させるためのスケジューリングについて議論している．0!" # なワークロードを実行すると， !" # なワークロードを実行するが混在するとき，0 " * や 1 2

(111) による最適化が有効であることを実証した．また，1 ! 3 なワークロードを実行するときは専用ので実行する必要性を示した．4 らは仮想化環境での 0 性能を向上させるスケジューラを考案した．上で実行しているワークロードが 0!" # であるかを識別し，実行するワークロードが 0!" # であると判断したの優先度を上げることで応答時間を短縮する．これらの研究では

(112) !" # なワークロードに関しては考慮していない．. スケジューリングの分析実験本章では，キャッシュを考慮したスケジューラを設計するために，キャッシュ. ミスが性能に与える影響の検証とスケジューリングの分析をするための実験を行った．. 実験環境. スケジューラの挙動を知るため，物理で発生したイベントや，仮想のパラメータなどといった詳細な情報を取得した．これらの情報を得るために，本研究では，商用サーバに広く用いられているオープンソースである仮想化環境の. &5& に分析システ. ムを実装した．. 図 &5 にシステムの概要を示す．内部でハードウェアパフォーマンスカウンタ 6. のイベントを監視する．6 はの ) 7 1*

(113) 1 の一種で，内部で起きたイベントを計測する．6 はカウンタ用 1 と制御用 1 が対になっている．制御用 1 でイベントカウントの有効0無効化と監視するイベントを設定する．指定したイベントの発行数がカウンタ用 1 に格納される．6 は各コアに独立に備わっているため，コアごとにデータを取ることができる．6 は主にシステムのプロファイリングに用いられ，プロファイリング用のツール , や

(114) 7 ，は内部で 6 を利用している．また，6 を用いてシステムの挙動を解析するを用いて物理. 研究が行われている．. が定期的に 6. をサンプリングし，. の内部メモリに内容を出力する．サンプリングデータを出力するために，ドメインからの内部メモリに格納さ. れたサンプリングデータを取得し，取得したデータの内容をファイルに出力する．出力したファイルを解析して分析に用いる．. スケジューラの挙動の分析のために，6. の状態をタイマ割り

(115)

(116) を性能評を求めるために ) 状態でないコアサイクル数を得るの値と各仮想. 込みをきっかけに定期的に出力する．本研究では，価の指標の一つとして用いる．. ための

(117) と完了した命令数を得るための

(118) . を 6. がどの物理で実行されたかをの，仮想が属するの，仮想の，物理が属する物理チップのを. を用いてモニタリングする．また，仮想. 知るために，スケジューリングした仮想. がスケジューリングされた物理. 出力する．. 実験に用いたマシンの構成は表 &5 に示した通りである．特に，. . の構造を図 &5 に. ((8 -"

(119) + # -

(120)

(121).


(123) . 図図. . 表. ( ,

(124). の構造. 分析システムの概要図. . 図. 表. . . 仮想 ( 数. ,

(125). !" # なワークロードを実行した場合の実行時間の. 分布は平均実行時間の± %以上と広い分布になっている．. の構成. . - +. 平均実行時間の分布の違いの原因を調べるため，つの上で

(126). !" # なワーの分布を測定する．実行結果を図 &5$ に示す．図 &5$ はに関しての確率分布を示すヒストグラムになっている．また，キャッシュの影響が少ないと考えられるの分布と比較するために !" # なワークロードを実行したときのの分布を測定した．実行結果を図 &5 に示す．図 &5$ より，

(127) !" # な. クロードを実行したときの. は

(128) アーキテクチャの 8 )# コアで，つのパッケージ内にとつのキャッシュを持ち，キャッシュはつの物理で共有する．は前述の分析システムを実装したを用いた．の構成を表 &5 に示す．上で動作させるワークロードとして， " $5

(129) を用いる． " は ! " #9

(130) !" #9 0!" # なワークロードを生成できるベンチマークである． ! " # なワークロードでは素数判定を行う．

(131) !" # なワークロードではメモリへの書き込みを行う．0!" # なワークロードではファイル 0 のランダムリード0ライ示す．. つの物理チップを搭載する．各物理チップは，それぞれつの物理. ワークロードを実行した場合は分散が大きく，二つの山ができていることがわかる．一方，. !" # なワークロードを実行した場合は図 &5 のように分散の小さな一つの山ができ !" # なワークロードを実行すると，キャッシュの影響により，が低くなる場合とが高くなる場合があると. るのみである．よって，クレジットスケジューラで

(132) 考えられる．. 上で

(133) !" # なワークロードを実行したときの分布で二つの山ができる原因を調べるため，

(134) !" # なワークロードを実行したときの物理チップのスケジューリングパターンとを測定した．スケジューリングパターンとは，物理チップ上の各物理にスケジューリングされている仮想の組み合わせを指す．測定の結果，合計 / 種類のスケジューリングパターンを確認した．その中から，頻度の高かった種類のスケジューリングパターンの一覧を表 &5& に示す．の分布を測定した結果を図 &5/ に示す．横軸はスケジューリングパターンを表し，縦軸はの分布を箱ひげ図によって表したものである．スケジューリングパターン 9 $9 &9 &/ の $ 種類のの分布を見ると，他のスケジューリングパターンに比べて，%近くまで小さくなっている．は 5 の近傍に分布しており，これは図 &5$ のつ目の山. トを行う．単純なワークロードを実行することで，どのような場合に，どのようなワークロードを実行したときに性能に影響が出るかを明確化する．. . クレジットスケジューラによるワークロードの実行時間. に収まっているのに対して，

(135). 物理マシンの構成. ! ""# ## $%&' ))* ' $+$ ))* ' $ + %+. . 既存のスケジューラの挙動の分析. 現在ののクレジットスケジューラの挙動を分析する．まず，つの上で

(136) ! " #， !" # なワークロードを実行した場合の実行時間を測定する．

(137) !" # なワークロードはキャッシュによる影響が大きいと考えられる．実行結果を図 &5& に示す．横軸はワークロードの種類を示し，縦軸は実行時間を示す． !" # なワークロードを実行した場合の実行時間の分布は平均実行時間の± %以内. '. . ((8 -"

(138) + # -

(139)

(140).


(142) . 表. . )*2 3 4. $ 5 # " 5 6 " $ ". 図. . ,

(143) ./ 0 1 の ( の分布. 図. 物理チップ上のスケジューリング. . (*

(144) ) ( # ( ( ( ( ( ( ( ( ( ( ( (. # #. # # # #. . (*

(145) ) ( ( ( ( ( ( ( ( ( ( ( ( (. # # # # # #. リングを示し，縦軸はクレジットスケジューラの実行時間で正規化した値を示す．)

(146) ). (./ 0 1 の ( の分布. )

(147) がもっとも悪いスループットを示す．クレジットスケジューラは )

(148) ) )

(149) の半分 )

(150) はクレジットスケジューラの半分以下の実行時間となっている．クレジットスケジューラは図 &5/ のように，. )

(151) と )

(152) ) )

(153) が入り混. が小さくなるのスケジューリングパターンに共通していることは，に属する仮想が全て同一の物理チップ上にスケジューリングされていることである．これにより，仮想間でキャッシュが効果的に利用され，の低下につながったと考えられる．が小さくなるスケジューリングパターンを一般化したものを図 &5: に示す．このように，に属する全ての仮想が同一の物理チップ上にスケジューリングされている状態をと定義する．また，スケジューリングパターン 9 $9 &9 &/ を除く . 種類のスケジューリングパターンに共通することは，別々のに属する仮想が同一の物理チップ上にスケジューリングされていることである．別々のが実行する

(154) !" # なワークロードがキャッシュの競合を引き起こし，キャッシュミスが増えた結果，が上昇したと考えられる．は &5 の近傍に分布しており，これは図 &5$ のつ目の山の分布に対応している．が大きくなるスケジューリングパターンを一般化したものを図 &5. に示す．このように，に属する仮想が別々の物理チップ上にスケジューリングされている状態をと定義する．スケジューリングによる性能差を比較するために . )

(155) と )

(156) ) )

(157) ，クレジットスケジューラの & 種類のスケジューリングについて，つの上で

(158) !" # なワークロードを実行し，実行時間を測定した．実行結果を図 &5; に示す．横軸はスケジュー. 以下の実行時間である．. の分布に対応している．. じったスケジューリングとなるため，その中間のスループットになったと考えられる．以上のことから，クレジットスケジューラでは上で

(159). !" # なワークロー. ドを実行するとき，キャッシュを考慮せずにスケジューリングを行うため，最適なスケジューリングとは言えないことを実証した．キャッシュを考慮したスケジューリングを行う必要がある．. 同時に実行するワークロードの組み合わせが性能に与える影響前節でつの上で

(160). !" # なワークロードを実行したとき，スケジューリ. ングによってスループットが増減することを示した．本節では，様々なワークロードを組み合わせて実行したときに性能に与える影響を調べる．. つの上で別々のワークロードを実行したときに，キャッシュの影響によって互いのの性能に与える影響を測定する．つの上で，それぞれ !" #9

(161) ! " #9 0!" #9 # のいずれかのワークロードを実行する．# はアイドル状態のワークロードを示す．その他のワークロードについては &5 節で説明した " によって生成したワークロードである．つのではつのワークロードのみを実行するものとする．# !# を除く ; 通りの組み合わせについて実行し，実行時間を測定した．また，ス &. . ((8 -"

(162) + # -

(163)

(164).


(166) . 図. . × の実行時間. )

(167) では . )

(168) と比べて約 &%のスループットの差が出る．これは，)

(169) ) )

(170) ではキャッシュが効果的に利用出来なくなるためと考えられる．次に，

(171) !" # なワークロードを実行している同士の組み合わせでは大きく性能が落ち，. )

(172) と比較すると約 $%のスループットの差となる5 これは，キャッシュが効果的に利用出来なくなることに加えて，

(173) !" # なワークロード同士でキャッシュの競合が発生す図. . るためキャッシュミスが増えるためと考えられる．. !" #9 0!" # なワークロードを実行するでは . )

(174) と )

(175) ). )

(176) の性能差は %以下にとどまった．これらのワークロードでは

(177) !" # なワークロードに比べてメモリアクセスが少ないため，キャッシュの影響が小さいためと考え. 仮想 ( のスケジューリングによる ( の分布. 一方，. られる．. 以上のことから，

(178). !" # なワークロードを実行するをどうスケジューリン. グするかが性能に大きな影響を与えると言える．また，実験結果から性能に影響を与える. 図. 7 * . 図. の状態とキャッシュの状態を分類できる．の状態は . )

(179) 9 )

(180) ) )

(181) のつの状態に分類できる．キャッシュの状態は )9

(182) のつの状態に分類できる．つの物理チップ上にスケジューリングされている

(183) !" # なの数をとすると， ) はが以下，つまり，他の

(184) !" # なによってキャッシュが競合していないことを示す．

(185) はがより大きい，つまり，他の

(186) !" # なによってキャッシュが競合している可能性があることを示す．. ( * . . )

(187) ，)

(188) ) )

(189) の双方の場合について実験する．実験結果を図 &5 に示す．横軸は上で実行するワークロードの種類を表す．，，0 はそれぞれ !" #，

(190) !" #，0!" # なワークロードを表す．まず，

(191) !" # なワークロードを実行しているは )

(192) ). ケジューリングが性能に与える影響を比較するために. の状態とキャッシュの状態が性能に与える影響. 前節でスケジューリングにおいてとキャッシュの状態について分類した．こ. れらの状態が性能へ与える影響を調べるため，とキャッシュの状態の組み合わせを. 9. . ((8 -"

(193) + # -

(194)

(195).


(197) . 図. 図. . 7 * .4

(198). 図. ( * .. 図. . ワークロードの組み合わせによる実行時間. 変えて上で

(199). !" # なワークロードを実行したときのを測定する．状態を比較することで共有キャッシュの影響の大きさを見る．状態の組み合わせは，. )

(200) ! )9 . )

(201) !

(202) 9 )

(203) ) )

(204) ! )9 )

(205) ) )

(206) !

(207) の $ つである．. )

(208) ! ) は図 &5: と同じ割り当てとした．)

(209) ) )

(210) !

(211) は図 &5. と同じ割り当てとした．)

(212) ) )

(213) ! ) と )

(214) ) )

(215) !

(216) の各組み合わせについて，物理チップへのの仮想の割り当てを図 &59 &5 に示す．実験によって得られた各状態の組み合わせについてのの分布を図 &5& に示す．横軸は状態の組み合わせを表し，縦軸はの分布を箱ひげ図で表したものである． ) と

(217) は )

(218) ) )

(219) のとき最大で倍以上のの悪化を招くが，. )

(220) のときは数%の違いであり，影響が小さい．よって，

(221) !" # なワークロードを実行するは . )

(222) になるようにスケジューリングする必要がある．の組み合わせによる. 図. . . の状態とキャッシュの状態の組み合わせによる ( の分布. 数による性能の変化. ジットスケジューラそれぞれの場合について各上で

(223). 前節までで. 実行し，実行時間を計測した．結果を図. がつのとき，

(224) !" # なワークロードを実行するを . )

(225) にするスケジューリングがスループットの面で有効であることを示した．数が増えたときにもこのスケジューリングが有効かを調べるために，数を増やしたときに性能がどのように変化するかを測定する．を $ つに増やし，. )

(226) 9 )

(227) ) )

(228) 9 クレ. × $ の実行時間. &5$ に示す5. !" # なワークロードを. 横軸はスケジューリングを表し，縦. 軸はクレジットスケジューラの実行時間で正規化した値を表す．実験結果から，. )

(229) %短い．よって，数が増えたときにも

(230) !" # なワークロードを実行するを . )

(231) にするスケジューリングが. の実行時間はクレジットスケジューラよりも約. :. . ((8 -"

(232) + # -

(233)

(234).


(236) . であるかを判別するには，. )

(237) と )

(238) ) )

(239) それぞれでワークロードを実行してを一定期間サンプリングする．得られたサンプリング結果の分布を統計処理によって比較し，その差が有意であれば

(240) !" # なであると言える．. 有効に動作すると言える．. キャッシュを考慮したスケジューラ前章で，上で

(241). !" # なワークロードを実行したとき，キャッシュを効果的に利用しなければのスループットが低下することを示した．また，既存のスケジューラはキャッシュを考慮したスケジューリングを行っていないため，

(242) ! " # なワークロードを実行するときスループットが低下することを示した．以上のことから，キャッシュを考慮した新たなスケジューラが必要であると言える．本章では，キャッシュを考慮したスケジューラの設計について述べる．. . の状態の判別. の状態を判別するには，定期的にの仮想がどの物理チップにスケジューが全て同じ物理チップの物理にスケジューリングされていたら . )

(243) であり，そうでなければ )

(244) ) )

(245) である．リングされているかを確認する．の仮想. キャッシュの状態の判別. キャッシュの状態を判別するには各が実行するワークロードの種類が判別されている必要がある．物理チップに割り当てられている

(246) !" # なワークロードを実行するがつならば )，複数ならば

(247) である．実際にスケジューリングを行うには )，

(248) のつの状態の他に，

(249) !" # なワークロードを実行するによって使われていないキャッシュであることを示す状態が必要である．この状態を < と定義する．< は

(250) を避けるようにスケジューリングするとき，仮想の移送先の物理チップを探すために必要になる．. スケジューリングアルゴリズムの概要. キャッシュを考慮したスケジューリングを行うためにはつの機能が必要となる．第一に，上で動くワークロードの種類，の状態，キャッシュの状態等のをスケジューリングする上で必要な情報を得る機能である．& 章において，キャッシュがの性能に与える影響は上で実行するワークロードによって異なることを示した．特に，

(251) !" # なワークロードはキャッシュによる影響が大きい．よって，

(252) ! " # なワークロードを実行するはキャッシュを効果的に利用できるようにスケジューリングをする必要がある．一方，キャッシュによる影響が小さいワークロードを実行するはキャッシュの利用よりも負荷分散を重視したスケジューリングをする必要がある．上で動くワークロードに応じて適切なスケジューリングを行うためには，上で実行しているワークロードの種類をから判別する必要がある．また，

(253) !" # なが有効にキャッシュを利用できているかをを判別できること，

(254) !" # なの移送先となる物理チップを判断するためのキャッシュの状態を判別できる必要がある．第二に，取得した情報を基にキャッシュを効果的に利用できるように仮想 . スケジューリング. がキャッシュミスによってスループットが低下することを防ぐためにの状態を . )

(255) にするスケジューリングを行う．では通常のクレジットスケジューラと同様の負荷分散を行う．

(256) !" # なワークロードを実行するが . )

(257) 状態になったとき，その時点でを実行している物理チップの物理に全てのの仮想を関連付ける．こうすることで，. )

(258) の状態を保つことができる．おわりに. のキャッシュを効果的に利用するスケジューラの必要性を示し，キャッシュを考慮したスケジューラの設計について示した．の性能低下の要因のつはキャッシュミスである．キャッシュが効果的に利用できるかによってスループットが大きく変動する．また，同じ物理チップ上で同時に実行する同士のキャッシュの競合がスループットに影響を与える．既存のスケジューラでは，. をスケジューリングする機能である．. 本研究では，. システムの状態の判別上で動くワークロードの判別. & 章の実験結果より，

(259) !" # なワークロードを実行するの特徴は . )

(260) )

(261) ) )

(262) それぞれで実行した場合のの分布の差である．. )

(263) と )

(264) ). )

(265) のの分散は小さく，ある値に集中している．また，集中しているの値に両者で明確な違いがある．

(266) !" # なワークロード以外を実行するでは，の分布に明確な差は表れない．よって，が実行する未知のワークロードが

(267) !" # と. キャッシュが性能に与える影響を考慮せずにスケジューリングするため，スループットの低下を引き起こすことがある．本研究では，これらのことを実証する実験を行った．その結果，.

(268) !" # なワークロードを実行するはキャッシュの影響によってスループッ ;. . ((8 -"

(269) + # -

(270)

(271).


(273) .

(274) ) * ) )"

(275)

(276) 9 3 ', 3 - 39 59 B 5$9 5$G$$: ;;:5 ; H 3 9 459 , # 9 59 6 )*9 F5 )# 1 " 9 5? . )

(277) # ?

(278)

(279) ))* * 3

(280) )

(281) )

(282) #!

(283)

(284)

(285) 9 3 ', 3 - 39 5.9 B 5&9 5;G/ 5 > * 9 <59 39 59 H 3 9 45 )# 1 " 9 5? ?

(286) * #

(287) ) * ) )"

(288)

(289) 9 3 ', 3 - 39 59 B 5$9 5$G$$: ;;:5 ). 9 5? 4. & % -,& 9

(290) 6).

(291) 9

(292) )## 13

(293) 9 B=9 :5 *9 59 )

(294) 9 =59 ( * #9 <5 )# ) @(9 5? , @)

(295) # ) )" !

(296)

(297) 3

(298) ) )9 5 6 7 - -', '9 >

(299) ( 9 9 9 <B ! ) $5 & *)

(300) 9 59 -9 55 )# 1-

(301) 9 5? # * 0 3

(302) ) ) !

(303) 9 !" #!$ % & ' 9 B@ F

(304) (9 BF9 9 9 5G .5 $ 49 659 9 659 = *9 =59 = 9 65 )# 9 =5? ,)(!)@)

(305) 3

(306) ) ) # * C

(307) 0

(308) C

(309) )59 8 /8 !

(310) " #!$ % & ' 9 B@ F

(311) (9 BF9 9 9 5G ;5 95

(312) 6/ * 0& ,

(313)

(314) ) ? .5 !"# ## $"$#5 /

(315)

(316) ) 9 5? ,

(317) C

(318) ) ) A

(319) 5 ! #%$ !"#$#&$'("5 : = 3 9 5 <5?

(320) 7 !

(321) 7

(322) C

(323) -5 % #" % ' 5 . =)(9 59

(324) 9 59 9 59 4 9 59 )9 ,5 )# F 9 65? 5 # ") !"$5 ; 9 459 D *9 59 @)

(325) ()#)9 59 9 59 @)

(326) 9 5 )# D)*9 5? 6)

(327) #@)

(328)

(329) #

(330) 3 ! !I

(331) 2 *)

(332) 9 "$ )6 . ,, , '' , - '9 B@ F

(333) (9 BF9 9 9 5.;G .5 4 39 5? >? )

(334) C

(335) ) ")

(336) (5 #*#+ #" % ' 5. トが大きく変化することを確認した．. 実験結果から，キャッシュを考慮したスケジューラが備えるべき要件を二つ示し. た．第一に，システムの状態を取得する機能である．キャッシュを考慮したスケジューリングをするためには，

(337). !" # なワークロードを実行する，の状態，キャッシュの状態等の情報をが知る必要がある．第二に，システムの情報を基にキャッシュを効果的に利用するために

(338) !" # なワークロードを実行するの状態を . )

(339) に保つことである．今後の課題は，本研究で示したスケジューラの実装である．また，既存のスケジューラとの比較実験を行う予定である．. 参考. 文. 献. 6 #9 =59 >) )9 =5 )# 4 9 5? +

(340) ) +@

(341) ) ? ,

(342) )!) * 1)

(343) 3

(344) 3@9 ,)

(345)

(346) 9

(347)

(348) ) /5 +#

(349) 3)9 59 A

(350) 9 59 ). 9 5 )# B ") 9 5?

(351) C

(352) ) C !

(353) )##

(354)

(355) )# ) C

(356)

(357) ) * #*9

(358) 5 & )

(359) ) 9 59

(360) 9 159 D)*9 59 B@. 9 5 )# #

(361) 9 ,5? )

(362) )

(363) A) E )) C )

(364) 3

(365) #) ")

(366) (9 !" #!$ % &

(367) ' 9 B@ F

(368) (9 BF9 9 9 5G& .5 $ +#

(369) 3)9 59 ). 9 59 B ") 9 5 )# A

(370) 9 5?

(371) )#* ! # ) @

(372) ) * #

(373) 9 ()) )) * +

(374) , !$ , * + ,9 B@ F

(375) (9 BF9 9 9 5; $5 ,)9 59 A9 15 )# 9 5? ,

(376) )#

(377) *? )

(378) *!)@)

(379) # ! * ! !,

(380)

(381) 9 - . / !$# - , ', - ' /.9 B@ F

(382) (9 BF9 9 9 5$:G. :5 / 9 59 H"" 9 5>59 4 A 9 59 )( 3 9 59 ))(9 59 > . 9 H5<59 +) )79 >59 +-9 59 6)

(383) #)3. )9 B59 @

(384) 9 ,5 5 )# ' (

(385) 9 5? # *

(386) )# C

(387)

(388) 3 ) )

(389) * 9 . -', ' ' 9 B@ F

(390) (9 BF9 9 9 5G :5 : > #!'(A

(391) 9 59 9 659 9 159 ) 9 F59

(392)

(393) 9 +5 45159 9 5 559 ' 9 5 )# D)*9 F5 5 F5 D5D5?

(394) ? )

(395) ) * C

(396) )

(397) 9 $, - ' 0 ',' 1$02 .5 . > * 9 <59 39 59 H 3 9 45 )# 1 " 9 5? ?

(398) * # 8. . ((8 -"

(399) + # -

(400)

(401).

(402)