マルチコアCPUの電力消費特性を考慮した仮想CPUスケジューラ

全文

(1)情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ吉. 田. 哲也†1 山田浩史†1,†3 佐々木河野健二†1,†3 中村宏†2. 広†2. クラウド環境を提供する仮想化データセンタにおける消費エネルギーを削減するために，Dynamic Voltage and Frequency Scaling（DVFS）を利用した CPU の電力制御が行われている．ここで，既存のマルチコア CPU には，すべてのコアの周波数を揃えて下げないと消費エネルギーの削減効果が小さいという特性がある．ところが，既存の VM 環境はこの性質を考慮していないため，効率良く消費エネルギーを削減できていない．本論文では，VM 環境において，先にあげたマルチコア CPU の電力消費特性を考慮した仮想 CPU（VCPU）スケジューラである Accele スケジューラを提案する．Accele スケジューラは，すべてのコアに同周波数の VCPU がスケジューリングされる時間を長くすることで，すべてのコアの周波数が揃って下がる時間を長くし，DVFS による消費エネルギー削減を大きくする．また，クラウド環境で一般的に行われている work-conserving なプロポーショナルシェアリングを行う．SysBench と SPEC CPU2006 を用いて実験を行った結果，Xen のスケジューラである Credit スケジューラと比べ，消費エネルギーを最大 22.8%小さくすることができた．. this paper, we propose an energy-conscious Virtual CPU (VCPU) scheduler that takes the above characteristic of multicore CPUs into account. Our scheduler, named Accele scheduler, schedules VCPUs by considering the frequency of them to increase the probability that all cores run the same frequency VCPUs simultaneously. As a result, the frequencies of all cores are lowered simultaneously with high probability, and therefore we can gain higher energy savings with DVFS. In addition, Accele scheduler performs work-conserving and proportional-share scheduling, which is common in the cloud computing environments. We evaluate Accele scheduler with SysBench and SPEC CPU2006. The evaluation showed that Accele scheduler reduced the energy consumption of the CPU by up to 22.8% compared with Xen’s Credit scheduler.. 1. はじめに近年，クラウドコンピューティングへの関心が高まっている2) ．クラウド環境で動作するアプリケーションは，処理に必要な量に応じてハードウェアリソースを使うことができるため，余分なリソースを用意することによるコストの浪費や，リソース不足によるアプリケーションの性能低下を避けることができる．このようなクラウド環境は，仮想化技術を利用したコンソリデーションによって実現している．各アプリケーションを仮想マシン（VM）上で動かすことで，ハードウェアリソース量を柔軟に変更できる．クラウドコンピューティングへの関心が高まる一方で，クラウド環境を提供するデータセンタにおける消費エネルギーの増加が問題となっている．その理由の 1 つとして，データセ. Considering Power Consumption Characteristics of Multicore CPUs for Energy Efficient Virtual CPU Scheduling Tetsuya Yoshida,†1 Hiroshi Yamada,†1,†3 Hiroshi Sasaki,†2 Kenji Kono†1,†3 and Hiroshi Nakamura†2 Dynamic voltage and frequency scaling (DVFS) is performed to reduce energy consumption in virtualized data centers used as a platform of cloud computing. However, DVFS provides inefficient energy savings in existing VM environments, because of the characteristic of multicore CPUs that DVFS cannot save significant amount of energy unless the frequencies of all cores are lowered. In. 25. ンタの運用に必要な電力コストが高いことがあげられる．ヒューレットパッカード社の調べによると，1.3 MW 規模のデータセンタにおける年間の電力コストは 1 億 2 千万円にのぼるとされている7) ．そこで，VM 環境を利用したデータセンタにおける消費エネルギーを削減するために，様々な研究が行われている10),14),15),19),21),22) ．データセンタにおける電力消費量を削減する方法の 1 つとして，サーバマシンの CPU の消費エネルギー削減がある．近年の CPU は，動作周波数と動作電圧を動的に変更する. Dynamic Voltage and Frequency Scaling（DVFS）1),9) を備えており，ワークロードに合 †1 慶應義塾大学 Keio University †2 東京大学 The University of Tokyo †3 科学技術振興機構 CREST CREST, Japan Science and Technology Agency. c 2011 Information Processing Society of Japan .

(2) 26. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. わせて DVFS を利用することで消費エネルギーを減らすことができる．ところが，既存のマルチコア CPU の消費エネルギーは，最速のコアの周波数に大きく依 14). Accele スケジューラをオープンソースの VMM である Xen 3) に実装した．そして，Accele スケジューラの効果を調べるために，Xen のデフォルトスケジューラである Credit スケ. ．近年のマルチコア CPU は，動作周波数を各コアごとに設定で. ジューラと比較実験を行った．実験では，SysBench と SPEC CPU2006 に含まれる CPU. きる1),9) ．その一方で，動作電圧はすべてのコアで共通となる．動作電圧を制御するレギュ. バウンドなワークロードとメモリバウンドなワークロードを使い，消費エネルギーを測定し. 存するという特性がある. レータは面積が大きく，コアごとに設置することが難しいため，すべてのコアでレギュレー. た．その結果，実験に用いたすべてのワークロードの組合せにおいて，Accele スケジューラ. タを共有していることが原因である16),26) ．この制限から，一番高い周波数のコアが必要と. の方が消費エネルギーが小さくなり，その差は最大で 22.8%となった．これにより，Accele. する動作電圧がすべてのコアにかかる．CPU の消費電力 P ，動作周波数 F ，動作電圧 V. スケジューラが CPU の消費エネルギーを大きく削減できることが示された．. 2. の間には，P ∝ F V の関係があり，動作電圧の大きさは消費電力に大きく影響する．した. 以降の構成は次のとおりである．まず，2 章でマルチコア CPU の電力消費特性に関して. がって，マルチコア CPU において，DVFS を使って効率良く消費エネルギーを下げるため. 述べる．3 章で本研究の提案である Accele スケジューラについて述べ，4 章でその実装に. には，すべてのコアの周波数を揃えて下げる必要がある．ところが，既存の VM 環境では，. ついて述べる．提案手法の有効性を示すために行った実験について 5 章で述べ，6 章では本. このようなマルチコア CPU の特性が考慮されていない．. 研究に関連する既存研究について述べる．最後に，7 章で，本論文をまとめる．. 本研究では，VM 環境において，マルチコア CPU の電力消費特性を考慮した仮想 CPU （VCPU）スケジューラである Accele スケジューラを提案する．Accele スケジューラは，. 2. マルチコア CPU の電力消費特性. 同周波数の VCPU を同時にスケジュールする時間を長くすることで，すべてのコアの周波. 既存のマルチコア CPU は，すべてのコアの周波数を下げないと DVFS による消費エネ. 数を揃えて下げられる時間を長くし，DVFS による消費エネルギーの削減効果を大きくす. ルギーの削減が小さいという特性がある14) ．これは，周波数が一番高いコアが必要とする. る．そのため Accele スケジューラは，各コアのランキューが持つ VCPU の周波数の分布が. 動作電圧が，すべてのコアにかかることが原因である．動作電圧を制御するレギュレータは. 近くなるように，周波数を考慮して VCPU の分配を行う．そして，各ランキューにおいて. 面積が大きく，コアごとに設置することが難しい．そのため，すべてのコアでレギュレータ. VCPU を周波数の昇順にソートしてからスケジューリングする．これにより，各コアで低. を共有しており，すべてのコアで動作電圧が同一になる16),26) ．したがって，動作電圧を下. い周波数の VCPU から順にスケジューリングされるため，すべてのコアの周波数が揃って. げるためには，すべてのコアの周波数を下げる必要がある．. 下がる時間が長くなる．また Accele スケジューラは，クラウド環境で一般的となっている. 2.1 予備実験. work-conserving なプロポーショナルシェアスケジューリングを行う．work-conserving ス. 先にあげたマルチコア CPU の特性を実証するために予備実験を行った．2 コアのマルチ. ケジューリングを行うことで，高い CPU 利用率を保つ．そして，プロポーショナルシェアリ. コア CPU の各コア上で無限ループを実行し，各コアの周波数を変えて消費電力を測定した．. ングを行うことで，VCPU ごとに指定した割当て量に従うように CPU 資源を割り当てる．. 実験に用いた CPU は，AMD Opteron Quad-Core 2384 である．この CPU は，各コアの. ここで Accele スケジューラは，各 VCPU の周波数が適切に設定されていることを前提. 周波数を 2.5 GHz，1.8 GHz，1.3 GHz，0.8 GHz に設定できる．本実験では，最高周波数の. とする．VM 環境で DVFS を行う場合，各ゲスト OS や VMM が持つ電力制御機構が，各. 2.5 GHz と最低周波数の 0.8 GHz を用い，すべての組合せ (2.5 GHz, 2.5 GHz)，(0.8 GHz,. VCPU の周波数を決定する14) ．本研究は，電力制御機構によって周波数が決められた VCPU. 0.8 GHz)，(2.5 GHz, 0.8 GHz) における消費電力を測定した．ここで，4 コアのうち，利用. を適切にスケジューリングすることで，消費エネルギーを削減する．VCPU の周波数を決. しない 2 コアは最低周波数の 0.8 GHz に設定し，つねにアイドル状態とした．. める方法は本研究の対象外である．また，本研究は CPU の消費エネルギーを削減すること. 実験結果を図 1 に示す．X 軸は周波数の組合せ (f1 , f2 )，Y 軸は各場合における CPU. でエネルギー効率を上げることを目的としているため，CPU 使用率の高いワークロードを. の消費電力である．結果は，(2.5 GHz, 2.5 GHz) で 21.2 W，(0.8 GHz, 0.8 GHz) で 3.8 W，. 対象とする．具体的には，数値計算やインデックス計算のようなワークロードがあげられ. (2.5 GHz, 0.8 GHz) で 16.4 W であり，(2.5 GHz, 2.5 GHz) の場合を基準とした消費電力の. る4) ．そのため，CPU 使用率が低い I/O バウンドなワークロードは本研究の対象外とする．. 削減率は，(0.8 GHz, 0.8 GHz) で 77.4%，(2.5 GHz, 0.8 GHz) で 17.9%となった．ここで，. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). c 2011 Information Processing Society of Japan .

(3) 27. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. ここで，コアが {c1 , c2 , . . . , cc } の c 個あり，設定可能な周波数が {f1 , f2 , . . . , fn } の n 段階であるマルチコア CPU 上におけるスケジューリングを考える．このとき，すべてのコアの周波数が等しくなるのは，コア c2 , . . . , cc の周波数が，コア c1 と同じになる場合である．したがって，すべてのコアの周波数が揃う確率 p(c, n) は，. p(c, n) =. 1 nc−1. (1). で表される．たとえば，先の実験で用いた AMD Opteron の場合，コア数が 4，設定可能な周波数が. 4 種類であるため，p(4, 4) = 図 1 コア周波数の違いによる CPU の消費電力の変化 Fig. 1 Relation of CPU power consumption and core frequencies.. 1 64. となる．したがって，VCPU の周波数を考慮せずにスケ. ジューリングした場合，同じ周波数の VCPU が組になってスケジューリングされる確率は小さいといえる．また，式 (1) から，コア数が増えると，p(c, n) が指数関数的に小さくなることが分かる．CPU のコア数はこれからも増え続けていくといわれているため6) ，すべてのコ. コアごとに動作電圧が設定できる場合，つまりは，消費電力が最速のコアに依存せず，各コアの周波数のみで決まると仮定した理想ケースを考える．この場合，(2.5 GHz, 0.8 GHz) の消費電力は，(2.5 GHz, 2.5 GHz) と (0.8 GHz, 0.8 GHz) の平均値である 12.5 W になると期待できる．そしてこのとき，消費電力の削減率は 41.0%となる．これを，図 1 において，. (2.5 GHz, 0.8 GHz) の理想ケースとして示している．ところが，(2.5 GHz, 0.8 GHz) の実測値は，この理想値より 3.9 W 大きく，消費電力削減率の差に 23.1%という大きな差があ. アに同じ周波数の VCPU がスケジューリングされる確率はさらに小さくなると予想される．以上のことから，すべてのコアに低い周波数の VCPU をスケジューリングするためには，. VCPU の周波数を考慮したスケジューリングが必要であるといえる．. 3. 提案：Accele スケジューラ本研究では，マルチコア CPU の電力消費特性を考慮した VCPU スケジューラである. る．これより，マルチコア CPU の消費エネルギーは最速のコアの周波数に依存することが. Accele スケジューラを提案する．先の実験で示したとおり，マルチコア CPU の消費エネ. 確かめられた．. ルギーを大きく削減するためには，すべてのコアの周波数を揃えて下げる必要がある．そこ. 2.2 マルチコア CPU の特性を考慮した VCPU スケジューリングの必要性. で，すべてのコアに同じ周波数の VCPU をスケジューリングする時間を長くすることで，. 前節の実験より，マルチコア CPU の消費エネルギーは，最速のコアの周波数に依存する. DVFS による消費エネルギー削減効果を大きくする．また，すべてのコアの周波数を同じ. ことが分かった．このことから，マルチコア CPU において DVFS を行う場合，すべての. にすることができない場合は，できる限りコア間の周波数の差を小さくする．同時にスケ. コアの周波数を揃えて下げることで消費エネルギーを大きく下げることができると考えら. ジュールされている全 VCPU の最低周波数と最高周波数の差が小さいほど，最高周波数の. れる．ここで本研究では，クラウド環境における消費エネルギー削減を目的としているた. コアに消費エネルギーが依存してしまうことによる損失が小さいと考えられるためである．. め，VM 環境における消費エネルギー削減を考える．VM 環境では，VMM が持つ VCPU. さらに Accele スケジューラは，クラウド環境で一般に行われている work-conserving な. スケジューラが，物理 CPU に VCPU を割り当てることで，物理 CPU をシェアしている．. プロポーショナルシェアスケジューリングを行う．work-conserving なスケジューリングと. そこで，VCPU をスケジューリングする際，すべてのコアに同じ周波数の VCPU をスケ. は，CPU 利用率を高めるために，実行可能なジョブがある限り CPU をアイドルにしない. ジューリングすることで，消費エネルギーを大きく削減できると考えられる．ところが既存. スケジューリングである．クラウド環境では，多くの VM が物理 CPU を共有するため，で. の VCPU スケジューラは，VCPU の周波数を考慮せずにスケジューリングを行うため，す. きる限り CPU 利用率を高める必要があると考えられる．そこで，work-conserving なスケ. べてのコアに同じ周波数の VCPU がスケジューリングされる確率が小さい．. ジューリングを行う．またクラウド環境では，CPU 利用率に応じた課金を行うために，各. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). c 2011 Information Processing Society of Japan .

(4) 28. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. VM ごとに CPU の割当て量（シェア）をあらかじめ設定し，シェアに従うように VCPU をスケジュールすることが一般的であると考えられる．ここで Accele スケジューラは，VCPU の周波数が適切な値に設定されていることを前提とし，VCPU の周波数は変更しない．仮想化環境では，各ゲスト OS が電力制御を行うことで，VCPU の周波数を決定する14),19) ．本章では，3.1 節において，VCPU 周波数を考慮することで消費エネルギーを削減する. VCPU スケジューリング手法について述べる．まずは，プロポーショナルシェアリングを考慮せず，消費エネルギーを削減するために同じ周波数の VCPU を同時にスケジューリングする時間を長くする方法について議論する．そして，この方法を拡張し，消費エネルギーを削減しつつプロポーショナルシェアリングを行う手法を 3.2 節で述べる．. 3.1 VCPU 周波数を考慮したスケジューリング 3.1.1 VCPU の分配とランキューソートすべてのコアに同周波数の VCPU をスケジュールできる時間を長くするためには，各コアのランキューが持つ VCPU の周波数分布が近くなるようにする必要がある．各ランキューが同周波数の VCPU を同程度の数持つことで，それらを同時にスケジュールできる確率が高くなるためである．そこで Accele スケジューラは，VCPU をランキューに割り当てる際に VCPU の周波数を考慮し，各ランキューに割り当てる VCPU の周波数分布ができる限り等しくなるように VCPU を割り当てる．. /* すべての VCPU を周波数ごとに分類する */ for ( cpu_no = 0; cpu_no < CPU_NUM; cpu_no++){ /* ランキュー内の全 VCPU に関して操作を行う */ while ( !runq[cpu_no].isEmpty() ){ /* ランキューから周波数ごとに用意した配列へ VCPU を移す */ v = runq[cpu_no].remove(); same_freq_vcpus[v->freq_no].add(v); } } /* 同周波数の VCPU を各ランキューへ均等に分配する */ for ( freq_no = 1; freq_no < FREQ_NO_MAX; freq_no++ ){ /* 同周波数の全 VCPU に関して操作を行う */ while ( !same_freq_vcpu[freq_no].isEmpty() ){ /* 周波数ごとに用意した配列からランキューへ VCPU を移す */ v = same_freq_vcpu[freq_no].remove(); runq[cpu_no].add(v); /* 格納先ランキューを変更 */ cpu_no = (cpu_no+1) / CPU_NUM; } } 図 2 VCPU 分配のアルゴリズム Fig. 2 Algorithm of VCPU distribution.. このアルゴリズムを，図 2 に示す．まず，全 VCPU を周波数ごとに分類する．具体的には，周波数ごとにリストを用意し，各ランキュー内の VCPU を対応する周波数のリストに移す．その後，各周波数ごとに，対応するリスト内の VCPU を各ランキューへ均等に配分する．これにより，VCPU が各周波数ごとに均等にランキューへ分配されるため，各ランキューが持つ VCPU の周波数分布が近くなる．ここで一連の操作は，たかだか数十個の要素を線形リスト間で移動するという操作であり，処理に要する時間は小さいと考えられる．ここで，VM の起動・停止，VCPU のスリープなどによる VCPU 数の変化や，ゲスト. OS による VCPU の周波数の変更が起こると，ランキューが持つ VCPU の周波数分布が変わる．そのため，ランキューに対する VCPU の割当てを定期的に更新することが必要となる．そこで，一定周期エポックを定め，各エポックの開始時に VCPU の再分配を行う．. 図 3 ランキューソートの例 Fig. 3 Runqueue sort.. そして，各エポック内において，同周波数の VCPU を同時にスケジュールする時間を長くするために，各ランキューの VCPU を周波数の昇順にソートしてからスケジューリング. から順にスケジュールされるため，すべてのコアに同じ周波数の VCPU がスケジュールさ. を行う．各ランキューを周波数の昇順にソートすると，各コアにおいて周波数の低い VCPU. れる確率が高くなる．たとえば図 3 の場合，ランキューソートを行うことで，5 回のスケ. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). c 2011 Information Processing Society of Japan .

(5) 29. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. ジューリング中，3 回同じ周波数の VCPU がスケジューリングされている．また，周波数. は，アプリケーションの応答性や，コンテキストスイッチのオーバヘッドに影響を与える. が揃わない場合でも，周波数が近い VCPU が同時にスケジューリングされるようになる．. ため，VCPU 数に影響されて変動することは望ましくない．そこで，VCPU のタイムスラ. ここで，エポックの周期はある程度長い時間にしないと，エポック開始時に行う VCPU. イスの基準値 BS をパラメータとして設定し，全 VCPU のタイムスライスの平均がこの基. の再分配のオーバヘッドが大きくなってしまうと考えられる．コアをまたいで VCPU の再. 準値になるようにラウンド長を決める．具体的には，VCPU の個数 n，コア数 C の場合，. 分配を行うため，全コアで同期をとる必要があるためである．本実装では，エポックの周期. RL =. BS·n C. とする．本実装では，BS を 30 msec とした．. 3.1.3 優先スケジューリング. を 1 秒としている．. 3.1.2 ラウンド. スケジュールされている VCPU が，スリープや I/O 完了待ちの状態になると，コアの周波. 前項において，周期エポックごとに VCPU を再分配し，各ランキューをソートしてから. 数が揃う時間が短くなる場合がある．これは，Accele スケジューラは work-conserving なス. VCPU をスケジュールすることで，同じ周波数の VCPU を同時にスケジュールする時間. ケジューリングを行い，スリープした VCPU の代わりにランキューの先頭にある VCPU を. を長くする手法を述べた．ところが，ランキューをソートして全 VCPU をスケジュールす. スケジュールするためである．このとき，CPU を明け渡した VCPU と代わりにスケジュー. るという一連の流れをエポックという長い周期（例：1 秒）で行うと，VCPU の周波数変. ルされる VCPU の周波数が異なると，すべてのコアの周波数が揃わなくなってしまう場合. 更などの状態変化への対処が遅くなってしまうと考えられる．たとえば，図 3 の例の場合. がある．この例を図 4 (a) に示す．2 コアの CPU のそれぞれのランキューが，1.0 GHz と. に，最初の VCPU をスケジューリングしてから 10 msec で，コア 2 の 1.0 GHz の VCPU. 3.0 GHz の VCPU を 1 つずつ持っており，コア 1 で実行中の 1.0 GHz の VCPU がスリー. が，3.0 GHz に変更されたとする．エポックが 1 秒の場合，各 VCPU のタイムスライスが. プしたとする．これにより，3.0 GHz の VCPU が代わりにスケジュールされた結果，両方. 200 msec となるため，タイムスライスを使いきるまでの 190 msec という長い時間，1.0 GHz. のコアが 1.0 GHz になる時間が短くなっている．. と 3.0 GHz の VCPU を同時にスケジュールしてしまうことになり，消費エネルギーの削減. このように VCPU がスリープ状態に入ることによってコアの周波数が揃わなくなってしまう時間を減らすため，CPU を明け渡してスリープ状態になった VCPU が起床したとき，. 効率が悪くなってしまう．そこで，エポックを複数のラウンドという周期に分割し，各ラウンドごとにランキューを. 実行中の VCPU をプリエンプトして優先的にスケジュールする．これにより，VCPU のス. ソートして VCPU をスケジュールする．これにより，ランキューをソートして全 VCPU を. ケジューリング順序が，ラウンド開始時にランキューをソートした順序に近くなるため，す. スケジューリングするという流れを比較的短い周期で行うため，VCPU の状態変化に早く. べてのコアの周波数が揃う確率が高くなる．この様子を図 4 (b) に示す．1.0 GHz の VCPU. 対応し，その影響を緩和することができる．ここで，先の例と同じく，図 3 の状況下で，ス. がスリープすることで，いったんは全 VCPU の周波数が 1.0 GHz に揃わなくなっている. ケジューリング開始 10 msec 後に，コア 2 の 1.0 GHz の VCPU が，3.0 GHz に変更された場合を考える．ラウンドの長さが 100 msec であるとすると，各 VCPU のタイムスライスは 20 msec となるため，1.0 GHz と 3.0 GHz を揃えてスケジュールする時間は 10 msec という短い時間となる．そして，次のラウンドの開始時には，ランキューをソートし直すため，周波数が近い VCPU が同時にスケジューリングされるようになる．ラウンドの長さは，各エポックの開始時に，システムが保持している VCPU 数を考慮して動的に決める．ラウンド長を固定値にしてしまうと，ランキューが保持する VCPU 数によって，VCPU のタイムスライスの大きさが大きく変わってしまうためである．たとえば，ラウンド長を 100 msec に固定すると，ランキュー内に VCPU が 4 個ある場合はタイムスライスの平均が 25 msec，20 個ある場合は平均 5 msec となる．タイムスライスの大きさ. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). (a) 優先スケジューリングなし. (b) 優先スケジューリングあり. 図 4 優先スケジューリング Fig. 4 Priority boosting for VCPUs yielding their core.. c 2011 Information Processing Society of Japan .

(6) 30. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. ものの，実行可能になった 1.0 GHz の VCPU をすぐにスケジューリングすることで，もう 1 度 1.0 GHz の VCPU が揃ってスケジューリングされている．その結果，同じ周波数の. VCPU がスケジューリングされている時間が長くなっている．ただし，起床した VCPU を必ず優先的にスケジュールしてしまうと，周波数が高い VCPU が周波数が低い VCPU をプリエンプトしてしまい，周波数が低い順にスケジュールしている状況を壊してしまう場合がある．これは，同じコア上の VCPU が複数個スリープした. (a) 全ランキューを走査して最適化. 場合に起こりうる．たとえば，1.0 GHz と 3.0 GHz の 2 つの VCPU がスリープしたときに，先に 1.0 GHz の VCPU が起床し，後から 3.0 GHz の VCPU が起床すると，3.0 GHz. Fig. 5. (b) アイドルを入れる. 図 5 周波数が揃う時間を長くするスケジューリングの例 Other ways to schedule same-frequency VCPUs simultaneously.. に VCPU が，先に起床して実行されていた 1.0 GHz の VCPU をプリエンプトしてしまう．そこで，起床した VCPU を優先的にスケジュールするのは，起床した VCPU の周波数が，実行中の VCPU の周波数より低い場合のみとする．こうすることで，高い周波数の VCPU が低い周波数の VCPU をプリエンプトし，周波数が揃っている状況を壊すことを防ぐ．. 3.1.4 議. 論. として導入しているため，コア間で同期をとる必要がある方法は適さない．また，図 5 (b) のように，周波数が揃わない箇所で CPU をアイドルにすることによってコアの周波数が揃う確率を高くすることも考えられる．この例では，4 回のスケジューリングで周波数が揃っており，本手法を用いた場合より周波数が揃う回数が多い．しかし Accele. これまでに述べた VCPU の分配とランキューのソートを行っても，つねに同じ周波数の. スケジューラは，CPU 利用率を高めるために work-conserving なスケジューリングを行う. VCPU を同時にスケジュールできるとは限らない．本項では，同じ周波数が揃わないケー. ため，スケジューリング可能な VCPU がある状況では，CPU をアイドルにしない．その. スにおいても Accele スケジューラによるスケジューリングが有効であるかを，他の考えう. ため，実行可能な VCPU がある状況で CPU をアイドルにするこの方法は適さない．. るスケジューリング方法と比較して議論する．. これらの方法に対し，本手法で導入しているラウンドごとのランキューソートは，コア間. 同じ周波数の VCPU を同時にスケジュールできないケースとして，ある周波数の VCPU. の同期を行わずに，同周波数の VCPU が同時にスケジューリングされる時間を長くできる．. を，すべてのコアに均等に分散させることができない場合があげられる．これは，ある周. また，同周波数の VCPU をスケジュールできない場合は，近い周波数の VCPU が同時に. 波数の VCPU の数がコア数の倍数でない場合に起こる．先にあげた図 3 の例はこれに該当. スケジュールされるため，コアの周波数を異なる値に設定してしまうことによる損失を最小. し，1.0 GHz の VCPU と 3.0 GHz の VCPU は均等に割り振ることができない．結果とし. 限に抑えることができる．. て，5 回のスケジューリング中 2 回は異なる周波数の VCPU がスケジュールされている．しかし本手法では，ランキューをソートすることによって，周波数が揃わない場合でもコア間の周波数の差が小さくなるため，効率良く消費エネルギーが削減できると考えられる．ここで比較のため，その他に考えうるスケジューリング方法について検討する．まず，できる限り同じ周波数の VCPU のペアを作ってから，最後に余った VCPU をスケジューリングするという手法が考えられる．その結果，図 5 (a) のようになる．この場合，4 回のスケ. 3.2 プロポーショナルシェアスケジューラへの拡張前節では，プロポーショナルシェアリングを考慮しない状況において，消費エネルギーを小さくするスケジューリング手法について述べた．本節では，前節で述べたスケジューリング手法を拡張し，プロポーショナルシェアリングを行いつつ，消費エネルギーを小さくする手法について述べる．まず，プロポーショナルシェアリングを行うためには，各 VCPU に与えられたシェアに. ジューリングで周波数が揃っており，本手法を用いた場合よりも周波数が揃う回数が多い．. 従って，VCPU へタイムスライスを割り与える必要がある．そこでラウンドの開始時におい. しかしこの方法は，すべてのランキューの中身を見て組合せを決定してからスケジューリン. て，各ランキューごとに，ラウンド長を VCPU のシェアに従った比率で分割し，各 VCPU. グを始める必要があるので，ラウンドの開始時にすべてのコアで同期をとる必要がある．周. にタイムスライスとして割り与える．これにより，各ランキューごとにプロポーショナル. 期ラウンドは，コア間で同期をとらない状況でできる限りコアの周波数を揃えることを目的. シェアスケジューリングを行う．ランキュー k 上の VCPU vi に対して割り与えるタイムス. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). c 2011 Information Processing Society of Japan .

(7) 31. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. ライス ti は，ラウンド長 r，vi のシェアの値 si ，ランキュー k 上の VCPU のシェアの合計 STk を用いた式 ti =. r·si STk. 差が細かい粒度で近くなるように VCPU が割り当てられていく．以上の方法により，各ランキューが持つ VCPU の周波数分布と，保持する VCPU のシェアの合計の両方が近くな. で定める．. ここで，各ランキューにおけるプロポーショナルシェアスケジューリングを行うことに. るようにする．. よって，システム全体でプロポーショナルシェアリングを実現するためには，各ランキュー. ところが，上記の方法を用いても，VCPU のシェアの合計をすべてのランキューで等し. 内のタイムスライスの割当てと，全 VCPU のシェアの比率から求まるタイムスライスが等. くできるとは限らない．さらに，VCPU がスリープする場合などに，VCPU に与えたタイ. しくなる必要がある．そしてこの条件は，各ランキューが持つ VCPU のシェアの合計をす. ムスライスと，その VCPU が実際に動作した時間が異なる場合がある．そこで，これらの. べて等しくすることで満たすことができる．その理由を以下に示す．まず，各ランキューご. 問題に対処するため，エポックの開始時に，各 VCPU が実際に動作した時間と，全 VCPU. とにタイムスライスを割り与えた場合の全 VCPU のタイムスライスの比は，vi が属してい. のシェアの比から計算したタイムスライスとのずれを検査し，そのずれを修正するように. るランキューの番号を R(i) として，. 次のエポックにおける各 VCPU のシェアの値を変更する．このようにシェアの値を調整す. r · s1 r · s2 r · sn : : ··· : STR(1) STR(2) STR(n). (2). ることによってタイムスライスの長さが変わるため，実際の動作時間とタイムスライスのずれを調整するように，次のエポックにおけるタイムスライスが調整される．具体的には，. と表せる．そして，システム全体でプロポーショナルシェアリングを行う場合に与えるタイ. エポック n で全 CPU のシェアを考慮して vi に与えられるタイムスライス ETn,i と，vi が. ムスライスの比は，. エポック n で実際に動作した時間 RTn,i との比率から，エポック n + 1 における vi のシェ. s1 : s2 : · · · : sn. (3). となる．したがって，式 (2) と (3) が一致したとき，ランキューごとにプロポーショナル. ア sn+1,i を，sn+1,i = sn,i ·. ETi RTi. とする．この式から，vi が ETi より長い時間動作してい. た場合，次のエポックにおけるシェアが小さくなるため，与えられるタイムスライスが短く. シェアスケジューリングを行うことで，システム全体でプロポーショナルシェアを実現でき. なる．逆に，実際の動作時間が ETi より短かった場合，次のエポックにおけるシェアが大. る．この条件は. きくなるため，与えられるタイムスライスが長くなる．. . k=R(1). STk =. k=R(2). STk = · · · =. . STk. (4). k=R(n). となったときに満たすことができる．そして条件式 (4) は，STk をすべて等しくすること. 4. 実. 装. Accele スケジューラを，オープンソースの VMM である Xen 3.4.1 に実装した．Xen は，. で，すなわち，すべてのランキューのシェアの合計を等しくすることで満たすことができる．. Credit スケジューラや SEDF スケジューラなど，複数のスケジューリングポリシを持って. そこで Accele スケジューラは，エポックの開始時における VCPU の分配を行う際に，. おり，起動時にこれらを選択することができる．そこで，Xen のスケジューリングポリシ. VCPU の周波数分布が近くなるように分配するのに加え，各ランキューが持つ VCPU の. の 1 つとして，Accele スケジューラを実装した．スケジューラのソースコードは，C 言語. シェアの合計ができる限り等しくなるように VCPU を分配する．具体的にはまず，周波数. で 1,827 行である．. に関して全 VCPU を周波数ごとにクラスタリングする．さらに，シェアの大きさを考慮し. ここで，スケジューリングする VCPU の周波数に応じて物理 CPU の周波数を変更する. て VCPU を分配するために，各クラスタ内の VCPU をシェアの値の降順にソートする．そ. 手法は，VirtualPower などの既存研究で提案されているものの，既存の Xen には実装され. して，各クラスタごとに，保持している VCPU を，シェアの大きいものから順にランキュー. ていない．そこで，Xen にこの手法を実装した．具体的には，VCPU のデータ構造に周波. へ割り当てていく．その際，割り当てるランキューは，その時点でシェアの合計が最小のラ. 数を表す属性を追加し，ハイパーコールを通じて変更可能とした．そして，VCPU をスケ. ンキューとする．このように，シェアが大きい VCPU から順に割り当てていくことで，最. ジュールする schedule() 関数において，スケジュールする VCPU の周波数に従って，物. 初は粗い粒度で全ランキューのシェアの合計が近くなるように VCPU が割り当てられる．. 理 CPU の周波数を変更するようにした．. そして，割り当てる VCPU のシェアが小さくなるにつれ，ランキュー間のシェアの合計の. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). 本実装では，各 VCPU のタイムスライスの基準値 BS を 30 msec とした．エポックの長. c 2011 Information Processing Society of Japan .

(8) 32. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. さは，1 秒以上の値でラウンド長の倍数となる最小値とした．ラウンドの長さによってエ. 50 msec，100 msec の 3 通りに設定することでスリープ頻度を変化させ，同周波数の VCPU. ポックの長さを変えるのは，ラウンドの途中でエポックが終了してしまうと，割り当てられ. を同時にスケジュールすることが難しい度合いを変化させた．まず，VCPU がスケジュー. たタイムスライスを使いきれない VCPU が多くなってしまうと考えられるためである．. ルされるたびに 1 回スリープする場合として，スリープ時間に 10 msec，スリープ間隔に. 5. 実. 10 msec というパラメータを用いる．4 章より，本実装では各 VCPU のタイムスライスの基. 験. 準値が 30 msec であるため，ある VCPU をスリープ時間 10 msec，スリープ間隔 10 msec. Accele スケジューラが，消費エネルギーを削減しつつ，プロポーショナルシェアリング. でスリープさせることで，スケジュールされるたびに 1 回スリープする．そして，この場合. を行っていることを示すために実験を行った．既存の VCPU スケジューラとの比較を行う. よりスリープ頻度が低い場合のスリープ間隔として，50 msec，100 msec を用いる．VCPU. ために，Xen のデフォルトスケジューラである Credit スケジューラを用いた．. Credit スケジューラは，VCPU の周波数を考慮したスケジューリングを行わない．第 1 に，ランキューに対して VCPU を割り当てる際に，VCPU の周波数を考慮しない．VM 作成時，各コアに 1 つずつ VCPU を割り当てる．そして，VCPU の割当てを変更する場合も，. は，2.5 GHz のものを 4 つ，0.8 GHz のものを 4 つの合計 8 つを動作させ，それぞれの上で無限ループを実行した．そして，0.8 GHz の VCPU 上で動作する無限ループの 1 つを先に述べた設定で定期的にスリープさせた．ここで，物理 CPU のコア数は 4 とした．結果を図 6 に示す．X 軸はスリープの周期，Y 軸は Accele スケジューラで測定した消. VCPU の周波数を考慮しない．あるランキューが空になったとき，work-conserving なス. 費エネルギーと Credit スケジューラで測定した消費エネルギーの比である．結果より，ス. ケジューリングを行うために，別のランキューの先頭にある VCPU を取り出して空のラン. リープの周期が 50 msec と 100 msec の場合における消費エネルギーはそれぞれ，Credit. キューへ割り当てる．第 2 に，VCPU をスケジュールする順序を決める際に，VCPU 周波. スケジューラの 87.1%，87.6%であり，消費エネルギーを大きく削減できていることが分. 数を考慮した順序付けを行わない．VCPU は，ランキューに割り当てられる際にランキュー. かった．. の最後尾に入り，先頭の VCPU から順にスケジュールされる．. しかし，10 msec の周期でスリープする場合は，Accele スケジューラの消費エネルギー. 5.1 実験環境. は Credit スケジューラの 98.3%であり，差が小さかった．この原因を調べるため，Accele. CPU は予備実験で使用したものと同じ AMD Opteron Quad-Core 2384 を用いた．こ. スケジューラにおいて，スリープ周期が 10 msec と 50 msec の場合の実験について，コア. の CPU は，各コアの周波数を 2.5 GHz，1.8 GHz，1.3 GHz，0.8 GHz に設定できる．メモ. 周波数の組合せの内訳を記録した．この結果を図 7 に示す．X 軸はコアの周波数の組合せ，. リは 16 GB DDR2 SDRAM を使用した．CPU の消費エネルギーの測定にはシネジェテック社の電力測定器を用い，測定周期は 1 msec とした．各 VM 上で動作する OS は，Linux. 2.6.18.8 を用いた．そして，各 VM に割り与えるメモリ容量は，VCPU 数が 2 の場合は 2 GB，VCPU 数が 4 の場合は 3 GB とした． 5.2 マイクロベンチマーク 5.2.1 周波数を揃えにくい状況下における消費エネルギーの変化 Accele スケジューラは，同周波数の VCPU を揃えてスケジューリングしにくい状況になるほど，消費エネルギーの削減効率が悪くなる．そこで，同じ周波数の VCPU を揃えてスケジュールすることが難しい状況を作り，消費エネルギーにどの程度影響があるかを調べる実験を行った．本実験では，同じ周波数の VCPU を揃えてスケジュールすることが難しい状況として，複数の VCPU が動作している状況で，ある VCPU が一定周期でスリープする場合を考える．具体的には，スリープ時間を 10 msec に固定し，スリープ間隔を 10 msec，. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). 図 6 周波数を揃えにくい状況下における消費エネルギー Fig. 6 Power consumption when a VCPU sleeps periodically.. c 2011 Information Processing Society of Japan .

(9) 33. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. (a) 10 msec. (b) 50 msec. 図 7 Accele スケジューラにおけるコア周波数の組合せ Fig. 7 Time fraction of each combination of core frequencies.. 図 8 シェア調整の効果 Fig. 8 Effect of adjusting CPU share.. ラ，3) Credit スケジューラの 3 通りのスケジューラを使って行い，結果を比較した．実験. Y 軸は各組合せで動作した時間が実行時間全体に占める割合を表している．結果より，すべてのコアが 0.8 GHz になっている時間が，スリープ周期 10 msec の場合で全体の 3.9%，. に使うコアの数は 4 とした．VM のメモリサイズはすべての場合で 3 GB とした．実験結果を図 8 に示す．各結果に対し，全 VCPU の動作時間の平均値をプロットし，動. 50 msec の場合で全体の 34.0%となっており，大きな差が見られた．したがって，スリープ. 作時間が最大の VCPU の動作時間と，動作時間が最小の VCPU の動作時間を直線で結ん. が 10 msec の場合，すべてを 0.8 GHz に揃えられる時間が短いために，消費エネルギーの. でいる．図の X 軸は VCPU 数，Y 軸は各 VCPU 数の場合における Credit スケジューラ. 削減が小さくなったと考えられる．ここで，スリープ 10 msec の場合に，0.8 GHz が 3 つ，. の平均値を 1 とした相対値である．. 2.5 GHz が 1 つとなる組合せが全体の 38.2%という長い時間起きている．これは，0.8 GHz. 結果より，シェアの調整を行う Accele スケジューラと Credit スケジューラの場合は，す. の VCPU のうち，スリープしない 3 つは揃えてスケジュールできているものの，1 つの. べての VCPU 数において，VCPU の動作時間の差が小さいことが分かる．シェアの調整を. VCPU が頻繁にスリープするために，すべてのコアに 0.8 GHz の VCPU をスケジュール. 行う Accele スケジューラの場合は動作時間の最大値と最小値の差が最大 3.2%，Credit ス. できていない状況を表している．しかしながら，このようにすべてのコアの周波数を揃える. ケジューラの場合は最大 1.9%である．このことからシェアの調整を行う Accele スケジュー. ことが難しい状況においても，Credit スケジューラよりも消費エネルギーが大きくなるこ. ラは，既存のプロポーショナルシェアスケジューラである Credir スケジューラと同程度の. とはなかった．. 精度でプロポーショナルシェアリングを実現できていることが分かった．. したがって Accele スケジューラは，すべてのコアの周波数を揃えることが難しい場合でも，Credit スケジューラと同等かそれ以上に消費エネルギーを削減できることが分かった．. 一方，シェアの調整を行わない Accele スケジューラでは，VCPU の動作時間の最大値と最小値の差が大きくなった．VCPU の動作時間の最大値と最小値の差は最大で 43.9%であ. 5.2.2 シェア調整の効果. る．これは，VCPU 数がコア数の倍数になっていないため，ランキューのシェアの合計を等. Accele スケジューラが，3.2 節で述べたシェアの調整によってプロポーショナルシェア. しくすることができず，各コアごとのスケジューリングでは全 VCPU のシェアに従ったタ. リングを行っていることを示すため，実験を行った．全 VCPU に同じシェアを与え，60. イムスライスの割当てができないことが原因であると考えられる．このような状況下では，. 秒間それぞれの上で無限ループを動かし，各 VCPU が動作した時間を測定した．実験は，. 3.2 節で示したシェアの調整を行わないと，プロポーショナルシェアリングが実現できない．. 1) シェアの調整を行う Accele スケジューラ，2) シェアの調整を行わない Accele スケジュー. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). 以上の結果から，Accele スケジューラは，エポック開始時にシェアの調整を行うことで，. c 2011 Information Processing Society of Japan .

(10) 34. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. 5.3 マクロベンチマーク. プロポーショナルシェアリングが行えていることが示された．. 5.2.3 優先スケジューリングの効果. Accele スケジューラが，実アプリケーションを動作させた際に CPU の消費エネルギーを. VCPU がスリープする場合に，その VCPU が起床したときに優先的にスケジューリング. 小さくできることを示すために実験を行った．Accele スケジューラと Credit スケジューラ. することで，同じ周波数の VCPU を同時にスケジュールする時間が長くなることを示すた. において，複数の VCPU 上でワークロードを動作させ，CPU の消費エネルギーとワーク. めに実験を行った．0.8 GHz と 2.5 GHz の VCPU を 4 つずつ動作させ，すべての VCPU. ロードの実行時間を測定し，結果を比較した．また，エネルギー効率を表す値である Energy. 上で無限ループを実行した．そして，0.8 GHz の VCPU 上で動作する無限ループの 1 つで，. Delay Product（EDP）を算出し，エネルギー効率の比較も行った．EDP はスループット. 500 msec ごとに 10 msec のスリープを入れた．この状況において，優先スケジューリング. あたりの消費エネルギーを表す指標であり，EDP が小さいほどエネルギー効率が高い．. を行う場合と行わない場合で 60 秒間測定を行い，物理コアの周波数の組合せがどのように. 5.3.1 ワークロード. なったかを記録した．実験に使うコアの数は 4 とした．. ワークロードは，SysBench と SPEC CPU2006 を用いた．SysBench は，CPU バウン. 結果を図 9 に示す．X 軸はコアの周波数の組合せ，Y 軸は各組合せで動作した時間が実. ド，メモリバウンド，I/O バウンドなど，様々なワークロードを含んでいる．今回は，CPU. 行時間全体に占める割合を表している．図 9 (a) より，優先スケジューリングを行うと，すべ. バウンドなワークロード（SysBench-CPU）とメモリバウンドなワークロード（SysBench-. てのコアが 0.8 GHz になるのが実行時間全体の 42.5%，すべてのコアが 2.5 GHz になるの. Mem）を用いて実験を行った．SPEC CPU2006 からは，hmmer，milc，sjeng，xalancbmk，. が実行時間全体の 42.7%となった．それに対し，優先スケジューリングを行わない図 9 (b). soplex，zeusmp，h264ref，omnetpp，gcc を用いた．. の場合，すべてのコアが 0.8 GHz になるのが全体の 21.9%，すべてのコアが 2.5 GHz にな. ここで，Accele スケジューラは，各 VCPU の周波数が適切な値に設定されていること. るのが全体の 24.1%となった．したがって，優先スケジューリングを行うことで，全コアが. を前提としている．そこで予備実験を行い，ワークロードごとに最適な周波数を決定した．. 0.8 GHz になる時間が 20.6%，全コアが 2.5 GHz になる時間が 18.6%増加した．このこと. 各ワークロードを，実験で用いる CPU で設定可能なすべての周波数で動作させ，EDP が. から，優先スケジューリングを行うことで，すべてのコアの周波数が同じになる時間が長く. 最小となる周波数を，そのワークロードにおける最適な周波数とする．予備実験の結果は. なることが分かった．. 図 10 に示すとおりとなり，この結果から，各ワークロードを動作させる際の VCPU 周波数を表 1 のように定めた．実験は，表 2 に示す 5 通りのワークロードの組合せで行った．シナリオ 1 は SysBench を用いた．シナリオ 2 から 5 では SPEC CPU2006 のワークロードを用い，最適な周波数が 2.5 GHz のもの，1.3 GHz のもの，0.8 GHz のものを様々に組み合わせて実験を行った．. 5.3.2 実験結果実験結果を図 11 に示す．X 軸はシナリオ番号，Y 軸は各シナリオに関して，消費エネルギー，処理時間，EDP の値を表している．また各値は，Credit スケジューラの場合を 1 とした相対値である．グラフより，コア数 2，4 双方において，すべてのシナリオで Accele スケジューラの消費エネルギーが，Credit スケジューラの場合より小さくなっていることが分かる．消費エネルギーの減少は最大で 22.8%，最小で 12.1%となった．このことから， (a) 優先スケジューリングあり. (b) 優先スケジューリングなし. 一方で，ワークロードの実行時間に関しては，Accele スケジューラの方が最大で 8.3%長. 図 9 優先スケジューリングの効果 Fig. 9 Effect of the priority boost.. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. Accele スケジューラが消費エネルギーを大きく削減できていることが分かる．くなった．この原因として，共有キャッシュやメモリバスといった共有リソースの競合，本ス. 25–39 (Mar. 2011). c 2011 Information Processing Society of Japan .

(11) 35. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. (a) コア数 2 Fig. 11 Fig. 10. 図 10 各ワークロードの CPU 周波数に対する EDP の値 Relation of EDP and the core frequency at which each workload runs.. (b) コア数 4. 図 11 各シナリオにおける消費エネルギー，処理時間，EDP の比較 Comparison of energy consumption, execution time and EDP in each scenario.. ドを同時に動作させる時間が長くなる．したがって，共有リソースの競合がパフォーマンス低下の要因の 1 つとして考えられる．また，定期的にランキューの再構成を行うため，この. 表 1 各ワークロードの最適な周波数 Table 1 Best frequency for each workload.. 操作によるオーバヘッドも要因の 1 つと考えられる．ここで，消費エネルギーと処理時間の双方を考慮して得られる値である EDP を比較する. 周波数（GHz）. ワークロード. 2.5 1.3 0.8. h264ref，hmmer，sjeng，SysBench-CPU zeusmp，xalancbmk，gcc soplex，milc，omnetpp，Sys-Mem. と，すべてのシナリオにおいて，Accele スケジューラの方が小さくなっている．したがって，処理時間の増加より消費エネルギーの減少の効果の方が大きく，結果として Accele スケジューラを使うと CPU のエネルギー効率が上がることが分かった．このことから Accele スケジューラは，消費エネルギーを減少させ，さらにエネルギー効率も高められるといえる．. 表 2 実験で用いたワークロードの組合せ Table 2 Combination of workloads.. シナリオ. 1 2 3 4 5. VM1 SysBench-CPU（2.5 GHz） hmmer（2.5 GHz） sjeng（2.5 GHz） zeusmp（1.3 GHz） h264ref（2.5 GHz）. ワークロード VM2. Sys-Mem（0.8 GHz） milc（0.8 GHz） xalancbmk（1.3 GHz） soplex（0.8 GHz） gcc（1.3 GHz）. さらに，コア数が 2 つの場合と 4 つの場合を比較すると，次のことが分かる．まず，消費エネルギーに関しては，コア数 4 の場合の方が，Credit スケジューラと比較して小さい VM3 omnetpp（0.8 GHz）. 値となっている．これは，2.2 節で述べたとおり，コア数が多くなると，偶然にすべてのコアの周波数が揃う確率が小さくなるためと考えられる．逆に，処理時間を比較すると，コア数 4 の場合の方が，Credit スケジューラに対する処理時間が大きくなっている．これは，コア数が多い方が，同時にスケジューリングされるメモリバウンドなワークロードの数が多くなるため，メモリアクセスの競合が大きくなるためと考えられる．マルチコア CPU のコア数はさらに増加していくといわれているため，今後は，メモリバスの競合とマルチコア. ケジューラのオーバヘッドなどが考えられる．Accele スケジューラは，同周波数の VCPU を同時にスケジュールするため，Credit スケジューラと比べ，メモリバウンドワークロー. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). CPU の電力消費特性の双方を考慮するスケジューラが必要であると考えられる．ここで，Accele スケジューラが同じ周波数のコアを同時にスケジューリングしているこ. c 2011 Information Processing Society of Japan .

(12) 36. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. くできていることが分かる．ここで，Credit スケジューラの場合，コア数が 2 の場合より. 4 の場合の方が，すべてのコアの周波数が揃う確率が小さくなっている．これは，2.2 節で述べたとおり，VCPU の周波数を考慮せずにスケジューリングすると，コア数が増えるに従って，すべてのコアの周波数が揃う確率が小さくなることを示している．その他のシナリオにおいてもスケジューリングのログを調べた結果，すべてのシナリオにおいて，Accele スケジューラは高い確率ですべてのコアの速度を揃えてスケジューリングを行っていることが確かめられた． (a) Accele（2 コア）. (b) Credit（2 コア）. 6. 関連研究データセンタにおける消費エネルギーを削減するために，VM 環境における電力制御手法が研究されている．Nathuji ら14) は，VM 環境において，VM と VMM が協調して電力制御を行うためのフレームワークである VirtualPower を提案している．各ゲスト OS が. VCPU に対して発行する DVFS 関連の命令を VMM がフックすることで，VM が行う電力制御を考慮しながら VMM による電力制御を行う．また，Stoess ら19) や Kansal ら10) は，. VM 環境において，システム全体の消費エネルギーを，各 VM にアカウンティングする手法を提案している．各 VM に対して正確に消費エネルギーをアカウンティングすることで，各 VM が定めたエネルギー内で動作するように動作制限を行う．pMapper 21) は，VM の (c) Accele（4 コア）. (d) Credit（4 コア）. 図 12 シナリオ 1 における各コア周波数の組合せの動作時間 Fig. 12 Time fraction of the combination of core frequencies in Scenario 1.. 移送を利用し，エネルギー効率の良いマシンに VM を集約することで消費エネルギーを削減する．Accele スケジューラは，このような VM 環境における電力制御機構と補完的に動作することで，さらに消費エネルギーを削減する．. Weiser らが実システムのトレースを用いて DVFS の有用性を示して以来25) ，DVFS をとを示すため，シナリオ 1 の実験における VCPU スケジューリングのログを記録した．結. 用いた CPU の電力削減手法が数多く研究されてきた．Hsu ら8) は，プログラムをコンパイ. 果を図 12 に示す．X 軸は各コアの VCPU の周波数の組合せ，Y 軸は各組合せがワーク. ルする際にコードを解析し，適切な箇所に DVFS を利用するコードを自動挿入するコンパ. ロードの実行時間全体に占める割合を表す．結果のグラフから，Accele スケジューラでは，. イラを提案している．Koala 18) は，DVFS がパフォーマンスと消費エネルギーに与える変. コア数 2，4 の場合ともに同じ周波数の VCPU がスケジューリングされている時間が長い. 化を正確に予測するために，CPU だけでなく，メモリとメモリバスを考慮に入れたモデル. ことが分かる．コア数 2 の場合，すべての VCPU が 2.5 GHz で揃っている場合が実行時間. を作成し，電力制御を行う．Chameleon 12) は，アプリケーション主導で電力制御を行うシ. 全体の 44.4%，0.8 GHz で揃っている時間が 49.6%となっており，動作時間の 94.0%という. ステムである．アプリケーションは，電力制御に必要なメトリクスを OS から取得し，OS. 高い割合で 2 つのコアの周波数が揃っている．一方，Credit スケジューラの場合，2 つの. が提供するインタフェースを介して電力制御を行う．これらの手法は，仮想化環境におい. コアの周波数が揃っているのは全体の 27.3%という低い割合となっている．コア数 4 の場. て，ゲスト OS が電力制御に用いる手法であり，Accele スケジューラはこれらが決定した. 合も同様に，Accele スケジューラの場合は高い割合ですべてのコアの周波数が揃っている．. VCPU 速度をもとに VCPU スケジューリングを行う．. これにより，Accele スケジューラが同周波数の VCPU を同時にスケジュールする時間を長. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). これまで VCPU スケジューリングの研究は，主にシステムのパフォーマンスの向上を目. c 2011 Information Processing Society of Japan .

(13) 37. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. 的として行われてきた．Time balloning 20) は，マルチプロセッサ上で動作する VM 環境において，ゲスト OS のプロセススケジューラが正しくロードバランスを行えるようにす. 7. おわりに. る．Govindan ら5) は，VM 間の通信遅延を小さくするための VCPU スケジューリング手. 本論文では，VM 環境において，マルチコア CPU の電力消費特性を考慮した VCPU スケ. 法を提案している．Lee ら11) は，VM 環境において，ソフトリアルタイムアプリケーショ. ジューラである Accele スケジューラを提案した．マルチコア CPU には，すべてのコアの周. ンのレイテンシを小さくする手法を提案している．しかし今まで，消費エネルギー削減のた. 波数を下げないと，DVFS による消費エネルギーの削減が小さいという特性がある．Accele. めの VCPU スケジューリング手法は提案されていない．. スケジューラはこの特性を考慮し，すべてのコアの周波数が下がる確率が高くなるように. 既存の VMM が持つ VCPU スケジューラにおいても，VCPU の周波数を考慮したスケ. VCPU をスケジューリングする．具体的には，各ランキューにおいて，一定周期で VCPU. ジューリングは行われていない．KVM は，VCPU スケジューラとして Linux のプロセス. を周波数順にソートしてからスケジューリングを行う．SysBench と SPEC CPU2006 に含. スケジューラを用い，各 VCPU をプロセスとして扱うことで VCPU スケジューリングを. まれる CPU バウンドワークロードとメモリバウンドワークロードを用いた実験の結果か. 行う17) ．既存の Linux のプロセススケジューラでは，各プロセスをスケジュールする際に. ら，Accele スケジューラが大きく消費エネルギーを削減できることが示された．. CPU 周波数は考慮していないため，同周波数の VCPU が同時にスケジュールされる確率. ただし同時に，メモリアクセスの競合によってワークロードのパフォーマンスが低下する. は低いと考えられる．VMware の VCPU スケジューラは，プロポーショナルスケジューリ. ことが分かった．したがって今後，マルチコア CPU の電力消費特性とメモリアクセスの競. ングを行う VCPU スケジューラである23),24) ．商用の VMM であるため，スケジューリン. 合の双方を考慮するスケジューリング手法が必要であると考えられる．. グアルゴリズムの詳細は公開されていない．しかし，筆者らが調査した限りでは，VCPU の周波数を考慮した VCPU スケジューラは本スケジューラが初めてである．したがって，. VMware の VCPU スケジューラにおいても，同周波数の VCPU がスケジュールされる確率は低いと考えられる．. Merkel らは，マルチコア CPU におけるメモリバスの競合を避けるようにアプリケーションをスケジューリングすることで，CPU のエネルギー効率が高くなることを示している13) ．マルチコア CPU において，メモリバウンドなワークロードを同時にスケジューリングすると，メモリバスの競合によるパフォーマンスの低下が起き，DVFS を利用してもエネルギー効率が悪くなることがある．しかし，本研究の実験結果では，メモリバウンドなワークロードを同時に動かすことによるパフォーマンス低下より，DVFS による消費エネルギー削減の効果の方が大きく，エネルギー効率が高くなった．これは，DVFS による消費エネルギーの削減が CPU によって異なるためと考えられる．Merkel らが実験に用いた CPU は最低周波数が 1.6 GHz であり，本研究で用いた CPU の最低周波数 0.8 GHz よりも大きいため，DVFS による消費エネルギーの削減が小さい．本研究と Merkel らの研究は補完関係にあり，今後，メモリバスの競合とマルチコア CPU の電力消費特性の双方を考慮するスケジューラが必要であると考える．. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). 参. 考. 文. 献. 1) Advanced Micro Devices, Inc. AMD PowerNow!TM Technology (2000). http://www.amd.com/epd/processors/6.32bitproc/8.amdk6fami/x24404/ 24404a.pdf 2) Armbrust, M., Fox, A., Griffith, R., Joseph, A.D., Katz, R.H., Konwinski, A., Lee, G., Patterson, D.A., Rabkin, A., Stoica, I. and Zaharia, M.: Above the Clouds: A Berkeley View of Cloud Computing, Technical Report UCB/EECS-2009-28, EECS Department, University of California, Berkeley (2009). 3) Barham, P., Dragovic, B., Fraser, K., Hand, S., Harris, T., Ho, A., Neugebauer, R., Pratt, I. and Warfield, A.: Xen and the Art of Virtualization, Proc. 19th ACM SIGOPS Symposium on Operating Systems Principles (SOSP’03 ), pp.299– 310 (2003). 4) Dean, J. and Ghemawat, S.: Mapreduce: Simplified data processing on large clusters, Proc. 6th Conference on Symposium on Opearting Systems Design & Implementation (OSDI’04 ), pp.137–150 (2004). 5) Govindan, S., Nath, A.R.. Das, A., Urgaonkar, B. and Sivasubramaniam, A.: Xen and Co.: Communication-aware CPU scheduling consolidated Xen-based hosting platforms, Proc. 3rd International ACM SIGPLAN/SIGOPS Conference on Virtual Execution Environments (VEE’07 ), pp.126–136 (June 2007). 6) Hill, M.D. and Marty, M.R.: Amdahl’s Law in the Multicore Era, IEEE Computer, Vol.41, No.7, pp.33–38 (2008).. c 2011 Information Processing Society of Japan .

(14) 38. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. 7) HP: Control power and cooling for data center efficiency (2006). 8) Hsu, C.-H. and Kremer, U.: The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction, Proc. ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI’03 ), pp.38–48 (2003). R 9) INTEL CORPORATION: Intel64 and IA-32 Architectures Software Developer’s Manual, (Nov. 2007). http://www.intel.com/design/processor/manuals/253668.pdf 10) Kansal, A., Zhao, F., Liu, J., Kothari, N. and Bhattacharya, A.: Virtual Machine Power Metering and Provisioning, Proc. 1st ACM Symposium on Cloud Computing (SOCC’10 ) (2010). 11) Lee, M., Krishnakumar, A.S., Krishnan, P., Singh, N. and Yajnik, S.: Supporting soft real-time tasks in the Xen hypervisor, Proc. 6th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE’10 ), pp.97–108 (2010). 12) Liu, X., Shenoy, P. and Corner, M.: Chameleon: Application level power management with performance isolation, Proc. 13th Annual ACM International Conference on Multimedia (MULTIMEDIA’05 ), pp.839–848 (2005). 13) Merkel, A., Stoess, J. and Bellosa, F.: Resource-consious Scheduling for Energy Efficiency on Multicore Processors, Proc. 5th ACM European Conference on Computer Systems (EuroSys’10 ), pp.289–302 (2010). 14) Nathuji, R. and Schwan, K.: VirtualPower: Coordinated power management in virtualized enterprise systems, Proc. 21st ACM SIGOPS Symposium on Operating Systems Principles (SOSP’07 ), pp.265–278 (2007). 15) Nathuji, R. and Schwan, K.: Vpm tokens: Virtual machine-aware power budgeting in datacenters, Proc. 17th International Symposium on High Performance Distributed Computing (HPDC’08 ), pp.119–128 (2008). 16) Panov, Y. and Jovanovic, M.: Design Considerations for 12-V/1.5-V, 50-A Voltage Regulator Modules, IEEE Trans. Power Electronics, Vol.16, No.6 (2001). 17) Red Hat, Inc.: KVM – KERNEL BASED VIRTUAL MACHINE (2009). http://www.redhat.com/f/pdf/rhev/DOC-KVM.pdf 18) Snowdon, D.C., Le Sueur, E., Petters, S.M. and Heiser, G.: Koala: A platform for OS-level power management, Proc. 4th ACM European Conference on Computer Systems (EuroSys’09 ), pp.289–302 (2009). 19) Stoess, J., Lang, C. and Bellosa, F.: Energy management for hypervisor-based virtual machines, Proc. 2007 USENIX Annual Technical Conference (ATC’07 ), pp.1–14 (2007). 20) Uhling, V., Le Vasseur, J., Skoglund, E. and Dannowski, U.: Towards Scalable Multiprocessor Virtual Machines, Proc. 3rd Virtual Machine Research and Tech-. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). nology Symposium (VM’04 ), pp.43–56 (2004). 21) Verma, A., Ahuja, P. and Neogi, A.: pMapper: Power and migration cost aware application placement in virtualized systems, Proc. 9th ACM/IFIP/USENIX International Conference on Middleware (Middleware’08 ), pp.243–264 (2008). 22) Verma, A., Dasgupta, G., Nayak, T.K., De, P. and Kothari, R.: Server Workload Analysis for Power Minimization using Consolidation, Proc. 2009 USENIX Annual Technical Conference (ATC’09 ), pp.355–386 (2009). 23) VMware, Inc.: Co-scheduling SMP VMs in VMware ESX Server (2008). http://communities.vmware.com/docs/DOC-4960 24) VMware, Inc.: VMware vSphere 4: The CPU Scheduler in VMware ESX 4 (2009). http://www.vmware.com/files/pdf/perf-vsphere-cpu scheduler.pdf 25) Weiser, M.. Welch, B., Demers, A. and Shenker, S.: Scheduling for reduced CPU energy, Proc. 1st USENIX Conference on Operating Systems Design and Implementation (OSDI’94 ), pp.12–23 (1994). 26) Wu, W., Lee, N. and Schuellein, G.: Multi-phase buck converter design with twophase coupled inductors, Proc. IEEE Applied Power Electronics Conference and Exposition (2006). (平成 22 年 7 月 26 日受付) (平成 22 年 11 月 13 日採録) 吉田哲也（学生会員）. 1983 年生まれ．2005 年電気通信大学電気通信学部情報工学科卒業．2008 年慶應義塾大学大学院理工学研究科開放環境科学専攻前期博士課程修了．現在，慶應義塾大学大学院理工学研究科開放環境科学専攻後期博士課程在籍．平成 21 年度情報処理学会論文賞受賞．仮想マシン技術，オペレーティングシステム等のシステムソフトウェアに興味を持つ．ACM，USENIX 各会員．. c 2011 Information Processing Society of Japan .

(15) 39. マルチコア CPU の電力消費特性を考慮した仮想 CPU スケジューラ. 山田浩史（正会員）. 河野健二（正会員）. 1981 年生まれ．2004 年電気通信大学電気通信学部情報工学科卒業．2009. 1993 年東京大学理学部情報科学科卒業．1997 年同大学大学院理学系研. 年慶應義塾大学大学院理工学研究科開放環境科学専攻後期博士課程修了．. 究科情報科学専攻博士課程中退，同専攻助手に就任．現在，慶應義塾大学. 現在，慶應義塾大学理工学部特別研究助教．博士（工学）．平成 20 年，21. 理工学部情報工学科准教授．博士（理学）．平成 11 年度，20 年度，21 年. 年度情報処理学会論文賞，平成 20 年度山下記念研究賞受賞．仮想マシン. 度情報処理学会論文賞受賞．平成 12 年度山下記念研究賞受賞．オペレー. 技術，オペレーティングシステム等のシステムソフトウェアに興味を持つ．. ティングシステム，システムソフトウェア，ディペンダブルシステム，イ. ACM，USENIX，IEEE/CS 各会員．. ンターネットセキュリティ等に興味を持つ．IEEE/CS，ACM，USENIX 各会員．. 佐々木広（正会員）. 中村. 宏（正会員）. 2003 年東京大学工学部計数工学科卒業．2005 年同大学大学院情報理工. 1985 年東京大学工学部電子工学科卒業．1990 年同大学大学院工学系研. 学系研究科修士課程修了．2008 年同大学院工学系研究科博士課程修了．博. 究科電気工学専攻博士課程修了．工学博士．同年筑波大学電子・情報工学. 士（工学）．同年東京大学先端科学技術研究センター特任助教．2010 年より. 系助手．同講師，同助教授を経て，1996 年東京大学先端科学技術研究セ. 東京大学大学院情報理工学系研究科特任助教．計算機アーキテクチャ，オ. ンター助教授，2010 年東京大学大学院情報理工学系研究科教授．この間，. ペレーティングシステムの研究に従事．IEEE，ACM，USENIX 各会員．. 1996∼1997 年カリフォルニア大学アーバイン校客員助教授．高性能・低消費電力 VLSI システム，省電力コンピューティング，ハイパフォーマンスコンピューティングの研究に従事．情報処理学会より論文賞（平成 5 年度），山下記念研究賞（平成 6 年度），坂井記念特別賞（平成 13 年度）各受賞．IEICE，IEEE，ACM 各会員．. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 2. 25–39 (Mar. 2011). c 2011 Information Processing Society of Japan .

(16)